Summary — What This Chapter Covers
- Abstraction keeps only the details that matter for the problem and hides the rest.
- Decomposition breaks a problem into sub-problems, each of which becomes a module: a procedure or a function.
- An algorithm is a solution to a problem written as a sequence of defined steps.
- Identifiers should be meaningful and recorded in an identifier table.
- Every algorithm is built from three constructs: sequence, selection and iteration, with input, process and output.
- Algorithms can be documented as structured English, a flowchart or pseudocode, and converted between these forms.
- Stepwise refinement breaks each step down until it can be programmed directly.
- Logic statements (conditions using AND, OR, NOT and relational operators) define the decisions in an algorithm.
1. Abstraction
Computational thinking skills
Keep only what matters
Abstraction means removing details that are not needed to solve a problem, so that a model includes only the essential details. A metro map is an abstraction: it shows stations, lines and connections but not the real distances or streets, because a passenger only needs to know the order of stations and where to change.
Purpose and benefits: the problem becomes simpler to understand and solve; development is quicker because effort goes only on what matters; programs are smaller and easier to maintain; the model can be reused for similar problems; the user is not distracted by unnecessary detail.
Worked Example
A gym wants a program to book classes. Produce an abstract model of a member by listing only the essential data.
2. Decomposition
Computational thinking skills
Break it into modules
Decomposition breaks a complex problem into smaller sub-problems, and those into smaller ones again, until each part is simple enough to solve on its own. Each sub-problem becomes a module of the program: a procedure (carries out a task) or a function (carries out a task and returns a single value).
Benefits: each module can be written and tested separately, possibly by different programmers at the same time; modules can be reused; errors are easier to find; the program is easier to understand and maintain.
Practice Question
Decompose a program that marks a multiple-choice quiz into modules, saying whether each is a procedure or a function.
3. Algorithms and Identifier Tables
Algorithms
Defined steps and meaningful names
An algorithm is a solution to a problem expressed as a sequence of defined steps that always terminates. Each step must be precise enough that there is only one way to carry it out.
Identifiers (names of variables, constants, procedures, functions) should describe what they hold, use mixed case (TotalCost), start with a letter, contain only letters, digits and underscores, and never be a keyword. An identifier table documents them:
| Identifier | Data type | Description |
|---|
| Num |
INTEGER |
| Total |
INTEGER |
| Count |