Algorithms
| English | Chinese | Pinyin |
|---|---|---|
| algorithm | 算法 | suàn fǎ |
| flowchart | 流程图 | liú chéng tú |
| pseudocode | 伪代码 | wěi dài mǎ |
| tracing | 追踪 | zhuī zōng |
| binary search | 二分查找 | èr fēn chá zhǎo |
| efficiency | 效率 | xiào lǜ |
| linear search | 线性查找 | xiàn xìng chá zhǎo |
A recipe a machine could follow
- "Make it better" is not an algorithm. "Compare each pair and swap them if they are the wrong way round" is.
- An algorithm 算法 is a finite sequence of unambiguous steps that terminates.
- All three words are load-bearing: finite, unambiguous, and it must stop.
Which are required for a sequence of steps to be an algorithm? Choose all that apply.
Pseudocode and flowcharts are algorithms too. The language is not part of the definition.
Writing one down
- A flowchart 流程图 draws it: a diamond is a decision, a rectangle a process, an oval a start or end.
- Pseudocode 伪代码 writes it in structured English, and it is what most exam questions ask for.
- Neither is a programming language. They exist so a human can check the logic before a machine runs it.
Match each flowchart shape to what it means.
The shapes are standard, and using the wrong one is marked in this unit.
Tracing
- Tracing 追踪 is running an algorithm by hand: a table with one column per variable and one row per step.
- It is the marked technique in this unit, and it finds a bug without running anything.
- Write every variable's value at every step, including the ones that did not change.
Trace a binary search for 7 in [1, 3, 5, 7, 9, 11].
| Step | Range | Middle | Compare |
|---|---|---|---|
| 1 | 1…11 | 5 | 5 < 7, take the right half |
| 2 | 7…11 | 9 | 9 > 7, take the left half |
| 3 | 7 | 7 | found |
Three steps, and the table is the answer. Writing "found" without it shows nothing about how, which is what the question asks.
Linear against binary search
Halving beats checking one at a time, and the gap widens with the list.
Binary search for 7 in [1, 3, 5, 7, 9, 11]. How many comparisons does it take?
Middle 5, then middle 9, then 7. The trace table is what shows this.
Efficiency
- A linear search 线性查找 checks every item: a million items, up to a million steps.
- A binary search 二分查找 halves the list each time: a million items, twenty steps.
- Efficiency 效率 is about how the work grows with the size of the input, not about how fast the computer is.
- ⚠ Binary search needs a sorted list. On unsorted data it does not merely run slowly, it returns wrong answers.
A list has a million items. Roughly how many steps does a binary search need?
Each step halves the list, and 2²⁰ is just over a million.
A binary search works on an unsorted list, just more slowly.
It returns wrong answers. Halving only makes sense when order tells you which half to keep.
Trace before you judge. Most algorithm questions are answered by carefully executing three or four steps on paper. Students who reason about what the algorithm "should" do get it wrong more often than students who simply run it.