Unit 20: Divide and Conquer, Greedy, and Dynamic Programming
Three ways to attack a hard problem: break it in half, grab the best choice available now, or remember every subproblem you've already solved.
7 topics · 25 questions
Each topic is a path, not a menu: work down it in order and every question builds on the one above. Click any of them to watch the answer draw itself.
Divide and Conquer as a General Pattern
- How it worksHow does a divide-and-conquer algorithm break a problem into smaller pieces, solve each recursively, and merge the results?
- Worked exampleTrace how merge sort and binary search both follow the same split, solve, combine shape on an 8-element array.
- Ties togetherHow does divide and conquer's recursive splitting connect back to the recursion trees drawn for Fibonacci?
Your turn1 of 2
A divide-and-conquer algorithm splits a problem into 2 equal subproblems at each level, for 14 levels of splitting. How many total subproblems exist at the deepest level, given 2 to the power of k?Greedy Algorithms: The Locally Best Choice
- How it worksHow does a greedy algorithm commit to the best-looking choice at each step and never look back to reconsider it?
- Worked exampleTrace a greedy coin-change algorithm making 41 cents from quarters, dimes, nickels, and pennies.
- Common mistakeWhy doesn't a greedy algorithm ever revisit and undo a choice it already made?
Your turn1 of 2
A greedy coin-change algorithm makes 14 separate coin selections in a row to reach a target amount, never reconsidering an earlier choice. How many total coin selections does the algorithm make?When Greedy Fails
- How it worksHow does a coin system with a 25, a 10, and a 1 make greedy overshoot the fewest-coins answer for 30 cents?
- Worked exampleTrace greedy coin change for 30 cents using coins 25, 10, and 1, and compare it against the true minimum of three 10s.
- Going furtherWhat happens to greedy's reliability once the set of available coin denominations changes to 4, 3, and 1?
- Ties togetherHow does when-greedy-fails motivate reaching for dynamic programming on that same kind of problem?
Your turn1 of 2
A coin system offers denominations of 25, 10, and 1. For a target amount where greedy coin change overshoots, greedy uses 8 coins while the true minimum uses 2 coins. How many more coins does greedy use than the true minimum?Dynamic Programming: Overlapping Subproblems and Optimal Substructure
- How it worksHow does optimal substructure let a problem's best answer be built directly from the best answers to its smaller pieces?
- Worked exampleTrace how fib(5) and fib(4) both need fib(3), making it an overlapping subproblem worth caching.
- Ties togetherHow does dynamic programming's overlapping subproblems connect back to memoization on a recursion tree?
Your turn1 of 2
Computing fib(5) and fib(4) both require fib(3) as a subproblem. If a naive recursive computation solves fib(3) separately 15 times across the whole call tree, how many redundant recomputations of fib(3) does this represent, not counting the first?Filling a Dynamic Programming Table Cell by Cell
- How it worksHow does each cell in a DP table for climbing stairs get filled using only the two cells right before it?
- Worked exampleTrace filling a bottom-up DP table for the number of ways to climb a staircase of 6 steps taking 1 or 2 steps at a time.
- Going furtherWhat happens to the DP table once the staircase problem allows steps of 1, 2, or 3 at a time?
- Worked exampleTrace the same bottom-up DP table computing Fibonacci from F(0) through F(6).
- Ties togetherHow does a DP table's bottom-up fill order guarantee every subproblem it needs is already computed?
Your turn1 of 2
A bottom-up DP table for climbing a staircase of 70 steps, taking 1 or 2 steps at a time, fills one cell per step count from 0 through n. How many total cells does this DP table have?The 0/1 Knapsack Problem
- How it worksHow does a knapsack DP table decide, for each item, whether including it beats leaving it out at every weight limit?
- Worked exampleTrace filling the knapsack DP table for items weighing 2 and 3 worth 3 and 4, with a capacity of 5.
- Common mistakeWhy doesn't a greedy pick-the-most-valuable-item-first strategy always solve 0/1 knapsack correctly?
- Going furtherWhat changes about the knapsack DP table once an item's weight is larger than the knapsack's entire capacity?
Your turn1 of 2
A 0/1 knapsack DP table has one row per item and one column per weight capacity from 0 through 33. For 14 items, how many total cells does this table have?Top-Down Memoization Versus Bottom-Up Tabulation
- How it worksHow does top-down DP cache answers on the way down from the original problem while bottom-up builds up from the smallest subproblem?
- Worked exampleTrace computing fib(5) once with a top-down memoized recursive call and once with a bottom-up table filled left to right.
- Going furtherWhat changes about stack usage once a top-down memoized solution is rewritten as bottom-up tabulation?
Your turn1 of 2
A top-down memoized solution and a bottom-up tabulated solution both compute fib(70), and both compute each of the n plus 1 distinct subproblems from fib(0) through fib(n) exactly once. How many total subproblems does each approach compute?