Recitation 5: Dynamic Programming

What this lecture covers

This recitation is a problem-solving session rather than a formal lecture. It opens by restating the core idea of dynamic programming, splitting a problem into subproblems and reusing solved results, then works through a sequence of examples of increasing difficulty: counting grid paths, making change with coins, and stacking rectangular blocks by height. Partway through, the class votes to spend the second half reviewing universal and perfect hashing from the previous lecture, since several students found it difficult.

After watching, you should be able to set up a dynamic programming recurrence for a new problem by asking two questions: how many distinct subproblems exist, and how much work is needed to combine each subproblem's results, and you should be able to walk through the collision-probability argument for a universal hash family and the two-level construction used for perfect hashing.

Key ideas

• DP runtime analysis pattern: for any DP solution, multiply the number of unique subproblems by the work needed to merge each subproblem's results.
• Grid-path warm-up: the number of distinct paths to a grid cell is the sum of the counts from the cell to its left and the cell below, giving O(mn) subproblems each solved in constant time.
• Coin change (make change): minimizing coins for value n looks polynomial in n and the number of coin types, but because the input size is O(log n) bits, this runtime is actually exponential in the input size, which is why it does not contradict NP-completeness of the related knapsack problem.
• Rectangular block stacking: define a subproblem as the best height achievable using only blocks compatible with (smaller in both length and width than) the current base block; sorting blocks first, then deciding whether the largest remaining block is the base or is skipped, cuts the subproblem count to O(n).
• Universal hash family (recap): a family of hash functions from which one is drawn uniformly at random so that any two distinct keys collide with probability at most 1/m; needed because any single deterministic hash function has a worst-case input, by a pigeonhole argument, when the universe of keys is much larger than the table.
• Concrete universal family: h(k) = ((a*k + b) mod p) mod m, with p prime and larger than the universe; the recitation redoes the collision-probability bound using modular inverses to show it is at most 1/m.
• Perfect hashing via table squaring: choosing a table size of n^2 for a universal hash function makes the probability of zero collisions among n keys exceed one half (a union bound over all pairs), giving a Las Vegas algorithm that succeeds with high probability after O(log n) retries.
• Two-level perfect hashing: to bring space down from O(n^2) to O(n), hash keys once into n bins, then build a second-level perfect hash table of size proportional to the square of each bin's occupancy; Markov's inequality bounds the total second-level space.

Walkthrough

Grid paths as a first DP example (1:01)

A robot moves from grid coordinate (1,1) to (m,n), taking only up or right steps. The number of distinct paths to any cell is the sum of the paths to the cell on its left and the cell below. This gives O(mn) subproblems, each combined in constant time, for an overall O(mn) runtime, illustrating the general DP pattern of counting subproblems and per-step merge cost.

Make change and a digression on P vs NP (5:17)

Given coin denominations including a 1-cent coin (to guarantee solvability) and a target value n, the goal is the minimum number of coins to make change. The naive recursive solution tries each coin, recursing on the remainder, giving at most n distinct subproblems and O(m) work per subproblem (where m is the number of coin types), for O(nm) total. The recitation pauses to note this resembles knapsack, an NP-complete problem, and resolves the apparent contradiction: the input n only takes O(log n) bits to represent, so a runtime of O(n) is actually exponential in the input size, not polynomial.

Stacking rectangular blocks (14:41)

Given blocks with length, width and height (no rotation allowed), the task is to stack blocks so each one is strictly smaller in both length and width than the block below it, maximizing total height. A naive subproblem definition, based on an arbitrary compatible set of remaining blocks, could blow up combinatorially. The fix, echoing the earlier weighted interval scheduling recitation, is to sort blocks by length (then width) and define the subproblem as a suffix of the sorted list: either the largest remaining block is used as the current base, or it is skipped entirely. This bounds the subproblems to O(n) and, with an O(n log n) sort and a claimed but unverified O(n log n) method for finding compatible sets, gives an O(n log n) overall algorithm (naive compatible-set lookups would cost O(n^2)).

Revisiting universal hashing (33:45)

The class votes to review hashing. The setup: n keys drawn from a universe of size u, hashed into m bins. A deterministic hash function always has a worst-case input set that collides entirely, by a pigeonhole argument, when u is larger than m^2. Since the hash function itself must stay deterministic once chosen (so lookups are consistent), the fix is to pick a hash function uniformly at random from a universal family, so an attacker who does not know the chosen function cannot construct a guaranteed-bad input. A universal family guarantees any two distinct keys collide with probability at most 1/m.

A concrete universal family and perfect hashing (39:57)

The recitation re-derives the collision bound for h(k) = ((a*k + b) mod p) mod m, with p prime and larger than the universe, showing algebraically that the number of "bad" choices of a that cause a given pair of keys to collide is at most 1/m of all valid choices. It then builds toward perfect hashing: first a simple method using table size n^2, which succeeds with probability greater than one half per attempt (via a union bound over all key pairs), giving a Las Vegas algorithm with failure probability that shrinks exponentially in the number of retries, but at the cost of quadratic space. The two-level fix hashes keys into n bins with a first-level universal function, then builds a second-level perfect hash table sized at the square of each bin's key count; Markov's inequality shows the total space stays O(n) with probability greater than one half, so retrying the first-level hash function a logarithmic number of times achieves both linear space and zero collisions.

Before you watch

• Watch or review the lecture on divide and conquer or greedy algorithms that introduced weighted interval scheduling, since the block-stacking solution reuses its "sort, then include-or-exclude the extreme element" idea.
• Review the prior lecture on universal and perfect hashing, since the second half of this session assumes familiarity with hash tables, load factors, and the definitions being re-explained.
• Be comfortable with basic probability tools: union bound, indicator variables, and Markov's inequality.

Check your understanding

1. For the grid-path and make-change problems, identify the number of subproblems and the per-subproblem merge cost, and explain how they combine into the overall runtime.
2. Why does the naive make-change algorithm not imply P = NP, even though it looks like a polynomial-time solution to a knapsack-like problem?
3. Why does defining block-stacking subproblems as arbitrary compatible sets fail to bound the subproblem count, and how does sorting fix this?
4. Explain why no deterministic hash function can avoid a worst-case input when the key universe is much larger than the hash table.
5. Why does squaring the table size make a universal hash function likely to have zero collisions, and why is a second level of hashing needed to keep the space linear?