Algorithms

1. Unrolling a recurrence

Learning goal: Solve a divide-and-conquer recurrence by counting levels and work per level.

A divide-and-conquer algorithm splits a problem, solves the parts, and combines the answers. Its running time satisfies a recurrence such as T(n) = 2T(n/2) + n. To solve it, unroll: level 0 costs n, level 1 has two subproblems of size n/2 costing n/2 each (n again), and so on.

For n a power of two with T(1) = 1, there are log2 n levels of splitting, each costing n, plus n leaves each costing 1. So T(n) = n log2 n + n. Check: T(2) = 4, T(4) = 12 and T(8) = 32. The common slip is to count n levels instead of log2 n.

Practice with a second recurrence: T(n) = T(n/2) + 1, which models binary search. Unrolling gives one unit per level and log2 n levels, plus the base case, so T(n) = log2 n + 1 when T(1) = 1. Check T(8) = 4. A good habit is to verify any closed form on two or three small inputs before trusting it, and to state the assumption that n is a power of two, since other values need floors and ceilings.

Worked example

Solve T(1) = 1, T(n) = 2T(n/2) + n for n = 8 by unrolling.

1. Level 0 cost: 8. Level 1: two subproblems of size 4, each costing 4: total 8.
2. Level 2: four subproblems of size 2, each costing 2: total 8.
3. Leaves: eight subproblems of size 1, each costing 1: total 8.
4. Sum: 8 + 8 + 8 + 8 = 32.

Mental model: Count levels, then the work at each level.

Common trap: Counting n levels instead of log n.

2. Which part of the tree is heavy

Learning goal: Compare combine cost with leaf cost to read off a recurrence.

For T(n) = a T(n/b) + f(n), the leaves of the recursion tree number about n^(log_b a). If f(n) is polynomially smaller than that, the leaves dominate and T(n) = Theta(n^(log_b a)). If f(n) is polynomially larger (with a regularity condition), the root dominates. If they are the same order, every level contributes and a log factor appears.

This is the master theorem in words. It only applies to recurrences of that exact shape. For T(n) = 7T(n/2) + n^2 we have log2 7 ≈ 2.80735, larger than 2, so the leaves dominate and T(n) = Theta(n^(log2 7)).

Now one where the root wins: T(n) = 2T(n/2) + n^2. Here log2 2 = 1 is smaller than 2, so f(n) = n^2 is polynomially larger. The regularity condition holds because 2 x (n/2)^2 = n^2 / 2 is at most a constant below 1 times n^2, so T(n) = Theta(n^2). If the recurrence is T(n) = 2T(n/2) + n log n, the master theorem does not apply cleanly, because the gap is only a log factor, so use the extended case or unroll the tree.

Worked example

Classify T(n) = 4T(n/2) + n using the heavy-part idea.

1. a = 4 and b = 2, so log2 4 = 2 and the leaves number about n^2.
2. The combine cost f(n) = n is polynomially smaller than n^2.
3. Leaves dominate.
4. T(n) = Theta(n^2).

Mental model: Compare the combine cost with the number of leaves.

Common trap: Applying the theorem to a recurrence of another shape.

3. Designing the state

Learning goal: Define a dynamic-programming state, transition and base case for knapsack.

Dynamic programming works when the problem has overlapping subproblems and optimal substructure. The design task is to choose a state that captures everything the future needs. For 0/1 knapsack the state is (i, c): the best value using the first i items with capacity c.

The transition says: either skip item i, giving D[i-1][c], or take it if it fits, giving value_i + D[i-1][c - weight_i]. The base row is 0. For items (weight, value) = (2,3), (3,5), (4,6) and capacity 5, the best value is 8, from items 1 and 2.

Fill the table to see the pattern. Items (2,3), (3,5), (4,6), capacity 5. After item 1: capacities 0 and 1 hold 0, capacities 2 to 5 hold 3. After item 2: capacity 2 holds 3, capacity 3 holds 5, capacity 4 holds 5 and capacity 5 holds 8. After item 3: capacity 4 improves to 6 and capacity 5 stays at 8. The answer is read at row n and column W. To recover which items were taken, walk backward from that cell and note where the value changed.

Worked example

Fill the knapsack table for items (weight, value) = (2,3), (3,5), (4,6) and capacity 5 and read the answer.

1. Define D[i][c] and set row 0 to all zeros.
2. After item 1 (2,3): capacities 2 to 5 get 3.
3. After item 2 (3,5): c = 3 gives 5; c = 5 gives max(3, 5 + D[1][2] = 8) = 8.
4. After item 3 (4,6): c = 4 gives 6, c = 5 stays 8. The answer is D[3][5] = 8.

Mental model: Pick a state that holds all the information the future needs.

Common trap: A state that forgets the remaining capacity.

4. Loop direction is a modeling choice

Learning goal: See how iteration order in a 1D table changes the problem being solved.

Many knapsack solutions keep only one row of the table and update it in place. The direction of the capacity loop matters. Iterating c downward reads values from before item i was considered, so each item is used at most once. Iterating c upward reads values that may already include item i, so an item can be reused.

That is not a bug in one case and a feature in the other: the downward loop solves 0/1 knapsack and the upward loop solves unbounded knapsack. State which problem you intend, and choose the loop to match.

Test the direction on one item of weight 2 and value 3 with capacity 4. The downward loop gives 3, because the item is used once. The upward loop gives 6, because after filling capacity 2 the loop reads that value at capacity 4 and adds the item again. That is a quick way to debug: if your answer for a 0/1 problem looks too large, check whether the loop runs upward.

Worked example

One item has weight 2 and value 3; capacity is 4. Compare an in-place ascending loop with a descending loop.

1. Start with D = [0,0,0,0,0] for c = 0..4.
2. Ascending: c = 2 gives 3; c = 3 gives 3; c = 4 gives 3 + D[2] = 6 because D[2] already includes the item.
3. Descending: c = 4 reads D[2] = 0 (not yet updated), giving 3; c = 3 gives 3; c = 2 gives 3.
4. Ascending yields 6 (unbounded), descending yields 3 (0/1).

Mental model: The loop direction states which problem you solve.

Common trap: Using the ascending loop for a once-only problem.

5. When greedy lies

Learning goal: Test a greedy rule with an exchange argument or a counterexample.

A greedy algorithm takes the locally best choice at each step. It is correct only if you can prove it, usually by an exchange argument: any optimal solution can be changed to include the greedy choice without getting worse. If you cannot find such a proof, try small cases that break it.

Taking the largest coin first is optimal for some coin systems but not all. With coins {1, 3, 4} and amount 6, greedy takes 4 + 1 + 1 (three coins), while 3 + 3 uses two. When greedy fails, dynamic programming over amounts solves the problem exactly.

Greedy also works for some scheduling problems. For interval scheduling, choose the interval that finishes first, discard those that overlap, and repeat; an exchange argument proves it optimal. Choosing the earliest start fails: with intervals A = (0, 10), B = (1, 3) and C = (4, 6), earliest start takes A alone, while B and C together give two. The choice of greedy criterion is the algorithm, so test it on a counterexample before you trust it.

Worked example

Show that largest-coin-first fails for coins {1, 3, 4} and amount 6, and find the optimal count.

1. Greedy takes 4 (remaining 2), then 1, then 1: three coins.
2. Try 3 + 3: two coins.
3. Two is below three, so greedy is not optimal.
4. DP agrees: D[6] = 1 + min(D[5], D[3], D[2]) = 1 + min(2, 1, 2) = 2.

Mental model: Prove greedy with an exchange argument or break it with a small case.

Common trap: Trusting a rule because it works on examples.

6. Dijkstra's hidden assumption

Learning goal: Know when a shortest-path algorithm is valid.

Dijkstra's algorithm repeatedly finalizes the unfinished vertex with the smallest known distance. The reason that is safe is that all edge weights are nonnegative, so a longer path can never become shorter by adding more edges. A negative edge breaks that argument.

With edges s to a of weight 2, s to b of weight 3 and b to a of weight -4, Dijkstra finalizes a at 2 first. The path through b has length 3 - 4 = -1, which is shorter, but a is already finalized. Bellman-Ford handles negative edges (without negative cycles) by relaxing all edges repeatedly.

Check the running time. With a binary heap, Dijkstra runs in about (V + E) log V time, while Bellman-Ford runs in V x E time but handles negative edges. For a graph with 1,000 vertices and 5,000 edges, that is roughly 6,000 x 10 = 60,000 steps for Dijkstra against 5,000,000 for Bellman-Ford. If all weights are nonnegative, use Dijkstra. If a negative cycle is reachable, shortest paths are not defined, and Bellman-Ford detects this on an extra pass.

Worked example

Run Dijkstra by hand on s to a (2), s to b (3), b to a (-4) and compare with the true shortest distance to a.

1. Start: dist(s) = 0. Relax: a = 2, b = 3.
2. Smallest unfinished is a (2), so finalize a at 2.
3. Then finalize b at 3 and relax b to a: 3 - 4 = -1, but a is already final.
4. Dijkstra reports 2; the true shortest distance is -1.

Mental model: Greedy finalization needs nonnegative weights.

Common trap: Using Dijkstra when negative edges exist.

7. The cheapest connection

Learning goal: Use the cut property or Kruskal's algorithm to build a minimum spanning tree.

A spanning tree connects all vertices with no cycle. A minimum spanning tree has the smallest total weight. Kruskal's algorithm sorts edges by weight and adds each edge unless it would form a cycle. Correctness comes from the cut property: the lightest edge crossing any cut belongs to some minimum spanning tree.

For edges AB 1, BC 2, AC 3, CD 4, BD 5: add AB (1), add BC (2), skip AC (it would close the cycle A, B, C), add CD (4), skip BD. The total is 1 + 2 + 4 = 7. A tree on n vertices has exactly n - 1 edges, which is a quick check.

Prim's algorithm grows one tree by adding the cheapest edge leaving it, and it also relies on the cut property. Kruskal's needs a union-find structure to check cycles quickly, and its time is dominated by sorting, about E log E. If all weights are distinct the minimum spanning tree is unique. If weights tie, several trees can have the same total, so a test that compares trees edge by edge can fail even when both answers are correct. Compare total weight instead.

Worked example

Find the MST weight for edges AB 1, BC 2, AC 3, CD 4, BD 5 by Kruskal.

1. Sort: AB 1, BC 2, AC 3, CD 4, BD 5.
2. AB and BC are accepted; AC would form a cycle, so it is skipped.
3. CD connects D, so it is accepted; BD is skipped.
4. Total = 1 + 2 + 4 = 7, using 3 edges = n - 1.

Mental model: Sort, add, and skip anything that forms a cycle.

Common trap: Adding the lightest edges without a cycle check.

8. Reductions point at the hard problem

Learning goal: Use polynomial reductions in the right direction.

A polynomial-time reduction from A to B turns any instance of A into an instance of B so that the answers match. If B can be solved quickly then so can A. To prove a new problem B is NP-hard, reduce a known NP-hard problem A to B. The reverse proves nothing about B's hardness.

Vertex cover and independent set are linked by complements: in a graph with n vertices, a set S is an independent set if and only if the remaining vertices form a vertex cover. So a graph has an independent set of size k exactly when it has a vertex cover of size n - k. For n = 10 and a maximum independent set of 4, the minimum vertex cover is 6.

Distinguish the classes. A problem is in NP if a proposed solution can be checked in polynomial time. For vertex cover, given a set of k vertices, check every edge has an endpoint in the set, which takes time proportional to the number of edges. A problem is NP-complete if it is both in NP and NP-hard. A common error is to reduce in the wrong direction: reducing B to a known hard problem only shows that B is no harder than that problem.

Worked example

A graph has 10 vertices and its largest independent set has 4 vertices. What is the smallest vertex cover?

1. A set S is independent exactly when V minus S is a vertex cover.
2. So covers of size n - k correspond to independent sets of size k.
3. A largest independent set of 4 gives a smallest cover of 10 - 4.
4. The minimum vertex cover has 6 vertices.

Mental model: Reduce from known-hard to new, and check the instance mapping.

Common trap: Reversing the reduction.

9. Polynomial in the number, not the bits

Learning goal: Separate pseudo-polynomial time from true polynomial time.

The knapsack DP fills an n by (W + 1) table, so its time is about n W. That is polynomial in the number W itself, but the input only writes W in about log2 W bits. In terms of input length the running time is exponential. Such algorithms are called pseudo-polynomial.

If W is written with 20 bits, W can be up to 2^20 - 1 = 1,048,575, and with n = 10 items the table has 10 x 1,048,576 = 10,485,760 cells. Adding one bit to W doubles the table. For small W the algorithm is fast, which is why the distinction matters in practice.

Compare subset sum with sorting. Subset sum by dynamic programming takes about n x T steps for target T, which is pseudo-polynomial. If T is written in unary the input length is T, so the same algorithm is polynomial in input size. This shows why the encoding matters. For n = 30 and T = 10^9 the table has 3 x 10^10 cells, which is not practical, even though the formula looks polynomial.

Worked example

A knapsack instance has n = 10 items and capacity W written in 20 bits (largest value 2^20 - 1). Estimate the table size and say what it shows about running time.

1. The largest W is 2^20 - 1 = 1,048,575.
2. The table has n x (W + 1) cells = 10 x 1,048,576.
3. That is 10,485,760 cells.
4. Doubling W with one extra bit doubles the cells, so time is exponential in the bit length.

Mental model: Measure running time against the number of bits, not the numeric value.

Common trap: Calling nW polynomial in the input length.

10. Cheap on average, costly sometimes

Learning goal: Use amortized analysis to bound a sequence of operations.

Amortized analysis bounds the total cost of a sequence of operations, and divides by the count. A dynamic array that doubles when full has some appends that copy the whole array, but those are rare. Starting at capacity 1, appends 2, 3 and 5 trigger copies of 1, 2 and 4 elements.

Counting one unit per write and one per copied element, 8 appends cost 8 + (1 + 2 + 4) = 15. In general the copies sum to less than 2n, so n appends cost less than 3n and the amortized cost per append is a constant. The worst single append still costs about n.

A second example is a binary counter. Incrementing from 0 up to n flips the lowest bit every time, the next bit every second time, and so on, so total flips are n + n/2 + n/4 + ... which is less than 2n. For n = 8 the flips are 8 + 4 + 2 + 1 = 15, below 16. Amortized cost per increment is under 2, though a single increment from 0111 to 1000 flips four bits. The accounting method assigns each flip a credit paid in advance.

Worked example

A dynamic array starts with capacity 1 and doubles when full. Count one unit per write and one per element copied. Find the total cost of 8 appends.

1. Capacity 1: append 1 costs 1 (no copy).
2. Append 2: full, copy 1, write 1: cost 2. Capacity 2.
3. Append 3: copy 2, write 1: cost 3. Capacity 4. Append 4: cost 1.
4. Append 5: copy 4, write 1: cost 5. Appends 6 to 8: cost 3. Total 1 + 2 + 3 + 1 + 5 + 3 = 15.

Mental model: Add up a whole sequence, then divide.

Common trap: Using the worst single operation for every operation.

11. Reading the recursion tree with numbers

Learning goal: Use level counts to see which part of a divide-and-conquer tree carries the work.

For T(n) = a T(n/b) + n^d with n = b^k, there are k levels of splitting. Level i has a^i subproblems of size n / b^i, and each costs (n / b^i)^d, so level i costs n^d x (a / b^d)^i. The ratio q = a / b^d decides everything.

If q is above 1, the cost per level grows as you go down, so the leaves, which number a^k, carry the work. If q equals 1, every level costs the same and the total is k times n^d, which gives a log factor. If q is below 1, the cost shrinks per level and the root dominates.

For example a = 2, b = 2, d = 1 gives q = 1, which is merge sort and has n log n cost. With a = 4, b = 2, d = 1 we get q = 2, so the leaves dominate and cost n^2. With a = 2, b = 2, d = 2 we get q = 1/2 so the root dominates and the cost is n^2 as well.

Use this view to check a master-theorem answer. Compute the level costs for a small k and verify that the pattern matches the case you chose.

Worked example

For T(n) = 4T(n/2) + n, what is the ratio q = a / b^d?

1. a = 4, b = 2, d = 1.
2. b^d = 2.
3. q = 4 / 2.
4. q = 2, so the leaves dominate.

Mental model: Level i costs n^d x q^i with q = a / b^d. The ratio picks leaves, balanced or root.

Common trap: Using the master theorem when the recurrence has a different shape.

12. Max flow and min cut

Learning goal: Compute a maximum flow by finding the smallest cut in a small network.

A flow network has edges with capacities. A flow sends units from the source s to the sink t without exceeding any capacity and without losing units at inner vertices. The max-flow problem asks for the largest total that can reach t.

A cut splits the vertices into a set containing s and a set containing t. Its capacity is the sum of capacities of edges that go from the s side to the t side. Any flow must pass through every cut, so the value of any flow is at most the capacity of every cut.

The max-flow min-cut theorem says the maximum flow equals the minimum cut capacity. The Ford-Fulkerson method finds flow by repeatedly finding a path with spare capacity in the residual graph and pushing along it. With integer capacities each augmentation adds at least one unit, so the number of steps is bounded by the flow value.

To check an answer, find a flow and a cut with the same value. If they match, both are optimal, and that pair is a certificate of correctness.

Worked example

In the network above the cut {s} has capacity 3 + 2. What is it?

1. Edges leaving s: s to a and s to b.
2. 3 + 2.
3. = 5.
4. A cut gives an upper bound of 5.

Mental model: Max flow equals min cut. A matching flow and cut prove both optimal.

Common trap: Counting edges that go back into the s side.

13. Hashing and the expected number of collisions

Learning goal: Use expectation to size a hash table without simulating it.

A hash table places each key in one of m slots by applying a hash function. Under the simple model of uniform hashing, every key lands in each slot with equal probability, independently of other keys. Real hash functions only approximate this.

Two keys collide if they land in the same slot, which has probability 1/m. With n keys there are n(n - 1) / 2 pairs, so by linearity of expectation the expected number of colliding pairs is n(n - 1) / (2m). That is the birthday argument in numbers.

The load factor n / m is the average chain length when collisions are resolved by chaining. A successful search examines about 1 + n / (2m) entries on average under the uniform model. Doubling the table when the load factor passes a limit keeps the cost constant on average, which connects to the amortized analysis earlier.

Randomized algorithms use the same tool: expectation is easy to compute even when the distribution is complicated. State the model, compute the expectation, and say what the model leaves out.

Worked example

n = 10 keys, m = 100 slots. Expected colliding pairs?

1. Pairs: 10 x 9 / 2 = 45.
2. Each collides with probability 1/100.
3. 45 / 100.
4. 0.45.

Mental model: Expected colliding pairs = n(n - 1) / (2m). The load factor n / m sets chain length.

Common trap: Assuming the uniform model holds for adversarial keys.