Design & Analysis of Algorithms
Why one way of solving a problem finishes in a second and another would outlast the universe.
AI tutor is turned off for this class
Use the CS161 lectures, notes, and assignments below to keep learning.
Big Idea
How Computing Works
Grade bands
K-2 · 3-5 · 6-8 · 9-12
AI literacy pillar
How AI works · Ethics
Lesson overview
Why one way of solving a problem finishes in a second and another would outlast the universe. This module climbs from an everyday intuition to the real mechanism, then names the Stanford course it descends from.
Teacher script · ~45 min
- 0–5
Hook
To find a name in a phone book, you don't read page 1 to the end; you open the middle and halve the problem each time. With a million names, reading start-to-finish takes a million steps; halving takes about twenty. Algorithms is the study of finding the twenty-step way.
- 5–15
Explore
Students do the activity in pairs: Sort five playing cards two ways: check every pair vs insert each into place. Count comparisons. The gap explodes as you add cards.
- 15–30
Explain
Many problems hide repeated sub-problems. Dynamic programming solves each small piece once, stores it, and reuses it, turning impossible exponential blowups into fast solutions. Greedy algorithms instead grab the best-looking local choice and (sometimes provably) reach the global best. Knowing which strategy fits is the craft.
- 30–40
Connect to the summit
Show students this is the real thing professionals build: CS161, the real thing. Why one way of solving a problem finishes in a second and another would outlast the universe.
- 40–45
Check
Run the formative check below. Anyone who can explain a key term in their own words has it.
Student activity
Sort five playing cards two ways: check every pair vs insert each into place. Count comparisons. The gap explodes as you add cards.
Slides
Formative check
- 1.In your own words, what is "Big-O notation"? (Looking for: A way to describe how an algorithm's work grows as the input grows.)
- 2.In your own words, what is "Divide and conquer"? (Looking for: Break a problem into smaller copies, solve those, and combine.)
- 3.In your own words, what is "Dynamic programming"? (Looking for: Solve overlapping sub-problems once and reuse the answers.)
Carry-away concepts
- Big-O notation
- A way to describe how an algorithm's work grows as the input grows.
- Divide and conquer
- Break a problem into smaller copies, solve those, and combine.
- Dynamic programming
- Solve overlapping sub-problems once and reuse the answers.
- NP-completeness
- A class of problems for which no known algorithm is fast on all inputs.
From the summit · the Stanford source
You design algorithms (divide-and-conquer, greedy, dynamic programming, graphs) and prove their correctness and running time rigorously.
This module descends from CS161 at Stanford. Students who climb the full ladder arrive here.