Problem Solving Lecture Notes PDF

Problem Solving  Learning Outcomes At the end of this lecture, you should be able to: appreciate programming as a tool to solve problems. explain the system (software or program) development methodology. describe the steps involved in problem solving. identify the input, the p...

Problem Solving  Learning Outcomes At the end of this lecture, you should be able to: appreciate programming as a tool to solve problems. explain the system (software or program) development methodology. describe the steps involved in problem solving. identify the input, the process and the output of a given problem. identify and apply basic problem solving design techniques to design algorithms in solving problems (by using flow chart and pseudo code). LECTURE 2 2 Programming and Problem Solving What does problem solving have to do with programming? Well everything. Programming is about problem solving. Engineers and scientists are problem solvers. What a good problem solver does is often ask more questions. It's good to ask questions. LECTURE 2 3  Solving a Problem When solving a problem, the level of abstraction that you choose to look at, can influence how "easy" or "hard" the problem is to solve. Solving a problem can involve moving between these levels of abstraction: more detailed, less detailed.. You try the best you can, get an answer, and then try to improve. Always strive to improve. LECTURE 2 4  Solving a Problem When ever you have to solve problems especially big, hard ones: 1. Don't give up. 2. Ask more questions. 3. Break the problem into smaller problems. (Breaking into parts, more like divide and conquer) 4. Think of the benefits and profit that you’ll get. 5. As soon as you develop one solution, start thinking of another way and just don't settle with what you’ve got until you can’t think of other solutions. This is most important quality of a problem solver. LECTURE 2 5  PROBLEMS ALGORITHM (Flowchart) Selection Repetition Sequence CODING / C++ Program  Start Write a program that can get / receive 3 integer numbers and calculate Input n1,n2,n3 total numbers. Display total numbers Calculate Total=n1+n2+n3 Display Total Stop 7 LECTURE 6 Program Development (Programming) Programming is a creative process. A programming process critically determines the overall quality and success of the program. Therefore in a programming process, there is the outline of a plan (methodology) to follow. Most programming projects are built using a software development life cycle (SDLC) methodology. One of the popular models in SDLC is known as the waterfall model. LECTURE 2 8 SDLC : The Waterfall Model Software Problem Solving Phase Coding Implementation Phase Testing LECTURE 2 9  Programming Process Involves TWO major Phases (with 4 steps of processes) that requires you to do the following in their order: 1. Problem Solving Phase Involves Analysis (step 1) & Design (step 2) The result is an algorithm that solves the problem. 2. Implementation Phase Involves Coding (step 3)& Testing (step 4) The result is a program that has been translated from the algorithm using a programming language. LECTURE 2 10  Programming Approach To produce a program, we may use different programming approach. Procedural programming is a programming approach that focuses on the process. When procedural programming is used to solve big problems: a. It uses a top-down design to model the structure of the program. b. A big problem is divided into smaller sub problems. c. Solution of a sub problem actually involves a task or some tasks that are grouped as a module or sub- module, and are coded in a function of the program. LECTURE 2 11 Step 1 - Analysis : To understand the problem. Clearly define what is needed for the Input, Process & Output (IPO) to solve the problem. If solution requires top-down design, then draw a structure chart that contains the hierarchy of modules in the solution. Main Module Module 1 Module 2 Sub-module Sub-module Sub-module 1.1 1.2 2.1 LECTURE 2 12 Step 2 - Design the algorithm : To get the logical steps of achieving the problem’s solution. Algorithm is a set of well defined and precise instructions (or steps) that leads to a solution. Algorithm design - To determine how to take inputs and process them into the specified output. Algorithm must be tested for its correctness (no logic errors). Experience shows this saves time in getting your program to run correctly. Do corrections to the algorithm’s design as many times as necessary as long as there is still logic error in the algorithm. LECTURE 2 13  If any program is designed carefully using good and structured development techniques, the program will be efficient, error-free and easy to maintain. Algorithm can be designed using: a) Pseudo code or b) Flowchart LECTURE 2 14 a) Pseudo code Precise algorithmic description of program logic. Its purpose is to describe, in precise algorithm detail, what the program being design is to do. Requires the defining the steps to accomplish the task in sufficient detail so that they can be converted into a computer program. LECTURE 2 15 b) Flow Chart A schematic (diagram) representation of a sequence of operations in a process. Program flowcharts show the sequence of instructions in a single program or subroutine. Different symbols are used to represent different operations in a flowchart. LECTURE 2 16 Basic Symbols of a Flow Chart Represent Various Operations Direction Preparation Terminal – Process beginning / end Decision Input / Output Connector Predefined Process (Call to a function) LECTURE 2 17 Step 3 - Coding : Write, save and compile the program code using the IDE. Program is an algorithm that has been expressed in a programming language. The coding process is easier as you gain experience with the programming language. Correct any syntax errors found during program compilation. Do corrections to the program codes as many times as necessary until there is no more syntax error in the program. LECTURE 2 18 Step 4 - Test the program : Run the program on sample data. Repeat Step 4 as many times as necessary to validate the result of the program. Correct any run-time and logic errors found. These two types of errors may require modification of the algorithm and program code, which means it need to repeat from step 2 or step 3. LECTURE 2 19 Problem Solving Examples: Problem 1 Problem Statement (or software requirements) Your summer surveying job requires you to study some maps that give distances in miles. You and your co- workers prefer to deal in metric measurements (km). Write a program that performs the necessary conversion. The program will display the distance in km. Formula: (1 mile = 1.609 kilometers) LECTURE 2 20 a) Solution of Problem 1 (using top down design) Step 1: Analysis i. Highlight the problem statement. Your summer surveying job requires you to study some maps that give distances in miles. You and your co- workers prefer to deal in metric measurements (km). Write a program that performs the necessary conversion. The program will display the distance in km. Formula: (1 mile = 1.609 kilometers) LECTURE 2 21 ii. Identify : What are the INPUTs, PROCESSes, OUTPUTs? Input – the distance in miles : M Process (include the formula) – Convert distance in miles to kilometers (Formula given : 1 mile = 1.609 kilometers) – Therefore to calculate distance in kilometers: K = M x 1.609 Output – the distance in kilometers : K LECTURE 2 22 iii. Draw a Structure Chart (**only if problem solution uses top-down design) main {conversion problem} convert display input {miles to {distance in {distance in miles} kilometers} kilometers } LECTURE 2 23  Step 2: Design the Algorithm. a) Algorithm using Pseudo code 1.0 Start 2.0 Call function input 2.1 Read distance in miles : M 2.2 Return M 3.0 Call function convert 3.1 Calculate distance in kilometer : K= M x 1.609 3.2 Return K 4.0 Call function display 4.1 Display the distance in kilometers : K 5.0 Stop LECTURE 2 24 b) Algorithm using Flow Chart input () convert (M) Start Read distance in miles (M) K = M * 1.609 M = input() Return Return M K K = convert(M) display (K) Display distance display(K) in kilometers (K) Return Stop LECTURE 2 25 Step 3: Code the program #include Preprocessor directives using namespace std; Namespace double input(); //global declaration void display(double K); Global double convert(double M); Declaration Area int main() { double M, K; //local declaration //M represents distance in miles //K represents distance in kilometers Main Function M = input(); K = convert(M); display(K); return 0; } LECTURE 2 26 double input() { double miles; User- coutmiles; Function return miles; } double convert(double distance_in_miles) { double km; User- km = distance_in_miles * 1.609; Defined return km; Function } void display(double distance_in_km) User- { Defined cout