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.
Lesson overview
Why one way of solving a problem finishes in a second and another would outlast the universe.
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.
- 30–40
Connect to the summit
Read aloud the "From the summit" section below. Ask students which ideas from today they recognize in it.
- 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 is based on a Stanford course.