Problem solving and algorithm representation
Programming is, above all, solving problems. The language comes later: first you have to understand what is being asked, plan the solution and be able to explain it without ambiguity.
01What an algorithm is
A cooking recipe, the instructions for assembling a piece of furniture and the procedure for measuring a resistance with a multimeter have something in common: they are steps that, followed to the letter, lead to a result. An algorithm is exactly that, with one more requirement: it must be possible for someone who does not understand the problem to follow it, such as a computer. Donald Knuth asks for five properties:
| Property | What it requires | A recipe violates it if… |
|---|---|---|
| Finiteness | It ends after a finite number of steps | it says “stir until done” |
| Definiteness | Each step is precise and unambiguous | it says “a pinch of salt” |
| Input | It has zero or more well-specified starting data | it does not say how many servings it makes |
| Output | It produces at least one result related to the input | — |
| Effectiveness | Each step can be done with pencil and paper in a finite time | it asks for “just the right point” |
The algorithm is the idea, independent of the language. The program is an algorithm written in a language that a machine can execute. Euclid’s algorithm is 2300 years old; its programs, a few decades. First you think of the algorithm, then you write the program, and the most expensive mistakes are the ones made before touching the keyboard.
02A method for solving problems
In 1945 George Pólya proposed four phases for solving mathematics problems that fit programming exactly:
- Understand the problem. What are the data? What is being asked? What conditions apply? What unusual cases may appear?
- Devise a plan. Does it resemble a problem already solved? Can it be split into smaller problems?
- Carry out the plan, checking each step: in programming, coding.
- Examine the solution. Test it with known cases and with the unusual cases from phase 1.
1 · Understand. Data: N resistance values. Result: the equivalent resistance of the parallel combination. Condition: \( \frac{1}{R_{\operatorname{eq}}} = \sum_{i = 1}^N \frac{1}{R_i} \). Unusual cases: a 0 Ω resistor is a short circuit and makes Req = 0 (and the formula would divide by zero); a negative value is a data-entry error; N = 0 makes no sense.
2 · Plan. It is an accumulation: add up the conductances in an accumulator and invert at the end.
3 · Carry out. Write the pseudocode, then the program.
4 · Examine. Two equal 100 Ω resistors must give 50 Ω; 100 Ω and 0 Ω, 0 Ω; a single resistor, its own value.
The unusual cases of phase 1 are the ones that get forgotten later. Writing them down before programming is half of testing.
03Tools for representing algorithms
Before writing code it is advisable to express the algorithm in a notation that does not distract with details of the language. There are three classic ones:
Structured natural language with keywords (If, While, For). It is the closest to code and the fastest to write.
Standardized symbols joined by arrows (ISO 5807). It shows the possible paths at a glance, but it gets tangled in long algorithms.
Also called a Chapin chart. Nested boxes with no arrows: by construction it only allows the permitted control structures.
04Three structures are enough for everything
In 1966 Corrado Böhm and Giuseppe Jacopini proved that any algorithm can be written by combining just three structures, each with one entry and one exit:
One step after another.
Choosing a path according to a condition: If … then … else …, or Case for several cases.
Repeating while a condition holds: While, Repeat … until, For.
Since each structure has a single entry and a single exit, they can be nested like boxes, and each one can be reasoned about separately. That is structured programming, and it is the basis of the next topic.
| Iteration | When it evaluates | Minimum iterations | Used when… |
|---|---|---|---|
| While | Before each iteration | 0 | no iterations may be needed at all |
| Repeat … until | After each iteration | 1 | something must be done at least once, such as reading a value and validating it |
| For | Before, with a counter | 0 | it is known in advance how many iterations there will be |
05The desk check
Before trusting an algorithm you have to run it by hand, with a pencil, recording in a table the value of each variable every time it changes. This is the desk check, and it is the tool that finds the most errors per minute invested. The machine below does it step by step: choose an algorithm, enter the data and step through it.
Desk-check table
That an algorithm terminates has to be proved. In Euclid’s, the remainder r is always smaller than b, so b decreases on every iteration and is a non-negative integer: it cannot decrease forever. And it is correct because gcd(a, b) = gcd(b, a mod b): that equality holds on every iteration. A property that is preserved on every iteration is called a loop invariant.
06Stepwise refinement
Niklaus Wirth proposed in 1971 designing from the top down: first write the solution in coarse steps and then replace each coarse step with its detail, until everything is executable. Each coarse step ends up being a function.
// Level 1: the whole problem
Read the resistance values
Compute the equivalent resistance
Display the result
// Level 2: “Compute the equivalent resistance”
g ← 0
For i ← 1 to N do
If R[i] = 0 then
Req ← 0 ; stop // there is a short circuit
g ← g + 1 / R[i]
EndFor
Req ← 1 / gThe advantage is not only order: at each level you can verify that the plan is correct without having written the detail yet.
07Correct is not enough: efficient too
Two correct algorithms can take very different amounts of time. Efficiency is measured by counting how many operations they perform as a function of the input size n, regardless of the machine.
Searching for a value in a list of n elements by scanning it takes, in the worst case, n comparisons. If the list is sorted, binary search looks at the middle element, discards the half that cannot contain it and repeats: in the worst case it makes ⌊log2 n⌋ + 1 comparisons.
| Elements n | Sequential search | Binary search |
|---|---|---|
| 10 | 10 | 4 |
| 1,000 | 1,000 | 10 |
| 1,000,000 | 1,000,000 | 20 |
The first is said to be of order n, O(n), and the second of logarithmic order, O(log n). With a million data items, a faster computer does not make up for choosing the wrong algorithm.
08In the lab
For an electronics problem —the nearest E12 standard value to a calculated resistance, or the power dissipated by each resistor in a divider— carry out Pólya’s four phases in writing, the flowchart and the desk check with three sets of data, one of them an unusual case.
Add an iteration counter to Euclid’s algorithm and test it with two consecutive Fibonacci numbers (89 and 55, 144 and 89). Compare with other pairs of the same size: the Fibonacci pairs are the worst case.
Write the pseudocode in PSeInt, which executes it and draws the flowchart by itself, and check that the output matches the desk check.
09Common mistakes
- Starting to program without having understood the problem. It shows when the program “works” but solves something else.
- The off-by-one error (also called a fencepost error): the loop runs one iteration too many or too few. It is detected in the desk check by looking at the first and last iterations.
- A loop that never ends because the condition variable does not change inside it.
- Testing only the easy case. You must test zero, one, the empty case and the extremes.
- Incorrectly negated conditions. The opposite of “a > 0 and b > 0” is “a ≤ 0 or b ≤ 0” (De Morgan’s laws).
10Self-assessment
Why is “stir until it browns” not an algorithmic step?
Because it violates definiteness: it does not say how to decide that it has browned. It does not guarantee finiteness either.
What are the three control structures of Böhm and Jacopini?
Sequence, selection and iteration.
What is the difference between While and Repeat … until?
While evaluates the condition first and may never execute the body; Repeat evaluates afterward and executes it at least once.
Do the desk check of Euclid’s algorithm with a = 48 and b = 18.
(48, 18) → r = 12 → (18, 12) → r = 6 → (12, 6) → r = 0 → (6, 0). Result: 6.
What is the maximum number of comparisons a binary search makes in 4096 sorted elements?
⌊log2 4096⌋ + 1 = 12 + 1 = 13.
What is a loop invariant?
A property that is true before entering the loop and holds after every iteration. On exit, together with the exit condition, it proves that the result is correct.
11Further reading
- Luis Joyanes Aguilar. Fundamentos de programación. Algoritmos, estructura de datos y objetos. 4th ed., McGraw-Hill, 2008 (in Spanish). The reference text in Spanish for pseudocode, flowcharts and Nassi-Shneiderman diagrams.
- George Pólya. How to Solve It. 1945. Spanish edition: Trillas (Cómo plantear y resolver problemas). Short and still relevant: the four-phase method with dozens of examples.
- Niklaus Wirth. Algorithms + Data Structures = Programs. Spanish edition (“Algoritmos + estructuras de datos = programas”), Ediciones del Castillo, 1980. By the creator of Pascal and of stepwise refinement. The title is a whole declaration.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. Introduction to Algorithms. 4th ed., MIT Press, 2022. For when you want to get serious about invariants, correctness and efficiency analysis.