Last content day of the semester. Put Unit 4 on the map, drill the three-way sort until it’s automatic, and take a System Check shaped like the final.
Big Idea 3 — Algorithms & ProgrammingReview — Units 0–4
Before this lesson
No new reading. Everything here is from 4.1–4.12, plus the System Check reaching
back to Unit 0. A term that feels fuzzy below is tonight’s study target.
The whole unit lived in the Algorithms region of Programs — the bridge back to Bits: how much work the machine does, and where it hits a wall. Today is also the last content day before the semester final, so the review reaches back through every unit so far.
2
The Point of Today
Can you say the unit in one breath?
“Algorithms can be compared by counting steps; some problems are efficient, some are solvable but
unreasonably slow, and some can’t be solved at all — and simulations let us study what we
can’t test.” If one piece of that sentence is fuzzy, you just found tonight’s study
target.
As always: retrieval, not re-reading. Produce the answer, then
check.
3
The Unit 4 Map — four regions
Cover the right column and define each term before you peek.
linear (sequential) search, binary search, sorted, precondition, worst case, efficiency
Limits (4.6–4.9)
algorithmic efficiency, linear & quadratic growth, reasonable time, unreasonable time, heuristic, approximate solution, optimization problem, decidable, undecidable, halting problem
Simulation (4.10–4.12)
simulation, model, random values, trials, abstraction
The unit’s spine is one three-way sort. Every problem is one of:
E — solvable efficiently (reasonable time) ·
U — solvable, but only in unreasonable time ·
N — not solvable: no algorithm exists (undecidable).
“It’s a huge input” doesn’t make it U, and “it takes forever” never makes it N.
4
The Three-Way Sort
The single most valuable review activity of the unit. File each problem. Wrong files explain themselves.
5
Vocabulary Rapid-Fire
The eight terms most likely to show up. Say the definition out loud, then check.
linear search Programs
Check each element in order until found or the list ends. Works on any list. Worst case: n checks.
binary search Programs
Check the middle of a sorted list, discard the half that can’t hold the target, repeat.
precondition Programs
What must be true before an algorithm works. Binary search: the data is sorted.
worst case Programs
The most steps an algorithm can be forced to take on inputs of a given size.
reasonable time Programs
Step count grows like a polynomial (n, n², n³) or slower.
heuristic Programs
A fast approach that finds a good-enough answer, without guaranteeing the best.
undecidable problem Programs
No algorithm can be built that always gives a correct yes-or-no answer.
simulation Programs
A simplified model of a real process, usually with random values, run many times.
6
Semester System Check
Ten questions from Units 0–4, weighted the way the semester final is: mostly programs and
algorithms, with data and bits mixed in. Trace on paper.
0 of 10 answered
7
Connections
Pulls together 4.1–4.12 — any card you misfiled above names the lesson to reopen:
4.7 for U, 4.9 for N.
Next in 4.14 — the Unit 4 test. Tomorrow’s page has the breakdown and a
practice set.
Then the semester final — Units 0–4. The System Check above is its shape.
Opens Unit 5 — your simulation’s trial results were a dataset. Next semester you
learn what to do with one.