Intro to Programming and Problem Solving Techniques (Pt. 1).pptx

Introduction to Programming and Problem Solving Techniques History of Programming The First Computer Programmer  In 1842-1843, Ada Lovelace translated an article about Charles Babbage’s proposed Analytic Engine.  In her notes, she described an algorithm that is cited as the...

Introduction to Programming and Problem Solving Techniques History of Programming The First Computer Programmer  In 1842-1843, Ada Lovelace translated an article about Charles Babbage’s proposed Analytic Engine.  In her notes, she described an algorithm that is cited as the first computer program, making her the first computer programmer.  She also theorized that the computer could, one day, play music and chess.  ADA, a U.S. Department of Defense computer language, is named in her honor The Jacquard Loom  In 1801, Joseph Marie Jacquard invented the Jacquard loom. A mechanical, automated loom.  Used changeable punched cards to control the operation of the loom  The punched card was later used by Charles Babbage as a method for storing programs for the Analytic Engine Electric Tabulating System  In 1889, Herman Hollerith developed the idea of the Electric Tabulating System, a machine that could read data.  Hollerith also used punched cards, known as Hollerith cards, after experimenting with paper tape.  He also invented the tabulator and keypunch machines. Along with Hollerith cards, these form the basis for information processing. Electronic Tabulating System  In 1896, he founded Tabulating Machine Company, which later became IBM.  In 1906, he developed a plug board or control panel, that allowed the machine to perform different tasks without being reconstructed. Atanasoff-Berry Computer (ABC)  Developed in 1937 and tested in 1942, the first electronic digital computer, the Atanasoff-Berry Computer (ABC) was designed to solve linear equations.  Although it was not programmable, it did use binary arithmetic, regenerative memory, parallel processing, and a separate memory. Colossus Machine  Used in World War II, the Colossus machines were the first programmable, electronic digital computers.  The Colossus machines were designed to break and read encrypted German messages. The First Actual Computer “Bug”  In 1947, Grace Murray Hopper, an admiral in the U.S. Navy and computer programming pioneer, documented the first actual computer “bug” when a moth got trapped in the Mark II Alken Relay Calculator.  They removed the moth and “debugged” the computer. The Electronic Delay Storage Automatic Calculator (EDSAC)  The Electronic Delay Storage Automatic Calculator, or EDSAC, was the first practical stored- program electronic computer.  On May 6, 1949, EDSAC ran its first program: calculating a table of squares and a list of prime numbers. FORTRAN  The first high level computer programming language used: FORTRAN  Invented by John Backus of IBM in 1954.  It was released commercially in 1957. SPACEWAR!  The first computer game, Spacewar! was developed in 1961.  Programmed by Steve Russel, Spacewar! is a two-player game where two spaceships, affected by the gravity, at each other.  Took roughly 200 man-hours to complete.  At Stanford University, Russell introduced Nolan Bushnell to Spacewar!  Bushnell went to program the first coin-operated arcade game and later started Atari Computers Fred Cohen  In 1983, Fred Cohen designed a hidden program that could infect a computer, copy itself, and then infect other computers through the use of floppy disk.  The program was benign, meant only to prove that it was possible. Overview of Programming Recap:  Hardware: Electronic Devices  Software: Instructions and Computer Programs Hardware  Input: Keyboard, Mouse  System unit:  Random Access Memory (RAM)  Central Processing Unit (CPU)  Output:Monitor, Printer  Secondary Storage: Disk Drive Software  Instructions for the hardware.  Actions to be performed  A set of instructions is called a program.  Driving force behind the computer  Without a program – What is a computer? ▪ Collection of Useless Hardware  2 purposes:  Tell the computer what to do  Tell other people what we want the computer to do. CPU  The central processing unit (CPU)  The “brain” of a computer  Retrieves instructions from memory and executes them. Memory (RAM)  Stores data and program instructions for CPU to execute  A program and its data must be brought to memory before they can be executed  Stores intermediate and final results of processing.  Volatile: Contents are erased when computer is turned off or reset.  A memory unit is an ordered sequence of bytes, each holds eight bits.  A byte is the minimum storage unit. No two data can share or split the same byte. Storage Devices  Hard Drives, CDs/DVDs, Flash Drives, etc.  Non-Volatile or Permanent Storage  Programs and data are permanently stored on storage devices and are moved to memory when the computer actually uses them. Computer Language  Digital devices have two stable states, which are referred to as zero and one by convention  The binary number system has two digits, 0 and 1. A single digit (0 or 1) is called a bit, short for binary digit. A byte is made up of 8 bits.  Binary Language: Data and instructions (numbers, characters, strings, etc.) are encoded as binary Computer Language (cont.)  Encoding and decoding of data into binary is performed automatically by the system based on the encoding scheme  Encoding schemes  Numeric Data: Encoded as binary numbers  Non-Numeric Data: Encoded as binary numbers using representative code ▪ ASCII – 1 byte per character Programming Languages  Computers can not use human languages, and programming in the binary language of computers is a very difficult, tedious process  Therefore, most programs are written using a programming language and are converted to the binary language used by the computer  Three major categories of prog languages:  Machine Language  Assembly Language  High level Language Machine Language  Natural language of a particular computer  Primitive instructions built into every computer  The instructions are in the form of binary code  Any other types of languages must be translated down to this level Assembly Languages  English-likeAbbreviations used for operations (Load R1, R8)  Assembly languages were developed to make programming easier  The computer cannot understand assembly language - a program called assembler is used to convert assembly language programs into machine code High Level Languages  English-like and easy to learn and program  Common mathematical notation  Total Cost = Price + Tax;  area = 5 * 5 * 3.1415;  Java, C, C++, FORTRAN, VISUAL BASIC, PASCAL  Compiling Source Code A program written in a high-level language is called a source program (or source code). Since a computer cannot understand a source program. Program called a compiler is used to translate the source program into a machine language program called an object program. The object program is often then linked with other supporting library code before the object can be executed on the machine. Source File Compiler Object File Linker Excutable File 27 Programming  Programming – the creation of an ordered set of instructions to solve a problem with a computer.  Only about 100 instructions that the computer understands - Different programs will just use these instructions in different orders and combinations.  The most valuable part of learning to program is learning how to think about arranging the sequence of instructions to solve the problem or carry out the task Programming Fundamentals: Putting the Instructions Together  Sequential Processing  A List of Instructions  Conditional Execution  Ifs  Repetition  Looping / Repeating  Stepwise Refinement / Top-Down Design  Breaking Things into Smaller Pieces  Calling Methods / Functions / Procedures / Subroutines  Calling a segment of code located elsewhere  Reuse of previously coded code segment Methods of Programming  Procedural  Defining set of steps to transform inputs into outputs  Translating steps into code  Constructed as a set of procedures  Each procedure is a set of instructions  Object-Oriented  Defining/utilizing objects to represent real-world entities that work together to solve problem  Basic O-O Programming Components ▪ Class ▪ Object/Instance ▪ Properties ▪ Methods Problem Solving Techniques Problem Solving  Theprocess of defining a problem, searching for relevant information and resources about the problem, and of discovering, designing, and evaluating the solutions for further opportunities. Includes:  Finding an Answer to a Question  Figuring out how to Perform a Task  Figure out how to Make Things Work Polya’s 4 Steps of Problem Solving U – Understand the Problem D – Devise a Good Plan to Solve I – Implement the Plan E – Evaluate the Solution Example: Solving Math Word Problem  Read the Problem: Understand the description of problem or scenario, identifying the knowns and unkowns  Decide how to go about solving the problem: Determine what steps need to be taken to reach the solution  Solve the Problem: Write the solution  Test the Answer: Make sure the Solving Computing Problems  In general, when we solve a computing problem we are taking some inputs, processing (performing some actions on) the inputs, and then outputting the solution or results.  This is the classic view of computer programming – computation as calculation  Polya’s steps (UDIE) can be very Applying Polya’s Problem Solving to Programming Step 1 - Understand the Problem  What is the Problem to be solved? What is the unknown? What is the condition? What is the data? What is needed to solve the problem? What actions need to take place?  Identify the inputs and outputs  Identify the processes needed to produce the outputs from the given inputs  Draw a figure. Introduce suitable Applying Polya’s Problem Solving to Programming Step 2 - Devise a Plan  Findconnections between the knowns and unknowns.  Simplify: Break the problem into smaller sub-problems  Design a solution  Make a plan or list of actions to implement the solution  Algorithm / Flowchart / Psuedocode Applying Polya’s Problem Solving to Programming Step 2 - Devise a Plan (cont.)  Algorithm  A FINITE set of clear, executable steps that will eventually terminate to produce the desired outcome  Logical design used to solve problems – usually a list of actions required to perform task  Pseudocode  Written like program code but more “English Like” and doesn’t have to conform to language syntax  Flowchart  Diagram that visually represents the steps to be Programming Step 3 - Implement the Plan  Implement in a Programming Language  Carry out the plan checking the preliminary results at each step.  Code A Little Test A lot Programming Step 4 - Evaluate the Solution  Run the Code  Check results repeatedly and thoroughly  Use numerous test cases or data sets  Use highly varied test case, including expected as well as and unexpected cases  Look for new solutions  Is there a better, easier, or more efficient solution Summary U - Read the Problem Statement  Identify the inputs, outputs, and processes D - Decide how to Solve the Problem  Create an Algorithm / Flowchart / Psuedocode I - Program the Code  Implement in Programming Language E - Test the Solution  Run the Code using numerous, varied