Computer Science · Ch 4 — Introduction to Problem Solving
Summary
Summary
- Problem solving is the process of identifying a problem, developing an algorithm for it, and implementing that algorithm as a computer program. Computers cannot solve problems themselves — they need precise step-by-step instructions.
- The key steps of problem solving with a computer are: analysing the problem, developing an algorithm, coding, and testing and debugging (followed by ongoing maintenance after delivery).
- An algorithm is a step-by-step procedure designed to perform an operation which, if followed correctly, leads to the desired result. It has a definite beginning, a definite end, and a finite number of steps.
- A good algorithm is precise, unique and finite; it receives input and produces output. To write an effective algorithm we must identify the input, the process to be followed, and the desired output.
- GIGO (Garbage In Garbage Out): the correctness of a computer's output depends on the correctness of the input provided.
- An algorithm can be represented by a flowchart — a diagram that shows the algorithm graphically using boxes of various kinds (terminator, process, decision, input/output) connected by arrows — or by pseudocode, a non-formal, human-readable description using keywords such as INPUT, COMPUTE, PRINT, IF/ELSE and WHILE; pseudocode cannot be executed by a computer.
- Flow of control can take three forms:
- Sequence — all steps execute one after the other;
- Selection — one of the alternatives is chosen based on the true/false outcome of a condition (conditionals, written as if / if-else);
- Repetition (iteration/loop) — a set of steps repeats for a finite number of times, or while a condition holds (the WHILE construct handles an unknown number of repetitions).
- Verifying an algorithm means taking different input values and walking through the steps by hand — a dry run — to catch incorrect steps and missing details before coding. Untested input cases are where programs fail; fixing a mistake at the algorithm stage costs the least effort.
- There can be more than one algorithm for the same problem. Algorithms are compared on time complexity (processing time needed) and space complexity (memory needed), and the choice between them is made on this basis. …