Algorithm Design and Problem Solving (Unit 9) - Computer Science

UNIT 9 : Algorithm Design and problem solving **Computational Thinking Skills** **Abstraction --** the process of extracting information that is essential, while ignoring what is not relevant, for the provision of a solution. **Decomposition --** the process of breaking a complex problem into...

UNIT 9 : Algorithm Design and problem solving **Computational Thinking Skills** **Abstraction --** the process of extracting information that is essential, while ignoring what is not relevant, for the provision of a solution. **Decomposition --** the process of breaking a complex problem into smaller parts. **Pattern recognition --** the identification of parts of a problem that are similar and could use the same solution. **[Using Abstraction]** Abstraction is an essential part of computational thinking. It enables computer scientists to develop clear models for the solution to complex problems. Abstraction involves extracting information that is essential while ignoring what is not relevant for the provision of a solution, only including what is necessary to solve that problem. The **benefits** of eliminating any unnecessary characteristics from the model include: - - - **[Using Decomposition]** Decomposition is also an essential part of computational thinking. It enables computer scientists to break a complex problem into smaller parts that can be further subdivided into even smaller parts until each part is easy to examine and understand, and a solution can be developed for it. Pattern recognition is used to identify those parts that are similar and could use the same solution. This leads to the development of reusable program code in the form of subroutines, procedures and functions. **Algorithms** **Structured English --** a method of showing the logical steps in an algorithm, using an agreed subset of straightforward English words for commands and mathematical operations. **Flowchart --** a diagrammatic representation of an algorithm. **Algorithm --** an ordered set of steps to be followed in the completion of a task. **Pseudocode --** a method of showing the detailed logical steps in an algorithm, using keywords, identifiers with meaningful names, and mathematical operators. **Stepwise refinement --** the practice of subdividing each part of a larger problem into a series of smaller parts, and so on, as required. **[Writing algorithms that provide solutions to problems]** Here are three frequently used methods: - - - **[Writing simple algorithms using pseudocode]** Each line of pseudocode is usually a single step in an algorithm. All identifier names used in pseudocode should be meaningful. **To input a value:** INPUT StudentName **To output a value:** OUTPUT \"You have made an error\" OUTPUT StudentName OUTPUT \"Student name is \", StudentName **To assign a value to a variable:** Counter ← 1 Counter ← Counter + 1 MyChar ← \"A\" LetterValue ← ASC(MyChar) StudentMark ← 40 Percentage ← (StudentMark / 80) \* 100 Oldstring ← \"Your mark is\" NewString ← OldString & \" ninety-seven\" **Operators used in pseudocode:** Addition \+ ---------------------- ---- Subtraction \- Multiplication \* Division / String concatenation & Assignment ← **Relational operators used in pseudocode selection statements:** Equal to = -------------------------- ------ Not equal to \ Greater than \> Less than \< Greater than or equal to \>= Less than or equal to \ - - **[Writing pseudocode from a structured English description]** The wording needs to be unambiguous and easily understandable. From a structured English description, the following things need to be possible: - - - - - Each structured English statement can be used to write one or more pseudocode statements, keeping the same order as the structured English.   **[Writing pseudocode from a flowchart]** Flowcharts can be used to identify any variables required and you can then complete an identifier table. Each flowchart symbol can be used to identify and write one or more pseudocode statements. **[Stepwise refinement]** The algorithms looked at so far have been short and simple. When an algorithm is written to solve a more complex problem, decomposition is used to break the problem down into smaller and more manageable parts. These parts then need to be written as a series of steps where each step can be written as a statement in a high-level programming language, this process is called stepwise refinement.  Each of these steps can be broken down further: And written in pseudocode: