Section 4 of 5 · Algorithms & Data Structures
Decomposition, Greedy Methods & Randomness
Hard problems often become manageable by exposing recursive state, proving a local choice, or accepting a controlled probability. Each shortcut needs a proof boundary and an adversarial test.
6 units 17 topics 0/6
Units
6 in this section
- 4.1 Recursion contracts, backtracking and sound pruning implement4 h
- 4.2 Divide and conquer, recurrences and partition-based selection derive · implement5 h
- 4.3 Greedy choice, optimal substructure and exchange arguments derive4 h
- 4.4 Greedy counterexamples and interval scheduling derive · implement4 h
- 4.5 Randomized correctness, expected cost and selection derive · implement4 h
- 4.6 Reservoir sampling, unbiased shuffling and empirical checks implement · measure4 h
Before moving on
Checkpoint
Prove or refute one unseen greedy rule before coding, implement a pruned search with a sound bound, and empirically verify one randomized guarantee with fixed seeds.
Deliberately out of scope
Leave for later
- Advanced approximation schemes
- Randomized linear algebra
- Competitive analysis beyond representative examples
Resources for this section
Shared by every unit above
- DSA Handbook - recursion, backtracking and greedy Study Part 7, Part 10 and the relevant foundations on recursion and probability. Write the state definition or greedy claim before opening code.
- AlgoMaster DSA - decomposition and greedy slice Attempt N-Queens and Gas Station cold, then implement reservoir sampling and test its output distribution over fixed-seed trials. Add another judged problem only for a diagnosed weakness.
- Algorithms - recursion, backtracking and greedy Use the recursion, backtracking, divide-and-conquer and greedy chapters for recurrence derivations, proof templates and counterexamples.
- MIT 6.042J - probability and randomized algorithms Use the probability, expectation and concentration readings to derive sampling probabilities and distinguish expected from high-probability guarantees.
- Algorithms lecture notes - randomized algorithms Use note 1 Discrete Probability, note 2 Nuts and Bolts (randomized quicksort, with QuickSelect in its exercises), note 4 Tail Inequalities and note 5 Hashing to derive expected costs, separate expected from high-probability guarantees, and analyze hashing behavior.
Apply the section
Mini-project · A proved greedy, a pruned search and a sampler check (8 to 12 h)
Prove one greedy rule and refute a tempting alternative before coding. Implement a backtracking search whose prunes are each sound, and verify a weighted sampler with a statistical test over seeds you choose.
Steps
- State the LC 1029 Two City Scheduling rule, sorting by the difference between the two costs and sending the first half to one city, and prove it with an exchange argument before coding.
- Refute the alternative that sends each person to their cheaper city until one city fills, searching over all splits with brute force. Keep the minimized counterexample and name the information the refuted order ignores.
- Solve LC 698 Partition to \(K\) Equal Sum Subsets by backtracking over buckets, stating each prune as a claim: order, early failure and skipping an equivalent bucket. Prove the skip sound by symmetry.
- Differential-test the pruned search against the unpruned one on small random inputs, recording how each prune changes the node count. Then drop the bucket backtracking for a first-fit variant and let the test find a counterexample.
- Solve LC 528 Random Pick with Weight with prefix sums and a binary search. Check the distribution with a chi-square test against the weights, keeping the check as a pytest over seeds you choose.
- Plant the off-by-one in the index mapping and show the test catches it, with counts shifting onto an index that should never appear. Keep the pytest passing on the correct sampler and failing on the planted one.
Deliverables
- The LC 1029 exchange proof with the refuted rule and its counterexample.
- The LC 698 pruned search with soundness claims, node counts and the caught unsound variant.
- The LC 528 sampler with its chi-square test and the planted off-by-one.
Checks
- rubric · Self-grade with the rubric below
- external-tests · LeetCode 1029: Two City Scheduling
- external-tests · LeetCode 698: Partition to \(K\) Equal Sum Subsets
- external-tests · LeetCode 528: Random Pick with Weight
Rubric
| Criterion | Pass | Strong |
|---|---|---|
| Greedy proof | The exchange argument is written before code, LC 1029 is accepted, and the refuted rule has a minimized counterexample. | The proof handles ties, and the write-up explains what information the refuted order ignores. |
| Pruned search | Every prune has a one-line soundness claim, and the pruned and unpruned searches agree on random inputs. | Node counts per prune are recorded, and the differential test catches the first-fit variant. |
| Randomized check | The chi-square test states its seeds, trials and decision rule, and the planted off-by-one fails it. | The pytest passes across the chosen seeds on the correct sampler and fails on the planted one for every seed. |
Feeds into: Capstone failure evidence: the refuted greedy, the first-fit variant and the off-by-one sampler. Transfer: LC 1029 solved cold with its proof.