Dynamic programming and optimization lesson plan
Solve a space mission's hard choices with tables on a Raspberry Pi: overlapping subproblems, coin change, knapsack, edit distance, greedy against DP, scheduling, and a route planner between stations.
Objectives and materials
By the end, students can
- Spot repeated work and replace it with a table filled bottom up.
- Pack a rocket and fix a garbled command, with the two most famous tables.
- When a quick choice is provably right, and when only a table will do.
- A route planner for ferries between space stations.
Materials for the whole unit
- Half breadboard
- LED x 2
- Pushbutton
- Raspberry Pi 4 Model B
- Resistor x 2
- Traffic light module
Every part is already on the simulator’s bench, so there is nothing to buy or hand out. The counts are the most any one lesson uses, if you build it on real breadboards too.
Think in tables
Spot repeated work and replace it with a table filled bottom up.
| Lesson | Time | What students do |
|---|---|---|
| Overlapping subproblemsA docking ladder climbed 1, 2 or 3 rungs at a time: see the same subproblem solved hundreds of times, memoize it, turn it into a table filled bottom up, and shrink the table to three numbers that climb 1000 rungs where recursion cannot. | 40 min |
|
| Coin changeThruster burns of fixed sizes: greedy picks three burns where two will do, a DP table finds the fewest, a pick table says which, a second DP counts every mix, and reachability shows which speeds can never be hit. | 40 min |
|
Materials
- Half breadboard
- LED x 2
- Raspberry Pi 4 Model B
- Resistor x 2
Check for understanding
Each student finishes "Coin change" on their own, without opening the hints. The simulator checks 5 of its 5 steps as they go.
Then ask each one to explain, in a sentence or two, the last thing it asked of them: "Speeds you can never hit".
The classics
Pack a rocket and fix a garbled command, with the two most famous tables.
| Lesson | Time | What students do |
|---|---|---|
| KnapsackPack a rocket's last 10 kg for the most science: brute force over 256 loads, the 0/1 knapsack table, reconstructing the load, the one-row version and the classic bug of looping the wrong way, then 30 crates that brute force could never try. | 40 min |
|
| Edit distanceGarbled commands from a probe: why counting mismatched positions fails, the Levenshtein table, printing it, walking it back into a list of edits, and a command line that answers "did you mean DEPLOY?" | 40 min |
|
Materials
- Half breadboard
- LED x 2
- Raspberry Pi 4 Model B
- Resistor x 2
Check for understanding
Each student finishes "Edit distance" on their own, without opening the hints. The simulator checks 5 of its 5 steps as they go.
Then ask each one to explain, in a sentence or two, the last thing it asked of them: "Did you mean?".
Greedy or DP
When a quick choice is provably right, and when only a table will do.
| Lesson | Time | What students do |
|---|---|---|
| Greedy vs DPWhen a quick greedy choice is provably right and when it fails: satellite passes by earliest end against shortest first, fuel tanks that can be split against ones that cannot, and a test that tells which coin systems greedy can handle. | 40 min |
|
| SchedulingWeighted interval scheduling: when passes carry different amounts of data, earliest end first loses 15 MB. A DP with bisect finds the best schedule, a walk back names it, the red LED tracks it in time, and a sweep line counts antennas. | 40 min |
|
Materials
- Half breadboard
- LED x 2
- Raspberry Pi 4 Model B
- Resistor x 2
Check for understanding
Each student finishes "Scheduling" on their own, without opening the hints. The simulator checks 5 of its 5 steps as they go.
Then ask each one to explain, in a sentence or two, the last thing it asked of them: "How many antennas for everything?".
Project
A route planner for ferries between space stations.
| Lesson | Time | What students do |
|---|---|---|
| Project: a route plannerThe project: a ferry route planner between space stations. Shortest times by DP in station order, the route walked back, the best route within a number of legs (Bellman-Ford rounds), and a planner on the traffic lights that takes a destination over serial. | 55 min |
|
Materials
- Pushbutton
- Raspberry Pi 4 Model B
- Traffic light module
Check for understanding
Each student finishes "Project: a route planner" on their own, without opening the hints. The simulator checks 7 of its 7 steps as they go.
Then ask each one to explain, in a sentence or two, the last thing it asked of them: "What you built".
Teach this unit as a class
Start a class from this course and its 7 lessons are assigned in one go, in order. Students join with a six-character code or printed login cards, and each one’s work comes back to you.
The class tools are free for 30 days for one class of up to 20 students, with no card. The lessons themselves are free either way.