CSC102 Lecture 1 and 2 (2).pdf

CSC 102 INTRODUCTION TO PROBLEM SOLVING LECTURE 1 OVERVIEW...

CSC 102 INTRODUCTION TO PROBLEM SOLVING LECTURE 1 OVERVIEW OF PROBLEM SOLVING: www.tech-u.edu.ng | [email protected]  Lecture Objectives ❑Introduction ❑General Problem Solving Strategies ❑Concepts of Algorithm ❑Major Components of Algorithm ❑Properties of Algorithm ❑Role of Algorithm in Problem Solving ❑Ways of expressing Algorithm ▪ Natural Language ▪ Pseudocode ▪ Flowchart  Introduction ❑ Problem solving is a compound word that is composed of two words, “Problem” and “Solving”. ❑ Problem has been defined in a number of ways; ▪ The dictionary definition holds that problem is a question raised for inquiry, consideration or solution ▪ In mathematics, problem has been defined as a situation that is to be resolved using well-defined mathematical principles. ❑ Solving on the other hand can be defined as a means of finding solution to a problem.  Introduction ❑ Based on the definitions of problem and solving, we can formally define problem solving as; ❑ The act of finding a solution to perplexing, distressing, vexing or unsettled question. ❑ Though the definition of problems cited in the first paragraph suits this definition, some of them are not suitable in the context of computing. ❑ This is because computers are limited in its problem solving capabilities. ❑ Computers cannot be used in solving problems involving physical activities or emotions.  Introduction ❑ A computer can be considered as an unintelligent device in that it cannot act unless when instructed to do so. ❑ It cannot analyze and proffer a solution to a problem without the programmer performing the analysis and providing the instructions in form of a program, which is fed into the computer in other to carry out the designated task. ❑ However, once a problem has been analyzed and instruction translated into program, the computer has the ability to carry out the processing in a very fast and consistent manner for different data entry.  General Problem Solving Strategies ❑ To solve a problem one has to understand the problem domain and the situation to avoid mistakes or incorrect assumptions. ❑ To be a better problem solver, there is a need to have a good understanding of the general problem-solving framework. ❑ One of the frameworks is the one outlined by Polya’s in his book “How to solve it”. ❑ The four Polya’s problem solving strategies are: General Problem Solving Strategies (Cont’d) ❑ Understanding the problem: ▪ Carefully read the problem to understand what needs to be accomplished. ▪ Assess one’s background skills in the area under consideration to know if there is need to acquire more skills in other to solve the problem. ▪ Visualize the final-result and use it as a guide in determining the validity of the solution and the result that will be obtained. ▪ Identify the known and the unknown (variables). ▪ Check the data and the conditions that needs to be satisfied. ▪ Check to know if the condition is sufficient to determine the unknown. ▪ Split the problem into parts and write down the parts. General Problem Solving Strategies (Cont’d) ❑ Device a plan: ▪ Check to see if there is a link between the data and the unknown (variable), ▪ if there is no link then try using auxiliary problem. ▪ Check if a similar problem exists so you can adapt the solution instead of reinventing the wheel. After all, the outcome of this phase is the plan of the solution. ❑ Carrying out the plan: ▪ In carrying out the plan, one have to go through the steps to know if they are correct, ascertain if there is any missing link. Check if the correctness of the plan can be proved. If the plan does not work correctly, discard it and try another plan. General Problem Solving Strategies (Cont’d) ❑ Looking Back: ❑ This is the moment of reflection. This is the phase that you can crosscheck what you have done to arrive at the present stage. ❑ In this phase, one can ascertain what worked and what did not work. This is the time the argument and results are verified for correctness and consistency. ❑ Also, one can check if the solution can be applied in other problems. This step can also ascertain if one can still get the same result using different methods.  Concepts of Algorithm ❑ Problem solving as we have seen involves the abstraction and decomposition of large amount of problem into smaller manageable subtasks that can be handled independently. ❑ An algorithm is important in the planning and execution of a problem solution since it specifies the sequence of steps needed to carry out the instructions that will lead to the overall result. ❑ An algorithm can be defined as a sequential set of instructions that are followed in other to solve a problem using a finite amount of data in a finite amount of time Concepts of Algorithm (Cont’d)  Concepts of Algorithm (Cont’d) ❑ More than one algorithm can be written for a particular problem. ❑ But the choice of selecting a particular algorithm in place of the other is dependent on the following factors: ▪ reliability ▪ Accuracy ▪ ease of modification and ▪ time required for the execution when converted to a high- level language  Major Components of Algorithm ❑ Most of the algorithms used in solving program related problems consist of three major sections: the input, processing and output. ❑ That is the summary of most if not all the activities undertaken by most algorithm in other to produce a result. ❑ To execute a task the algorithm requires some data (i.e. input), it performs some computation on the data (i.e. processing) then it produces result (i.e. output). ❑ The processing comprises of any or all of the following: computation, selection, iteration, etc.  Major Components of Algorithm ❑ The figure bellow shows the three major sections of an algorithm.  Properties of Algorithm ❑ Finiteness: An algorithm should be able to terminate after a finite number of instructions must have been processed. ❑ Definiteness: The algorithm should be developed in a form that each step will be precise and easy to understand. ❑ Effectiveness: This means that the algorithm should be in a form that will be easy to convert to a programming statement in a finite amount of time. ❑ Generality: The algorithm should be able to produce the same output when given different type of valid data. ❑ Input/output: The algorithm should be able to produce output value(s) when given a set of specified input value(s). There should be a relationship between the input and the output produced by the algorithm.  Role of Algorithm in Problem Solving ❑ Algorithm helps in the evaluation of a problem to know if it can be solved using a computer. Once an algorithm can be written for a problem then the problem can be solved using computational means. ❑ Algorithm helps in the identification of the various steps, major decision points and the variables needed to solve a problem. This are the concepts that are needed for the development of a computer program. ❑ Algorithm helps in the decomposition of a large task into small manageable subtasks. The decomposition helps in reducing the complexity of the problem and make it solvable.  Role of Algorithm in Problem Solving (Cont’d) ❑ The atomic nature of the tasks/subtasks of the algorithm makes the decision making process more rational in nature, since the subtasks are supported by facts. ❑ Given different tasks, one algorithm can be applied in performing all the tasks. This enhances the consistency and reliability of the problem solving process.  Ways of expressing Algorithm ❑ The expression of algorithm can come in three major ways. They are: ▪ Natural Language ▪ Pseudocode ▪ Flowchart  Natural Language It is a method of expressing algorithm using our day-to-day language, like English or other languages. This has been found to be disadvantageous as it is very wordy and confusing. ▪ Example of Natural Language ▪ Question: Write an algorithm in natural language to calculate the area of a triangle. (area = ½ * base * height)  Natural Language (Cont’d) ▪ Solution ✓ Step 1: Start ✓ Step 2: Select from the triangle the values for base and height ✓ Step 3: Calculate the product of the values (i.e. base and height) ✓ Step 4: Divide the product of base and height by 2 ✓ Step 5: The area is the result gotten after dividing base and height by 2 ✓ Step 6: Stop  Pseudocode This type of expression has a form that is closely related to a programming language though there is no restriction on the syntax. It is not ambiguous like the natural language. Pseudocode provides a means of designing computer programs independent of the programming languages and the make of the computers. It presents a good method of designing systems besides the flowchart. While the flowchart presents pictorial designs, pseudocode presents the system in statements that clearly state the various steps of the solution to the problem.  Pseudocode (Cont’d) Advantages ▪ It is easy to learn. ▪ It presents a more detailed overview of the system. ▪ It can be easily converted to programs. ▪ It lends itself to easy maintainability Disadvantages ▪ It may not be easily comprehensible to beginners. ▪ Error detection may be difficult. ▪ There is no standard way of writing pseudocodes.  Pseudocode (Cont’d) Example of Pseudocode ▪ Question: Write a pseudo code to calculate the area of a triangle ▪ Solution: ✓ Step 1: Start ✓ Step 2: Read base and height ✓ Step 3: Product = base x height ✓ Step 4: Area = product/2 ✓ Step 5: Print Area ✓ Step 6: Stop  Flow chart Flowcharting is one of the widely-used techniques for specifying an algorithm in Computer Science. A flowchart can simply be defined as a diagrammatic representation of algorithms. It is a pictorial representation of a complex procedure with considerable clarity. Uses symbols to represent the sequence of instructions. It is not ambiguous like the natural language, but the modification is done using a specialized tool. In addition, the implementation uses a standard rules.  Flow chart (Cont’d) Example of Flowchart ▪ Question: Draw a flowchart to calculate the area of a triangle - (area = ½ * base * height) ▪ Solution: Thank you What is a Flowchart? START Display message “How many hours did you work?” Read Hours Display message “How much do you get paid per hour?” Read PayRate Multiply Hours by PayRate. Store result in GrossPay. Display GrossPay END A flowchart is actually a graphical representation of a computer program in relation to its sequence of functions. Which will help the programmer to draw out the basic build block and working mechanism of the program or the system? In the flowchart, we generally use geometric symbols like a rectangle, oval shapes and arrows to define the relationships. In simple terms, it will explain the start and end of the program. Basic Flowchart Symbols Basic Flowchart Symbols Basic Flowchart Symbols Four Flowchart Structures ▪ Sequence ▪ Decision ▪ Repetition ▪ Case Sequence Structure Decision Structure The flowchart segment below shows how a decision structure is expressed in C++ as an if/else statement. Decision Structure The flowchart segment below shows a decision structure with only one action to perform. It is expressed as an if statement in C++ code. Flowchart C++ Code Repetition Structure Flowchart C++ Code while (x < y) YES x++; x < y? Add 1 to x Controlling a Repetition Structure Controlling a Repetition Structure YES x < y? Display x Add 1 to x Case Structure Connectors Modules Combining Structures Review Question Answer Pre- defined Process Symbols and functions Question Answer Question Answer Question Answer Question Answer Question Answer Representation of Flowchart Examples Adding two Numbers Examples Examples Basic Rules for Flowcharting 1. All boxes of the flowchart are connected with Arrows. (Not lines) 2. Flowchart symbols have an entry point on the top of the symbol with no other entry points. The exit point for all flowchart symbols is on the bottom except for the Decision symbol. 3. The Decision symbol has two exit points; these can be on the sides or the bottom and one side. 4. Generally a flowchart will flow from top to bottom. However, an upward flow can be shown as long as it does not exceed 3 symbols. 5. Connectors are used to connect breaks in the flowchart: Examples are: From one page to another page. From the bottom of the page to the top of the same page. An upward flow of more then 3 symbols Basic Rules (Cont’d.) 6) Subroutines and Interrupt programs have their own and independent flowcharts. 7) All flow charts start with a Terminal or Predefined Process (for interrupt programs or subroutines) symbol. 8) All flowcharts end with a terminal or a contentious loop. Advantages of Flowchart The benefits of flowcharts are as follows : Communication : Flowcharts are better way of communicating the logic of a system to all concerned. Effective Analysis : With the help of flowchart, problem can be analyzed in more effective way. Proper Documentation : Program flowcharts serve as a good program documentation, which is needed for various purposes. Efficient Coding : The flowcharts act as a guide or blueprint during the systems analysis and program development phase. Proper Debugging : The flowchart helps in debugging process. Efficient Program Maintenance : The maintenance of operating program becomes easy with the help of flowchart. It helps the programmer to put efforts more efficiently on that part. Disadvantages of Flowchart (i) For Lengthy programs or programs with complicated logic, drawing flowchart is very difficult (ii) If there is error in the flowchart it has to be redrawn (iii)Every instruction has to be represented with flowchart symbol, hence it difficult to draw (iv)The flowchart is not executable Examples ?? THANK YOU