Computer Science Algorithms and Problem Solving 2015 PDF

Topic 2: Algorithms and Problem Solving © 2015 Pearson Education Limited 2015 Chapter 5  Chapter 5: Algorithms and Problem Solving What Is A Computer Program? Software? An Overview of Computer Languages The Software Development Method An Example of...

Topic 2: Algorithms and Problem Solving © 2015 Pearson Education Limited 2015 Chapter 5  Chapter 5: Algorithms and Problem Solving What Is A Computer Program? Software? An Overview of Computer Languages The Software Development Method An Example of Meter to Yard Conversion Algorithm Polya’s Problem Solving Steps Pseudocode Flowcharts Algorithm Representation Control Structures Pseudocode Primitives Flowchart Examples © 2015 Pearson Education Limited 2015 5-2  What Is A Computer Program? Software? Program = set of instructions that a computer will follow to perform a specific task. Software = collection of programs. Two types of software: System software: used to manage computer hardware to enable us to execute & write application programs/software. Ex. Operating System, Compilers, Programming Languages…etc. Application Software: are meant for solving users own problems. Ex. Word processors, database management…etc. © 2015 Pearson Education Limited 2015 2  An Overview Of Computer Languages Machine Language Assembly Language High-Level Language Collection of binary Symbolic form of machine Combines algebraic numbers language (I.e. symbolic expressions & symbols taken names are used to represent from English language operations, registers & (ex. C, Pascal, memory locations FORTRAN, Python …etc) Ex. Ex. Ex. 10100001 00000000 00000000 MOV AX,A A=A+ 4 00000101 00000100 00000000 ADD AX,4 10100011 00000000 00000000 MOV A,AX Directly understood by a Assembler Compiler (or interpreter) computer converts to machine converts to machine language language Easier to use More powerful © 2015 Pearson Education Limited 2015 5  Machine Languages Python, Java, C, and C++ are, indeed, examples of high- level languages Strictly speaking, computer hardware can only understand a very low-level language known as machine language If you want a computer to add two numbers, the instructions that the CPU will carry out might be something like this: Load the number from memory location 2001 into the CPU Load the number from memory location 2002 into the CPU A Lot of Add the two numbers in the CPU Work! Store the result into location 2003 © 2015 Pearson Education Limited 2015  High-Level to Low-Level Languages In a high-level language like Python, the addition of two numbers can be expressed more naturally: c=a+b Much Easier! But, we need a way to translate the high-level language into a machine language that a computer can execute – To this end, high-level language can either be compiled or interpreted © 2015 Pearson Education Limited 2015  Compiling a High-Level Language A compiler is a complex software that takes a program written in a high-level language and translates it into an equivalent program in the machine language of some computer Source Code Machine Compiler (Program) Code Running Inputs Outputs Program © 2015 Pearson Education Limited 2015  Interpreting a High-Level Language An interpreter is a software that analyzes and executes the source code instruction- by-instruction (on-the-fly) as necessary Source Code (Program) Computer Running An Outputs Interpreter Inputs E.g., Python is an interpreted language © 2015 Pearson Education Limited 2015  9 The Software Development Method The process of creating application programs 1 Problem Analysis 4 2 Testing and Program Documentation Design 3 Program Coding © 2015 Pearson Education Limited 2015  The Software Development Method (expanded) 1. Specify the problem requirements. 2. Analyze the problem. 3. Design the algorithm to solve the problem. 4. Implement the algorithm. 5. Test and verify the completed program. 6. Maintain and update the program. © 2015 Pearson Education Limited 2015 7  An Example of Meter to Yard Conversion 1. Specify the problem requirements A program is required to convert square meters to square yards. 2. Analyze the problem Problem Input: size in square meters (decimal) Problem Output: size in square yards (decimal) Formulas: square yards = 1.196 * square meters 3. Design the algorithm to solve the problem 1. Read the fabric size in square meters. 2. Convert the fabric size to square yards using the formula. 3. Display the fabric size in square yards. © 2015 Pearson Education Limited 2015 8  An Example of Meter to Yard Conversion 4. Implement the algorithm (i.e. write the program) 5. Test and verify the completed program. 6. Maintain and update the program. © 2015 Pearson Education Limited 2015 9 Polya’s Steps for Problem Solving in the Context of Program Development 1. Understand the problem. 2. Get an idea of how an algorithmic function might solve the problem. 3. Formulate the algorithm and represent it as a program. 4. Evaluate the solution for accuracy and its potential as a tool for solving other problems. © 2015 Pearson Education Limited 2015 5-13  Ages of Children Problem Person A is charged with the task of determining the ages of B’s three children. – B tells A that the product of the children’s ages is 36. – A replies that another clue is required. – B tells A the sum of the children’s ages. – A replies that another clue is needed. – B tells A that the oldest child plays the piano. – A tells B the ages of the three children. How old are the three children? © 2015 Pearson Education Limited 2015 5-14  Figure 5.5 © 2015 Pearson Education Limited 2015 5-15  Algorithm An Algorithm is a procedure for solving a problem in terms of: 1. the actions to be executed 2- the order in which these actions are executed © 2015 Pearson Education Limited 2015 10  Pseudocode Pseudocode is an informal language that helps programmer develop algorithms. It is similar to everyday English. It is not a computer programming language specific. Example Get out of Bed Take a shower Get dressed Eat breakfast Drive to work © 2015 Pearson Education Limited 2015 11  Flowcharts A flowchart is a graphical representation of an algorithm. They are drawn using rectangles, parallelograms, diamonds, ovals, and small circles. © 2015 Pearson Education Limited 2015 12  Flowchart 19  A visual representation of the program using predefined symbols  Start / Stop  Input / Output  Processing CSCE101-Computer and Information Skills.  Flowchart 20  Flow Line  Conditional CSCE101-Computer and Information Skills.  Algorithm Representation Requires well-defined primitives (‫)عمليات بدائية‬ A collection of primitives constitutes a programming language. © 2015 Pearson Education Limited 2015 5-21  Control Structures 22  The order in which the programming statements are executed  There are three main control flows: CSCE101-Computer and Information Skills.  Pseudocode Primitives Assignment name = expression Example RemainingFunds = CheckingBalance + SavingsBalance © 2015 Pearson Education Limited 2015 5-23  Pseudocode Primitives (continued) Conditional selection if (condition): activity Example if (sales have decreased): lower the price by 5% © 2015 Pearson Education Limited 2015 5-24  Pseudocode Primitives (continued) Conditional selection if (condition): activity else: activity Example if (year is leap year): daily total = total / 366 else: daily total = total / 365 © 2015 Pearson Education Limited 2015 5-25  Pseudocode Primitives (continued) Repeated execution while (condition): body Example while (tickets remain to be sold): sell a ticket © 2015 Pearson Education Limited 2015 5-26  Pseudocode Primitives (continued) Indentation shows nested conditions if (not raining): if (temperature == hot): go swimming else: play golf else: watch television © 2015 Pearson Education Limited 2015 5-27  Figure 5.8 The while loop structure SET count = 1 WHILE count