TCS Review

How to use this workbook

This workbook is designed for four intensive weekdays, a weekend break, and a complete review day before a hard algorithms exam. It aims at exam-level fluency: selecting an appropriate technique, proving correctness without hidden gaps, and performing the quantitative analysis cleanly. One week cannot replace the breadth accumulated during two years of doctoral study, but focused work can bring performance on these particular topics close to the standard expected in a graduate algorithms course or qualifying exam.

For each module:

  1. Read the explanation actively. Re-derive every displayed equation.
  2. Cover the worked solution and attempt the problem for five minutes.
  3. Do the easy problem immediately, the medium problem under a 15-minute timer, and the hard problem under a 45-minute timer.
  4. When time expires, mark the precise obstruction before consulting notes.
  5. Rewrite one solution using the proof template below.
CheckpointLemma 1
Claim. State exactly what is being proved.
Structure. Name the extremal object, exchange, state decomposition, dual certificate, or potential.
Validity. Prove that the transformation preserves the required constraints.
Progress. Explain what strictly improves or becomes smaller.
Conclusion. Connect the structural statement to the original claim.

The time labels measure the intended solution time after learning the material. A hard problem is successful even when unfinished if the attempt identifies the correct structure and the exact missing lemma.

Schedule

DayPrimary workSecondary work
TuesdayExtremal arguments; exchange argumentsGraph theory; algebra
WednesdayDynamic programming; complexity with calculusRecurrences; graph DPs
ThursdayLP proofs; primal–dual algorithmsGraph certificates; algebra
FridayPotential functions; FFTBalls and bins; probability review
WeekendNo workLet consolidation happen
MondayOne integrated review problemCorrection and oral defense
TuesdayFinal examFresh problems; closed notes

Standards for a complete exam solution

A correct algorithmic answer contains four logically separate components:

  1. A precise algorithm or recurrence.
  2. A correctness argument covering every feasible output and every optimal solution, where appropriate.
  3. A termination or evaluation-order argument.
  4. A runtime analysis in the stated computational model.

A plausible algorithm without a correctness proof is incomplete. A proof that an optimum exists without showing that the algorithm finds it is incomplete. An asymptotic bound without identifying the counted operations is incomplete.

How to discover a proof rather than recognize one

When a proof is not immediately visible, separate discovery from verification. First translate the conclusion into a structural question: what would have to be true immediately before the conclusion? Then search for an operation that makes the instance simpler while preserving the hypotheses. Only after finding a plausible mechanism should you write the formal proof.

A useful scratch-page routine is:

  1. Write the quantifiers and negate the claim exactly.
  2. Test the smallest nontrivial instances and draw one example that is nearly false.
  3. Name what may change and what must be preserved under a modification.
  4. Propose three mechanisms: induction or extremality, exchange or local repair, and a numerical certificate such as a potential or dual solution.
  5. For each attempted mechanism, record the first unsupported implication.

This routine turns a failed proof into information. If an exchange fails because feasibility is lost, the missing ingredient is a stronger exchange lemma or a different canonical optimum. If induction fails because the smaller instance forgets boundary information, that information belongs in the induction hypothesis or DP state. If a potential proves progress but not a polynomial bound, its range or per-step decrease is too weak.

Algebra for algorithms

Algebra is not a separate topic from algorithms. It is the language used to turn structural facts into bounds. The most important habits are to preserve inequality directions, expose the relevant scale, and delay approximations until the exact expression has served its purpose.

Sums and scale

The basic finite sums are

∑𝑖=1𝑛𝑖=𝑛(𝑛+1)2,∑𝑖=1𝑛𝑖2=𝑛(𝑛+1)2𝑛+16,

and, for 𝑟≠1,

∑𝑖=0𝑚𝑟𝑖=𝑟𝑚+1−1𝑟−1.

The formula matters less than the scale. Thus ∑𝑖=1𝑛𝑖=Θ(𝑛2), while ∑𝑖=0⌊log2𝑛⌋2𝑖=Θ(𝑛). A geometric sum is controlled by its largest term when the ratio is bounded above one; a decreasing geometric tail is controlled by its first term.

Double counting often removes nested sums. For example,

∑𝑆⊆[𝑛]|𝑆|=∑𝑖=1𝑛|{𝑆⊆[𝑛]:𝑖∈𝑆}|=𝑛2𝑛−1.

The first form counts set memberships by subsets; the second counts them by elements.

Inequalities and logarithms

For positive quantities, logarithms convert products to sums and powers to multipliers. Useful comparisons include

ln(1+𝑥)≤𝑥(𝑥>−1),1−𝑥≤𝑒−𝑥(𝑥∈ℝ),

and, for 𝑥∈[0,1],

𝑒−𝑥1−𝑥≤1−𝑥≤𝑒−𝑥.

The first upper bound follows by comparing the derivative of ln(1+𝑥) with the derivative of 𝑥. Such inequalities are the bridge between exact probabilities like (1−1𝑛)𝑛 and exponential approximations.

When manipulating asymptotic expressions, state the regime. For example, log(𝑛!)=Θ(𝑛log𝑛) follows from

(𝑛2)log(𝑛2)≤∑𝑖=⌈𝑛2⌉𝑛log𝑖≤log(𝑛!)≤𝑛log𝑛.

Recurrences

The point of solving a recurrence is to account for work across scales. A named theorem is convenient after that accounting is understood, but it is not the source of the answer. The reliable process is:

  1. Expand enough levels to identify the sizes and multiplicities of subproblems.
  2. Express the work at one scale.
  3. Sum or integrate over the scales that actually occur.
  4. Use substitution to turn the resulting guess into a proof.

Decrement recurrences as integrals

Suppose

𝑇(𝑛)=𝑇(𝑛−ℎ(𝑛))+𝑔(𝑛),

where one recursive step reduces the argument by ℎ(𝑛). Near size 𝑥, it takes about d𝑥ℎ(𝑥) steps to move through an interval of width d𝑥, and each such step costs about 𝑔(𝑥). This suggests

𝑇(𝑛)≈∫1𝑛𝑔(𝑥)ℎ(𝑥)d𝑥.

Equivalently, view the discrete difference as a derivative:

𝑇(𝑛)−𝑇(𝑛−ℎ(𝑛))≈ℎ(𝑛)𝑇′(𝑛)=𝑔(𝑛),

so 𝑇′(𝑛)≈𝑔(𝑛)ℎ(𝑛). This is a discovery heuristic, not yet a proof. To prove the estimate, partition the trajectory into ranges on which 𝑔 and ℎ vary by only constant factors, or substitute upper and lower comparison functions into the original recurrence.

For example, if 𝑇(𝑛)=𝑇(𝑛−𝑛)+1, then 𝑇′(𝑛)≈1𝑛 and 𝑇(𝑛)=Θ(𝑛). The interpretation is concrete: when the current size is around 𝑥, each step removes about 𝑥, so roughly d𝑥𝑥 steps are spent crossing a short interval.

Divide-and-conquer as work by scale

For 𝑇(𝑛)=𝑎𝑇(𝑛𝑏)+𝑓(𝑛), level 𝑗 contains 𝑎𝑗 subproblems of size 𝑛𝑏𝑗, hence level cost

𝐶𝑗=𝑎𝑗𝑓(𝑛𝑏𝑗).

The recursion ends around 𝐿=log𝑏𝑛. The answer follows from the finite sum ∑𝑗=0𝐿𝐶𝑗: increasing level costs are leaf-dominated, decreasing costs are root-dominated, and comparable costs contribute an extra factor 𝐿. This is the mechanism summarized by the Master theorem.

Calculus is useful when the level cost changes slowly. Put 𝑥=𝑛𝑏𝑗, so 𝑗=log𝑏(𝑛𝑥) and one unit of 𝑗 corresponds to a constant change in log𝑥. Thus sums over recursion levels behave like integrals with measure d𝑥𝑥, not d𝑥:

∑𝑗𝐶𝑗≈∫1𝑛𝐶(log𝑏(𝑛𝑥))d𝑥𝑥.

That extra 1𝑥 is why boundary terms such as 𝑓(𝑛)=𝑛log2𝑛 behave differently from ordinary polynomial terms.

Unequal branches

For

𝑇(𝑛)=∑𝑖=1𝑞𝑎𝑖𝑇(𝑏𝑖𝑛)+𝑔(𝑛),0<𝑏𝑖<1,

there may be no uniform notion of a level. Find the exponent 𝑝 for which the total 𝑝-mass of the children equals the parent’s:

∑𝑖𝑎𝑖𝑏𝑖𝑝=1.

If 𝑇(𝑛) were proportional to 𝑛𝑝, this equation would make recursive work balance. A continuous recursion-tree calculation then predicts

𝑇(𝑛)=Θ(𝑛𝑝(1+∫1𝑛𝑔(𝑢)𝑢𝑝+1d𝑢)).

This is the substance of the Akra–Bazzi formula. You do not need to quote it blindly: the balance equation identifies the homogeneous scale, and the integral accumulates nonrecursive work relative to that scale. For exam proofs, state regularity assumptions and verify the resulting bound by substitution when the recurrence is simple enough.

Substitution is the certification step

Expansion and calculus suggest a candidate bound; induction certifies it. If a claim 𝑇(𝑛)≤𝐶𝑓(𝑛) fails to close, do not immediately change the asymptotic answer. Add lower-order slack, such as 𝐶𝑛log𝑛−𝐷𝑛, because recursive calls may need that negative term to pay for the current level. Floors and ceilings are normally absorbed only after showing that they perturb the argument by a controlled amount.

Worked problem: A recursion treeFact 2
Consider 𝑇(𝑛)=2𝑇(𝑛2)+𝑛log𝑛 for powers of two. At level 𝑗 there are 2𝑗 subproblems of size 𝑛2𝑗. Each contributes (𝑛2𝑗)log(𝑛2𝑗), so the level cost is 𝑛(log𝑛−𝑗). With 𝐿=log2𝑛 levels, the internal cost is ∑𝑗=0𝐿−1𝑛(𝐿−𝑗)=𝑛∑𝑟=1𝐿𝑟=Θ(𝑛log2𝑛). The leaves add only Θ(𝑛).
Worked problem: A logarithmic boundary termFact 3
Consider 𝑇(𝑛)=2𝑇(𝑛2)+𝑛log2𝑛 for powers of two. At level 𝑗, the total nonrecursive work is 2𝑗𝑛2𝑗log2(𝑛2𝑗)=𝑛(log𝑛−𝑗)2. Writing 𝑟=log𝑛−𝑗, the internal work is 𝑛∑𝑟=1log𝑛1𝑟2=Θ(𝑛). The leaves also cost Θ(𝑛), so 𝑇(𝑛)=Θ(𝑛). Treating every level as if it cost 𝑛log2𝑛 would miss the fact that costs rise near the leaves; treating every level as Θ(𝑛) would introduce a spurious logarithm. The sum across scales is decisive.
Worked problem: A binomial estimateFact 4
Show (𝑛𝑘)≤(𝑒𝑛𝑘)𝑘. Since (𝑛𝑘)≤𝑛𝑘𝑘!, it suffices to lower-bound 𝑘!. The integral estimate ∑𝑖=1𝑘ln𝑖≥∫1𝑘ln𝑥d𝑥=𝑘ln𝑘−𝑘+1 gives 𝑘!≥𝑒(𝑘𝑒)𝑘≥(𝑘𝑒)𝑘. Substitution yields the result. This estimate is used constantly in randomized algorithms and union bounds.
Easy — 2–5 minutes: Geometric levelsProposition 5

Evaluate ∑𝑗=0log2𝑛𝑛2𝑗 up to a tight asymptotic bound, and explain which level controls the sum.

Write the decisive idea before filling in algebra or pseudocode.

Medium — 15 minutes: A changing branching factorProposition 6

Solve 𝑇(𝑛)=𝑇(𝑛3)+𝑇(2𝑛3)+𝑛 to a tight asymptotic bound. Use a recursion-tree argument rather than quoting a theorem, and justify both upper and lower bounds.

Write the decisive idea before filling in algebra or pseudocode.

Hard — 45 minutes: Subset-sum bookkeepingProposition 7

Evaluate ∑𝑆⊆[𝑛]|𝑆|2 exactly. Derive the answer by counting ordered pairs (𝑖,𝑗) belonging to a subset, treating 𝑖=𝑗 and 𝑖≠𝑗 separately. Then use the result to analyze an algorithm that performs Θ(|𝑆|2) work for every subset 𝑆.

Write the decisive idea before filling in algebra or pseudocode.

Easy — 2–5 minutes: A shrinking decrementProposition 8

Use the differential heuristic to guess a tight bound for 𝑇(𝑛)=𝑇(𝑛−𝑛)+1. Then give a short discrete argument that the number of steps is both 𝑂(𝑛) and Ω(𝑛).

Write the decisive idea before filling in algebra or pseudocode.

Medium — 15 minutes: A logarithmic boundaryProposition 9

Solve 𝑇(𝑛)=2𝑇(𝑛2)+𝑛log2𝑛 from a recursion tree. Write the exact level cost, reindex the sum by distance from the leaves, and explain why multiplying the root cost by the number of levels is invalid.

Write the decisive idea before filling in algebra or pseudocode.

Hard — 45 minutes: Unequal branches without MasterProposition 10

Solve 𝑇(𝑛)=𝑇(𝑛3)+𝑇(2𝑛3)+𝑛 without using the Master theorem. First find the balance exponent 𝑝 from (13)𝑝+(23)𝑝=1. Then prove the tight bound with a recursion-tree conservation argument or substitution. Account explicitly for unequal leaf depths and for floors or ceilings.

Write the decisive idea before filling in algebra or pseudocode.

Balls and bins

Throwing balls independently and uniformly into bins is the basic model for hashing, randomized load balancing, occupancy, and collision phenomena. The first task is to define the random variable precisely: the load of one bin, the number of empty bins, the number of collisions, or the maximum load require different arguments.

Before calculating, decide whether the random object is attached to a ball, a bin, or a pair of balls. This choice determines the useful indicators. Bin indicators are natural for occupancy, pair indicators for collisions, and ball indicators for the event that an arriving ball sees a particular load. Many incorrect solutions start with a true symmetry statement—every bin has the same expected load—and silently replace it with a false independence statement about the vector of loads.

There are three recurring proof moves. Linearity of expectation handles global counts even when bins are dependent. A union bound converts a tail bound for one named bin into an upper bound for the maximum. Phase decomposition, as in coupon collection, represents a global waiting time as a sum of simpler waiting times. Always say which move is being used; they have different hypotheses.

Let 𝑚 balls be thrown independently into 𝑛 bins. For a fixed bin 𝑗,

𝐿𝑗∼Binomial(𝑚,1𝑛),𝔼[𝐿𝑗]=𝑚𝑛.

The loads are not mutually independent because ∑𝑗𝐿𝑗=𝑚, but indicator variables across balls for one fixed bin are independent. Do not assume more independence than the experiment provides.

Indicators and occupancy

Let 𝐼𝑗 indicate that bin 𝑗 is empty. Then

Pr(𝐼𝑗=1)=(1−1𝑛)𝑚,

so by linearity of expectation, without needing independence among bins,

𝔼[empty bins]=𝑛(1−1𝑛)𝑚≈𝑛𝑒−𝑚𝑛.

Likewise, the probability that a specified pair of balls collides is 1𝑛. Summing pair indicators gives expected colliding pairs

(𝑚2)𝑛.

This counts pairs, not the number of balls involved in any collision.

Birthday threshold

The probability of no collision among 𝑚≤𝑛 balls is

∏𝑖=0𝑚−1(1−𝑖𝑛)≤exp(−∑𝑖=0𝑚−1𝑖𝑛)=exp(−𝑚(𝑚−1)2𝑛).

Thus collisions become likely around 𝑚=Θ(𝑛), long before average load becomes large.

Maximum load

For 𝑚=𝑛, a fixed bin has mean one, but the maximum load is much larger. A union bound gives

Pr(max𝑗𝐿𝑗≥𝑘)≤𝑛Pr(𝐿1≥𝑘)≤𝑛(𝑛𝑘)𝑛−𝑘≤𝑛(𝑒𝑘)𝑘.

Choosing 𝑘=𝐶log𝑛loglog𝑛 for a sufficiently large constant 𝐶 makes this probability vanish. A matching lower bound needs a second-moment, Poissonization, or negative-dependence argument. The important lesson is that mean load does not predict maximum load.

Coupon collector

When 𝑖 bins have been seen, the probability that the next ball hits a new bin is 𝑛−𝑖𝑛. The waiting time for the next new bin is geometric with mean 𝑛𝑛−𝑖. Hence the expected time to see all bins is

∑𝑖=0𝑛−1𝑛𝑛−𝑖=𝑛𝐻𝑛=Θ(𝑛log𝑛).

This phase decomposition turns a dependent global process into waiting times whose expectations can be summed.

Worked problem: Expected occupied binsFact 11
Let 𝐽𝑗 indicate that bin 𝑗 is occupied. Then 𝔼[𝐽𝑗]=1−(1−1𝑛)𝑚. Consequently 𝔼[∑𝑗𝐽𝑗]=𝑛(1−(1−1𝑛)𝑚). For 𝑚=𝑛, this is approximately 𝑛(1−𝑒−1). The indicators 𝐽𝑗 are dependent, but linearity of expectation does not require independence.
Worked problem: A maximum-load upper boundFact 12
For 𝑛 balls and 𝑛 bins, the event 𝐿𝑗≥𝑘 implies that some chosen set of 𝑘 balls all landed in bin 𝑗. A union bound over such sets gives Pr(𝐿𝑗≥𝑘)≤(𝑛𝑘)𝑛−𝑘≤(𝑒𝑘)𝑘. Another union bound over bins yields 𝑛(𝑒𝑘)𝑘. Taking logarithms shows why 𝑘 near log𝑛loglog𝑛 is the relevant scale.
Easy — 2–5 minutes: Empty binsProposition 13

Throw 2𝑛 balls into 𝑛 bins. Compute the expected number of empty bins and give its asymptotic form.

Write the decisive idea before filling in algebra or pseudocode.

Medium — 15 minutes: Collision thresholdProposition 14

Prove that if 𝑚=𝑜(𝑛), the probability of any collision is 𝑜(1). If 𝑚=𝑐𝑛, use the no-collision product and logarithmic inequalities to identify the limiting no-collision probability. State where independence is used.

Write the decisive idea before filling in algebra or pseudocode.

Hard — 45 minutes: Two-choice load balancingProposition 15

Suppose balls arrive sequentially, sample two independent uniform bins, and enter the less loaded sampled bin. Compare this process with one-choice allocation. Establish at least one rigorous improvement: for example, bound the probability that a fixed ball is placed above level ℎ in terms of the fraction of bins already at level ℎ, then derive a recurrence suggesting why high-level fractions decay doubly exponentially. Clearly separate what you prove from the sharper Θ(loglog𝑛) maximum-load theorem you may know.

Write the decisive idea before filling in algebra or pseudocode.

Concentration inequalities

Concentration inequalities turn expectations, variances, boundedness, and independence into tail bounds. The main skill is not selecting the formula with the strongest name. It is matching the available information to the theorem’s hypotheses and expressing the bad event in the theorem’s variables.

Use the following pipeline rather than searching a formula sheet. Define the sum and its mean, rewrite the bad event as a centered upper or lower tail, list the information actually available (nonnegativity, variance, ranges, independence, Bernoulli structure), and only then choose a theorem. Finally, compare the exponent with the natural scale of the problem. A syntactically correct bound can still be useless if its exponent tends to zero.

The inequalities form a derivational hierarchy. Markov converts a moment into a tail probability. Exponential Markov lets us choose which exponential moment to use. Independence factorizes the MGF of a sum. Hoeffding, Chernoff, and Bernstein differ mainly in how they bound the individual MGFs: by range, exact Bernoulli structure, or variance plus a range cap. Remembering this common spine makes their assumptions harder to confuse.

Exponential Markov and the MGF method

Ordinary Markov says that for 𝑌≥0 and 𝑎>0,

Pr(𝑌≥𝑎)≤𝔼[𝑌]𝑎.

For any random variable 𝑋 and 𝜆>0, monotonicity of the exponential makes 𝑒𝜆𝑋 nonnegative, so

Pr(𝑋≥𝑡)=Pr(𝑒𝜆𝑋≥𝑒𝜆𝑡)≤𝑒−𝜆𝑡𝔼[𝑒𝜆𝑋].

This is exponential Markov. The parameter 𝜆 is freely chosen wherever the moment generating function is finite. Every admissible choice proves a bound; minimizing over 𝜆 gives the best certificate available from this MGF estimate.

For independent 𝑋𝑖,

𝔼[𝑒𝜆∑𝑖𝑋𝑖]=∏𝑖𝔼[𝑒𝜆𝑋𝑖].

This factorization is the engine behind Chernoff, Hoeffding, and Bernstein. Center variables when the event concerns deviation from the mean.

Worked problem: Optimizing an exponential certificateFact 16
Suppose 𝔼[𝑒𝜆𝑋]≤𝑒𝜆2𝜎22 for every 𝜆>0. Then Pr(𝑋≥𝑡)≤exp(−𝜆𝑡+𝜆2𝜎22). Differentiating the exponent gives −𝑡+𝜆𝜎2=0, hence 𝜆=𝑡𝜎2. Substitution yields Pr(𝑋≥𝑡)≤exp(−𝑡22𝜎2).
Easy — 2–5 minutes: Apply exponential MarkovProposition 17

If 𝔼[𝑒2𝑋]≤7, give an upper bound on Pr(𝑋≥3) without optimizing any parameter.

Write the decisive idea before filling in algebra or pseudocode.

Medium — 15 minutes: A geometric tailProposition 18

Let 𝑋 be geometric with Pr(𝑋=𝑘)=(1−𝑝)𝑘−1𝑝 for 𝑘≥1. Compute its MGF and identify the range of 𝜆 for which it is finite. Apply exponential Markov to bound Pr(𝑋≥𝑡), and compare with the exact tail (1−𝑝)𝑡−1.

Write the decisive idea before filling in algebra or pseudocode.

Hard — 45 minutes: From an MGF to a sub-Gaussian maximumProposition 19

Let 𝑋1,…,𝑋𝑛 satisfy 𝔼[𝑒𝜆𝑋𝑖]≤𝑒𝜆2𝜎22 for all real 𝜆; independence is not assumed. Use exponential Markov and a union bound to prove an upper-tail bound for max𝑖𝑋𝑖. Then integrate or otherwise bound the tail to show 𝔼[max𝑖𝑋𝑖]=𝑂(𝜎log𝑛). Track the contribution from small thresholds where the probability bound exceeds one.

Write the decisive idea before filling in algebra or pseudocode.

Chebyshev’s inequality

Apply Markov to the nonnegative variable (𝑋−𝜇)2:

Pr(|𝑋−𝜇|≥𝑡)=Pr((𝑋−𝜇)2≥𝑡2)≤Var(𝑋)𝑡2.

Chebyshev needs only finite variance and no boundedness or independence. For a sum, compute variance carefully:

Var(∑𝑖𝑋𝑖)=∑𝑖Var(𝑋𝑖)+2∑𝑖<𝑗Cov(𝑋𝑖,𝑋𝑗).

Independence makes covariance terms zero, but pairwise independence is already enough for this variance identity. Chebyshev usually gives polynomial rather than exponential decay.

Worked problem: Weak law for bounded-variance averagesFact 20
Let 𝑋𝑖 be independent with common mean 𝜇 and variance 𝜎2. For |𝑋=𝑛−1∑𝑖𝑋𝑖, Var(|𝑋)=𝜎2𝑛. Therefore Pr(||𝑋−𝜇|≥𝜀)≤𝜎2𝑛𝜀2, which tends to zero. No MGF assumption is required.
Easy — 2–5 minutes: One variance calculationProposition 21

If 𝔼[𝑋]=10 and Var(𝑋)=9, bound Pr(|𝑋−10|≥6) using Chebyshev.

Write the decisive idea before filling in algebra or pseudocode.

Medium — 15 minutes: Pairwise independence sufficesProposition 22

Let 𝑋1,…,𝑋𝑛 be pairwise independent Bernoulli(𝑝) variables. Use Chebyshev to bound Pr(|∑𝑖𝑋𝑖−𝑛𝑝|≥𝜀𝑛). Explain why mutual independence was not used.

Write the decisive idea before filling in algebra or pseudocode.

Hard — 45 minutes: Randomized approximation by samplingProposition 23

An unknown population has values in [0,1] with mean 𝜇. Draw 𝑛 independent samples and return their mean. Using only variance and Chebyshev, derive a sample size sufficient for additive error 𝜀 with failure probability at most 𝛿. Then use a median of 𝑟 independent batch means to reduce failure probability exponentially in 𝑟; justify the second stage with a binomial tail argument or a self-contained counting bound.

Write the decisive idea before filling in algebra or pseudocode.

Hoeffding’s inequality

If independent variables satisfy 𝑋𝑖∈[𝑎𝑖,𝑏𝑖], then for 𝑆=∑𝑖𝑋𝑖,

Pr(𝑆−𝔼[𝑆]≥𝑡)≤exp(−2𝑡2∑𝑖(𝑏𝑖−𝑎𝑖)2).

The same bound holds for the lower tail. Hoeffding’s lemma proves the centered MGF bound

𝔼[𝑒𝜆(𝑋𝑖−𝔼[𝑋𝑖])]≤exp(𝜆2(𝑏𝑖−𝑎𝑖)28),

then exponential Markov, independence, and optimization finish the proof. Hoeffding uses ranges, not actual variances. It is robust but may be loose when variance is much smaller than the squared range.

Worked problem: Majority of competent votersFact 24

Let 𝑋𝑖 be independent Bernoulli(𝑝), 𝑝>12, and 𝑆=∑𝑖𝑋𝑖. An incorrect majority implies 𝑆−𝔼[𝑆]≤−(𝑝−12)𝑛. Since every range has length one, Hoeffding gives

Pr(𝑆≤𝑛2)≤exp(−2(𝑝−12)2𝑛).

The structural step is expressing the threshold as a deviation from the mean.

Easy — 2–5 minutes: Bounded averageProposition 25

Independent 𝑋𝑖∈[0,1]. Bound Pr(|𝑛−1∑𝑖𝑋𝑖−𝑛−1∑𝑖𝔼[𝑋𝑖]|≥𝜀).

Write the decisive idea before filling in algebra or pseudocode.

Medium — 15 minutes: Unequal rangesProposition 26

Independent measurements satisfy 𝑋𝑖∈[−𝑖−1,𝑖−1]. Use Hoeffding to bound Pr(∑𝑖=1𝑛(𝑋𝑖−𝔼[𝑋𝑖])≥𝑡). Simplify the denominator to a bound independent of 𝑛, and interpret why later measurements add little tail risk.

Write the decisive idea before filling in algebra or pseudocode.

Hard — 45 minutes: Random cutProposition 27

Place each vertex of a graph independently on either side of a cut with probability 12. Edge-crossing indicators are not all independent. Expose vertices one at a time and investigate whether ordinary Hoeffding applies directly to the edge indicators. Give a valid concentration proof for the cut size under an additional maximum-degree assumption, either by partitioning edges into independent groups or by deriving a bounded-differences martingale argument explicitly. Clearly identify every independence or bounded-change claim; do not cite an inapplicable i.i.d. formula.

Write the decisive idea before filling in algebra or pseudocode.

Chernoff bounds

For independent Bernoulli variables 𝑋𝑖 with possibly different success probabilities, let 𝑋=∑𝑖𝑋𝑖 and 𝜇=𝔼[𝑋]. The standard multiplicative bounds include

Pr(𝑋≥(1+𝛿)𝜇)≤(𝑒𝛿(1+𝛿)1+𝛿)𝜇

for 𝛿≥0, and the convenient consequence

Pr(𝑋≥(1+𝛿)𝜇)≤exp(−𝛿2𝜇3)

for 0≤𝛿≤1. For the lower tail,

Pr(𝑋≤(1−𝛿)𝜇)≤exp(−𝛿2𝜇2),0≤𝛿≤1.

To derive the upper bound, independence gives

𝔼[𝑒𝜆𝑋]=∏𝑖(1−𝑝𝑖+𝑝𝑖𝑒𝜆)≤exp((𝑒𝜆−1)𝜇).

Exponential Markov at (1+𝛿)𝜇 and the choice 𝜆=ln(1+𝛿) yield the exact multiplicative expression.

Worked problem: No overloaded bin at a moderate meanFact 28
Throw 𝑚 balls into 𝑛 bins and fix a bin with mean load 𝜇=𝑚𝑛. Chernoff gives, for 0≤𝛿≤1, Pr(𝐿𝑗≥(1+𝛿)𝜇)≤𝑒−𝛿2𝜇3. A union bound over 𝑛 bins gives Pr(max𝑗𝐿𝑗≥(1+𝛿)𝜇)≤𝑛𝑒−𝛿2𝜇3. This becomes useful when 𝜇 is at least a sufficiently large multiple of log𝑛.
Easy — 2–5 minutes: Multiplicative substitutionProposition 29

For 𝑋 a sum of independent Bernoulli variables with 𝔼[𝑋]=100, bound Pr(𝑋≥150) using the convenient Chernoff upper tail.

Write the decisive idea before filling in algebra or pseudocode.

Medium — 15 minutes: Derive the optimizerProposition 30

Starting from Pr(𝑋≥(1+𝛿)𝜇)≤exp((𝑒𝜆−1)𝜇−𝜆(1+𝛿)𝜇), differentiate with respect to 𝜆, find the optimum, and derive (𝑒𝛿(1+𝛿)1+𝛿)𝜇. Check that the optimizer is admissible.

Write the decisive idea before filling in algebra or pseudocode.

Hard — 45 minutes: Randomized rounding with capacityProposition 31

Given fractional values 𝑥𝑖∈[0,1] with ∑𝑖𝑎𝑖𝑥𝑖≤𝐵 and 0≤𝑎𝑖≤1, independently select item 𝑖 with probability 𝑥𝑖. Let 𝑊=∑𝑖𝑎𝑖𝑋𝑖. Develop a tail bound for 𝑊 exceeding its mean by an additive amount. You may first handle equal 𝑎𝑖 with Chernoff, then reduce rational weights to Bernoulli trials or derive an MGF bound for weighted variables. State clearly whether your final exponent depends on 𝐵, the mean, or ∑𝑖𝑎𝑖2𝑥𝑖.

Write the decisive idea before filling in algebra or pseudocode.

Bernstein’s inequality

Let independent centered variables satisfy |𝑋𝑖|≤𝑏, and write 𝑉=∑𝑖Var(𝑋𝑖). Bernstein’s inequality states

Pr(∑𝑖𝑋𝑖≥𝑡)≤exp(−𝑡22(𝑉+𝑏𝑡3)).

It interpolates between a variance-controlled Gaussian regime 𝑡2𝑉 and a range-controlled exponential regime 𝑡𝑏.

The bounded-variable MGF proof begins with, for 𝑘≥2,

|𝑋𝑖|𝑘≤𝑏𝑘−2𝑋𝑖2,

so

|𝔼[𝑋𝑖𝑘]|≤𝑏𝑘−2Var(𝑋𝑖).

Expanding the exponential series, using 𝔼[𝑋𝑖]=0, and bounding the higher terms yields

𝔼[𝑒𝜆𝑋𝑖]≤exp(𝜆2Var(𝑋𝑖)2(1−𝜆𝑏3))

for 0<𝜆<3𝑏. Independence sums the variances in the exponent. Exponential Markov and the valid choice 𝜆=𝑡𝑉+𝑏𝑡3 give the displayed tail.

Bernstein improves on a range-only inequality when 𝑉 is substantially below the worst-case squared-range sum. The 𝑏𝑡 term prevents variance alone from claiming unrealistically strong far-tail behavior.

Worked problem: Weighted independent votesFact 32

Let 𝑌𝑖 be independent Bernoulli(𝑝) terminal decisions with weights 𝑤𝑖, 𝑊=∑𝑖𝑤𝑖, and 𝑆=∑𝑖𝑤𝑖𝑌𝑖. Failure of a correct weighted majority is 𝑆≤𝑊2. Center 𝑋𝑖=𝑤𝑖(𝑝−𝑌𝑖) for the lower tail. Then |𝑋𝑖|≤𝑤max, 𝑉=𝑝(1−𝑝)∑𝑖𝑤𝑖2, and 𝑡=(𝑝−12)𝑊. Bernstein gives

Pr(𝑆≤𝑊2)≤exp(−(𝑝−12)2𝑊22(𝑝(1−𝑝)∑𝑖𝑤𝑖2+𝑤max(𝑝−12)𝑊3)).

The quantities ∑𝑖𝑤𝑖2 and 𝑤max distinguish diffuse from concentrated weight.

Easy — 2–5 minutes: Identify Bernstein parametersProposition 33

Independent centered 𝑋𝑖 satisfy |𝑋𝑖|≤2 and ∑𝑖Var(𝑋𝑖)=30. Write Bernstein’s upper bound for Pr(∑𝑖𝑋𝑖≥12) without further simplification.

Write the decisive idea before filling in algebra or pseudocode.

Medium — 15 minutes: Variance versus rangeProposition 34

Let independent 𝑋𝑖 equal 1−𝑝 with probability 𝑝 and −𝑝 otherwise. Compute their means, variances, and uniform bound. Write both Hoeffding and Bernstein bounds for Pr(∑𝑖𝑋𝑖≥𝑡), and identify a regime of small 𝑝 and moderate 𝑡 where Bernstein captures information Hoeffding ignores.

Write the decisive idea before filling in algebra or pseudocode.

Hard — 45 minutes: Derive Bernstein from the seriesProposition 35

Let independent centered 𝑋𝑖 satisfy |𝑋𝑖|≤𝑏. Starting from the power series for 𝑒𝜆𝑋𝑖, prove the stated MGF bound, including the restriction 𝜆𝑏<3. Apply exponential Markov to the sum, choose 𝜆=𝑡𝑉+𝑏𝑡3, verify admissibility, and simplify the exponent to obtain Bernstein’s inequality. Every inequality in the series bound must be justified.

Write the decisive idea before filling in algebra or pseudocode.

Selecting a bound

ToolInformationTypical tailUse when
Markov𝑌≥0, mean1𝑡Only a first moment is available
ChebyshevMean, variance1𝑡2Dependence is allowed and variance is known
HoeffdingIndependence, ranges𝑒−Θ(𝑡2𝑅)Variables are bounded; variances may be unknown
ChernoffIndependent Bernoulli or suitable MGF𝑒−Θ(𝛿2𝜇)Relative deviations of counts
BernsteinIndependence, variance, max range𝑒−Θ(𝑡2𝑉+𝑏𝑡)Actual variance is informative

Potential functions and amortized analysis

The design question is causal: what feature of the current state predicts future expensive work? Potential is stored liability, not an arbitrary quantity that happens to be monotone. In a binary counter, one-bits predict future flips. In a dynamic array, excess occupancy since the last resize predicts the next copying cost. This viewpoint explains both how to invent a potential and how to reject one that tracks the wrong feature.

A potential function assigns stored credit to an algorithmic state. It can serve three related but distinct purposes:

  1. Amortization: expensive operations spend credit accumulated earlier.
  2. Termination: every operation strictly changes a bounded potential.
  3. Quantitative convergence: every operation changes the potential by enough to bound the number of iterations.

Termination alone does not imply polynomial time. A nonnegative integer potential may start exponentially large or decrease by only one each step.

Keep amortization and local search logically separate. In amortization, the potential may rise on cheap operations and fall on expensive ones; only the telescoping sum matters. In a termination proof, every allowed move must strictly improve a well-founded quantity. In a runtime proof, you additionally need a polynomially bounded initial range and a quantitatively large change per move.

The potential method

Let 𝐷𝑖 be the state after operation 𝑖, 𝑐𝑖 its actual cost, and Φ(𝐷𝑖) the potential. Define the amortized cost

𝑐̂𝑖=𝑐𝑖+Φ(𝐷𝑖)−Φ(𝐷𝑖−1).

Summing telescopes:

∑𝑖=1𝑚𝑐𝑖=∑𝑖=1𝑚𝑐̂𝑖+Φ(𝐷0)−Φ(𝐷𝑚).

If Φ(𝐷0)=0 and Φ(𝐷𝑚)≥0, total actual cost is at most total amortized cost. Other initial potentials are allowed, but their contribution must be retained.

Designing a potential

Look at what makes a future operation expensive. Store credit on precisely that structure. If an operation costs 𝑘, seek a potential drop of order 𝑘 or argue that earlier cheap operations accumulated enough potential.

Weighted potentials are often necessary. If different objects cause different future work, assign each a weight reflecting that liability. The potential need not resemble the objective function.

Multiplicative progress

If a positive potential satisfies

Φ𝑡+1≤(1−𝛿)Φ𝑡,

then Φ𝑡≤𝑒−𝛿𝑡Φ0. Reaching Φ𝑡<𝜀 takes 𝑂(𝛿−1log(Φ0𝜀)) steps. This is the deterministic analogue of many exponential tail calculations.

Worked problem: Binary counterFact 36
Let the actual cost of an increment be the number of flipped bits, and let Φ be the number of one-bits. If an increment flips 𝑡 trailing ones to zero and one zero to one, then 𝑐=𝑡+1 and ΔΦ=1−𝑡. Therefore the amortized cost is (𝑡+1)+(1−𝑡)=2. Starting at zero potential, 𝑚 increments perform at most 2𝑚 bit flips.
Worked problem: Dynamic-array doublingFact 37
Charge one unit for inserting and 𝑚 units for copying when a full array of capacity 𝑚 doubles. Let 𝑛 be the size and 𝑚 the capacity, and define Φ=2𝑛−𝑚 between the point when an array is at least half full and the next expansion. An ordinary insertion raises potential by 2, so its amortized cost is 3. At expansion from 𝑛=𝑚 to capacity 2𝑚, copying and inserting cost 𝑚+1, while the appropriate potential reset absorbs the accumulated credit. An equivalent accounting proof charges each inserted element enough to pay for its next move.
Easy — 2–5 minutes: Stack with multipopProposition 38

A stack supports Push, Pop, and MultiPop(𝑘), which removes up to 𝑘 items. Using stack size as potential, prove that any sequence of 𝑚 operations takes 𝑂(𝑚) total time.

Write the decisive idea before filling in algebra or pseudocode.

Medium — 15 minutes: A terminating local processProposition 39

Each vertex of a graph is colored red or blue. While a vertex has strictly more neighbors of the opposite color than its own color, flip it. Find a potential that proves termination. Bound the number of flips in terms of |𝐸|, assuming ties do not flip. Explain why your potential changes in the correct direction.

Write the decisive idea before filling in algebra or pseudocode.

Hard — 45 minutes: Resizable table with contractionProposition 40

A dynamic table doubles when full and halves when its load falls below 14. Insertions and deletions cost one plus the number of copied items. Design a piecewise-linear nonnegative potential proving 𝑂(1) amortized cost per operation. Verify the analysis separately in the regimes above and below load 12, and explain why contracting at load 12 instead would permit thrashing.

Write the decisive idea before filling in algebra or pseudocode.

Fast Fourier transform

The FFT is best understood as two ideas, not one formula. First, evaluation is a change of representation: multiplication is difficult in coefficient form because every pair of coefficients interacts, but trivial in value form because values multiply coordinatewise. Second, roots of unity make the change of representation fast because squaring maps the 𝑛 evaluation points onto only 𝑛2 distinct points. The even and odd coefficient polynomials can therefore share their recursive evaluations.

The FFT is a fast algorithm for evaluating a polynomial at roots of unity. Its algorithmic importance comes from a representation change:

coefficient convolution⇔pointwise multiplication of values.

When reducing a combinatorial problem to convolution, write the coefficient meaning before writing an FFT. If coefficient 𝑎𝑖 counts objects of weight 𝑖 and 𝑏𝑗 counts objects of weight 𝑗, then the coefficient of 𝑥𝑡 in the product counts ordered pairs whose weights sum to 𝑡. Questions about distinct objects, unordered pairs, negative indices, or Boolean existence need explicit correction; the transform does not resolve those modeling issues.

DFT and roots of unity

Let 𝜔𝑛=𝑒2𝜋𝑖𝑛 be a primitive 𝑛th root of unity. For coefficients 𝑎0,…,𝑎𝑛−1, the discrete Fourier transform is

𝑦𝑘=∑𝑗=0𝑛−1𝑎𝑗𝜔𝑛𝑗𝑘,0≤𝑘<𝑛.

Thus 𝑦𝑘=𝐴(𝜔𝑛𝑘) for 𝐴(𝑥)=∑𝑗𝑎𝑗𝑥𝑗. Direct evaluation costs Θ(𝑛2).

Important identities are

𝜔𝑛𝑛=1,𝜔𝑛𝑛2=−1,𝜔𝑛2𝑘=𝜔𝑛2𝑘.

Distinct roots are orthogonal:

∑𝑘=0𝑛−1𝜔𝑛𝑘𝑗={𝑛𝑗≡0mod𝑛0otherwise.

This geometric-sum identity explains the inverse transform.

Even–odd recursion

Split

𝐴(𝑥)=𝐴even(𝑥2)+𝑥𝐴odd(𝑥2).

At 𝑥=𝜔𝑛𝑘, both smaller polynomials are evaluated at 𝜔𝑛2𝑘. Moreover, the points for 𝑘 and 𝑘+𝑛2 have the same square and opposite signs. One pair of recursive transforms therefore produces two outputs:

𝑦𝑘=𝐸𝑘+𝜔𝑛𝑘𝑂𝑘,𝑦𝑘+𝑛2=𝐸𝑘−𝜔𝑛𝑘𝑂𝑘.

The recurrence 𝑇(𝑛)=2𝑇(𝑛2)+Θ(𝑛) gives Θ(𝑛log𝑛) time for powers of two.

Inverse transform and convolution

The inverse DFT uses 𝜔𝑛−1 and divides by 𝑛:

𝑎𝑗=1𝑛∑𝑘=0𝑛−1𝑦𝑘𝜔𝑛−𝑗𝑘.

If 𝐶(𝑥)=𝐴(𝑥)𝐵(𝑥), then 𝐶(𝑧)=𝐴(𝑧)𝐵(𝑧) at every evaluation point. Hence:

  1. zero-pad both coefficient arrays;
  2. compute their FFTs;
  3. multiply outputs coordinatewise;
  4. apply the inverse FFT.

If degrees are 𝑑𝐴,𝑑𝐵, use transform length at least 𝑑𝐴+𝑑𝐵+1. Insufficient padding computes cyclic convolution, causing high-degree coefficients to wrap around.

Worked problem: Multiplying two polynomialsFact 41
Let 𝐴(𝑥)=1+2𝑥 and 𝐵(𝑥)=3+𝑥. Their coefficient convolution is (1,2)∗(3,1)=(3,7,2), so 𝐶(𝑥)=3+7𝑥+2𝑥2. An FFT implementation pads each array to length four, evaluates at the fourth roots 1,𝑖,−1,−𝑖, multiplies the four pairs of values, and interpolates. The extra zero prevents the degree-two coefficient from wrapping into degree zero.
Worked problem: Counting pair sumsFact 42
For sets or multisets 𝐴,𝐵⊆{0,…,𝑀}, create frequency arrays 𝑎𝑖,𝑏𝑖. The coefficient of 𝑥𝑡 in (∑𝑖𝑎𝑖𝑥𝑖)(∑𝑗𝑏𝑗𝑥𝑗) equals ∑𝑖+𝑗=𝑡𝑎𝑖𝑏𝑗, the number of ordered pairs summing to 𝑡. FFT-based polynomial multiplication computes all 2𝑀+1 counts in 𝑂(𝑀log𝑀) time, which can be much faster than enumerating |𝐴‖𝐵| pairs when the value range is moderate.
Easy — 2–5 minutes: Roots and reuseProposition 43

For 𝑛=8, prove 𝜔8𝑘+4=−𝜔8𝑘 and (𝜔8𝑘+4)2=𝜔4𝑘. Explain in one sentence how these identities allow two outputs to reuse the same recursive evaluations.

Write the decisive idea before filling in algebra or pseudocode.

Medium — 15 minutes: Four-point transformProposition 44

Compute the length-four DFT of (𝑎0,𝑎1,𝑎2,𝑎3)=(1,2,0,1) using 𝜔4=𝑖. Then recover the original coefficients with the inverse formula. Show every complex arithmetic step.

Write the decisive idea before filling in algebra or pseudocode.

Hard — 45 minutes: Three-term sumsProposition 45

Given 𝐴⊆{0,…,𝑀}, determine for every 𝑡 whether there exist 𝑎,𝑏,𝑐∈𝐴 with 𝑎+𝑏+𝑐=𝑡. Design an FFT-based algorithm. State whether repeated use of the same element is allowed in your first version. Then modify the encoding or correction terms so that 𝑎,𝑏,𝑐 must be three distinct input positions. Analyze transform length, numerical assumptions, and runtime.

Write the decisive idea before filling in algebra or pseudocode.

Linear-programming proofs

An LP proof has two layers. The modeling layer says what each variable and constraint means. The certification layer says why a feasible solution on the other side bounds the objective. Mixing the layers causes common mistakes: deriving the formal dual correctly but being unable to explain it, or giving a natural combinatorial lower bound that is not actually dual feasible.

Linear programming separates a combinatorial problem into variables, constraints, and an objective. Its value in proofs comes from duality: a feasible solution to one program certifies a bound on every feasible solution to the other.

To derive a dual without memorizing a sign table, attach a nonnegative price 𝑦𝑖 to each covering requirement. Buying 𝑥𝑗 units of primal object 𝑗 helps constraints by amounts 𝐴𝑖𝑗, so the total price charged to that object is ∑𝑖𝐴𝑖𝑗𝑦𝑖. Requiring this charge to be at most its cost 𝑐𝑗 gives the dual constraint. Summing the prices yields the dual objective. The weak- duality algebra below is then exactly the statement that no feasible pricing scheme can charge more than any feasible purchase costs.

Modeling

Begin with the intended integral object. A binary variable 𝑥𝑖 records whether object 𝑖 is chosen. Express every feasibility requirement as a linear constraint, then relax 𝑥𝑖∈{0,1} to 𝑥𝑖≥0 or 0≤𝑥𝑖≤1.

Do not add upper bounds automatically. Sometimes they are implied or unnecessary; sometimes omitting them changes the relaxation. Check explicitly.

A standard covering–packing pair is

min𝑐𝑇𝑥subject to𝐴𝑥≥𝑏,𝑥≥0,max𝑏𝑇𝑦subject to𝐴𝑇𝑦≤𝑐,𝑦≥0.

Each primal constraint creates a dual variable; each primal variable creates a dual constraint. A minimization covering constraint points upward, while the corresponding maximization dual constraint points downward.

Weak duality by algebra

For primal-feasible 𝑥 and dual-feasible 𝑦, with nonnegative entries,

𝑏𝑇𝑦≤(𝐴𝑥)𝑇𝑦=𝑥𝑇𝐴𝑇𝑦≤𝑥𝑇𝑐=𝑐𝑇𝑥.

Every inequality has a reason: 𝐴𝑥≥𝑏 and 𝑦≥0 give the first; 𝐴𝑇𝑦≤𝑐 and 𝑥≥0 give the second. Weak duality alone proves that every dual-feasible value is a lower bound on a minimization optimum.

Strong duality says that, when finite optima exist, the best primal and dual values agree. In algorithm proofs, it is often enough to construct feasible objects of equal value; weak duality then proves both optimal.

Complementary slackness

Optimal feasible solutions 𝑥,𝑦 may be characterized by

𝑦𝑖((𝐴𝑥)𝑖−𝑏𝑖)=0

for every primal constraint 𝑖, and

𝑥𝑗(𝑐𝑗−(𝐴𝑇𝑦)𝑗)=0

for every primal variable 𝑗. Thus a positive variable on one side forces the corresponding constraint on the other side to be tight. Complementary slackness can verify optimality or guide an algorithm, but it does not by itself establish feasibility.

Integrality and rounding

An LP relaxation provides a lower bound for a minimization integer program. To obtain an approximation, transform a fractional solution 𝑥∗ into an integral solution 𝑋 and prove

cost(𝑋)≤𝛼𝑐𝑇𝑥∗≤𝛼OPTinteger.

The first inequality is the rounding analysis; the second is relaxation. Keep their directions distinct. An integrality gap is the worst-case ratio between the integer and fractional optima.

Worked problem: Fractional vertex cover and matchingFact 46

For a graph 𝐺=(𝑉,𝐸) with costs 𝑐𝑣, the relaxation is

min∑𝑣∈𝑉𝑐𝑣𝑥𝑣s.t.𝑥𝑢+𝑥𝑣≥1∀(𝑢,𝑣)∈𝐸,𝑥𝑣≥0.

Its dual assigns weight 𝑦𝑒 to edges:

max∑𝑒∈𝐸𝑦𝑒s.t.∑𝑒∈𝛿(𝑣)𝑦𝑒≤𝑐𝑣∀𝑣,𝑦𝑒≥0.

The dual packs fractional edge weight into vertex capacities. For unit costs it is fractional matching. Rounding every 𝑥𝑣≥12 upward covers each edge, because every edge constraint has at least one endpoint at least 12. Its cost is at most 2∑𝑣𝑐𝑣𝑥𝑣, giving a factor-two approximation.

Worked problem: Optimality certificateFact 47
Consider min3𝑥1+2𝑥2 subject to 𝑥1+𝑥2≥4, 2𝑥1+𝑥2≥5, and 𝑥≥0. The dual is max4𝑦1+5𝑦2 subject to 𝑦1+2𝑦2≤3, 𝑦1+𝑦2≤2, and 𝑦≥0. The primal point (1,3) has value 9; the dual point (1,1) has value 9. Both are feasible, so weak duality proves both are optimal. Equal values are a complete certificate.
Easy — 2–5 minutes: Write a dualProposition 48

Derive the dual of min5𝑥1+4𝑥2 subject to 2𝑥1+𝑥2≥3, 𝑥1+3𝑥2≥4, and 𝑥1,𝑥2≥0.

Write the decisive idea before filling in algebra or pseudocode.

Medium — 15 minutes: Set cover relaxationProposition 49

Given universe 𝑈, sets 𝒮︀, and costs 𝑐𝑆, formulate the standard LP relaxation for minimum-cost set cover and derive its dual. Give a combinatorial interpretation of every dual variable and constraint, and prove weak duality by rearranging sums.

Write the decisive idea before filling in algebra or pseudocode.

Hard — 45 minutes: A gap and its meaningProposition 50

For the unweighted vertex-cover LP, analyze the complete graph 𝐾𝑛. Determine the integer optimum and exhibit a fractional solution. Prove the fractional solution is optimal by constructing a matching dual solution. Compute the ratio and its limit. Then state exactly what this example rules out about any analysis that compares an integral solution only with this LP optimum.

Write the decisive idea before filling in algebra or pseudocode.

Designing primal–dual algorithms

A primal–dual algorithm tries to build a feasible combinatorial object and a lower-bound certificate at the same time. Dual growth tells us which primal objects have become fully paid for; tightness is the event that converts a continuous price increase into a discrete algorithmic choice. The returned primal solution need not satisfy complementary slackness exactly. For an approximation, it is enough that its cost can be charged to the dual objective with bounded multiplicity.

Design the proof before the pseudocode. Decide which uncovered requirements will have their prices raised together, what event stops the raise, and how a tight object is selected. Then check four obligations separately: the dual is never made infeasible; the algorithm terminates; the selected primal objects cover every requirement; and each unit of dual value is charged at most 𝛼 times. A proof that only says “choose tight sets” usually hides at least one of these obligations.

A primal–dual algorithm constructs a combinatorial primal solution while growing a feasible dual certificate. Tight dual constraints indicate primal objects that have become fully paid for.

For a covering primal and packing dual, the generic pattern is:

  1. Start with 𝑦=0, which is dual feasible.
  2. Choose an uncovered primal requirement.
  3. Raise its dual variable until some dual constraint becomes tight.
  4. Add the corresponding primal object or mark it eligible.
  5. Continue until all requirements are covered.
  6. Optionally reverse-delete redundant primal objects.
  7. Charge the primal cost to dual variables and bound the multiplicity.

The analysis has distinct proof obligations:

  1. Dual feasibility: no increase passes a constraint’s remaining slack.
  2. Primal feasibility: the stopping condition covers every requirement.
  3. Cost comparison: selected tight constraints express primal costs as dual contributions.
  4. Multiplicity bound: each dual contribution is charged at most 𝛼 times.

Then

𝑐𝑇𝑥≤𝛼𝑏𝑇𝑦≤𝛼OPT.

This is approximate complementary slackness: selected primal variables tend to have tight dual constraints, while positive dual variables correspond to approximately tight primal constraints.

Weighted vertex cover

Start with 𝑦𝑒=0. While an edge 𝑒=(𝑢,𝑣) is uncovered, increase 𝑦𝑒 until one endpoint constraint

∑𝑒∈𝛿(𝑣)𝑦𝑒≤𝑐𝑣

becomes tight; add every newly tight endpoint to the cover. The final cover 𝐶 is feasible. Since each chosen vertex is tight,

∑𝑣∈𝐶𝑐𝑣=∑𝑣∈𝐶∑𝑒∈𝛿(𝑣)𝑦𝑒≤2∑𝑒∈𝐸𝑦𝑒≤2OPT.

An edge contributes to at most two chosen endpoint costs. The factor two is a counting multiplicity, not a mysterious property of duality.

Set cover with bounded frequency

The set-cover dual assigns 𝑦𝑒 to elements, with ∑𝑒∈𝑆𝑦𝑒≤𝑐𝑆 for every set 𝑆. Raise uncovered-element duals until sets become tight, then select tight sets as needed. If each element belongs to at most 𝑓 sets, its dual weight can be charged at most 𝑓 times, yielding an 𝑓-approximation. Reverse deletion may be needed to control which tight sets remain selected.

Exact primal–dual algorithms

The same viewpoint can yield exact algorithms when integrality or problem structure closes the gap. Shortest-path labels act like feasible potentials; cuts bound flows; the Hungarian algorithm grows dual labels until equality edges support a larger matching. For this week, mastery means recognizing the dual-growth mechanism, not memorizing every exact algorithm.

Worked problem: A weighted vertex-cover runFact 51
On a path 𝑎−𝑏−𝑐 with costs (2,3,2), raise 𝑦(𝑎,𝑏) until 𝑎 becomes tight at value 2; choose 𝑎. Edge (𝑏,𝑐) remains uncovered. Vertex 𝑏 has residual dual capacity 1, while 𝑐 has 2, so raising 𝑦(𝑏,𝑐) by 1 makes 𝑏 tight; choose 𝑏. The cover costs 5, the dual value is 3, and the generic bound says 5≤6. The output need not be optimal for the approximation proof to be valid.
Worked problem: Deriving a frequency boundFact 52
Suppose every element lies in at most three selected tight sets. Tightness gives ∑𝑆∈𝐶𝑐𝑆=∑𝑆∈𝐶∑𝑒∈𝑆𝑦𝑒. Swap the sums: ∑𝑒𝑦𝑒|{𝑆∈𝐶:𝑒∈𝑆}|≤3∑𝑒𝑦𝑒. Weak duality then makes the cover a 3-approximation. The analysis depends only on charge multiplicity; if the algorithm selects arbitrarily many tight sets containing one element, the argument fails.
Easy — 2–5 minutes: Residual dual slackProposition 53

In weighted vertex cover, a vertex 𝑣 has cost 7 and incident dual variables currently sum to 5.5. By how much may an uncovered incident edge variable be raised before the constraint at 𝑣 becomes tight? Why must an algorithm also check the other endpoint?

Write the decisive idea before filling in algebra or pseudocode.

Medium — 15 minutes: Prove all four obligationsProposition 54

Write a rigorous proof of the weighted primal–dual vertex-cover algorithm. Separate termination, dual feasibility, primal feasibility, and the factor-two cost bound into four labeled claims.

Write the decisive idea before filling in algebra or pseudocode.

Hard — 45 minutes: Design from a covering LPProposition 55

Facilities have costs 𝑐𝑖 and cover client subsets 𝑁(𝑖). Every client must be covered, and each client belongs to at most 𝑓 facilities. Starting from the natural set-cover LP and dual, design a dual-growth algorithm, state a tie-handling rule, and prove an 𝑓-approximation. If you select every tight facility, explain whether reverse deletion changes feasibility or the bound. Your proof must derive the factor by swapping sums.

Write the decisive idea before filling in algebra or pseudocode.

Reductions

The direction is the first thing to write. To show that a target problem 𝐵 is hard, reduce a known hard problem 𝐴 to 𝐵: an algorithm for 𝐵 would then solve 𝐴. The construction alone is not the proof. You must establish the equivalence

𝑥∈𝐴⇔𝑓(𝑥)∈𝐵,

prove that 𝑓(𝑥) has polynomial encoding length and is computable in polynomial time, and explain how a solution is decoded when the reduction is between search or optimization problems.

Most gadget proofs are constraint simulations. First state the behavior a gadget must enforce, then prove a local lemma characterizing all feasible states of that gadget. Only after the local lemma should you compose gadgets and prove the two global directions. This modularity makes it much easier to detect unintended satisfying configurations.

A reduction transfers the ability to solve one problem into the ability to solve another. It is simultaneously an algorithm and a proof. The direction is easy to reverse accidentally: to use an algorithm for problem 𝐵 to solve problem 𝐴, transform instances of 𝐴 into instances of 𝐵. Symbolically,

𝐴≤𝑝𝐵

means that 𝐴 is no harder than 𝐵 under polynomial-time reductions. Thus if 𝐵∈𝑃, then 𝐴∈𝑃; if 𝐴 is NP-hard, then 𝐵 is NP-hard.

Many-one reductions

For decision problems, a polynomial-time many-one reduction is a function 𝑓 such that

𝑥∈𝐴⇔𝑓(𝑥)∈𝐵,

and 𝑓 is computable in time polynomial in |𝑥|. A complete proof contains:

  1. The construction of 𝑓(𝑥).
  2. A polynomial bound on the construction time and output size.
  3. The forward implication: a yes-certificate for 𝑥 yields one for 𝑓(𝑥).
  4. The reverse implication: a yes-certificate for 𝑓(𝑥) yields one for 𝑥.

The two directions often use different ideas. Similar-looking objectives or constraints do not establish equivalence.

Optimization and oracle reductions

Optimization problems may call a decision oracle multiple times. If a value is integer and polynomially bounded, binary search can often recover the optimum from a threshold-decision oracle. Recovering an actual witness usually requires self-reduction: tentatively fix one decision, query whether an optimum remains possible, and continue.

Record the number and size of oracle calls. Polynomially many calls on polynomial-size instances preserve polynomial time.

Gadget design

A gadget represents a logical choice, constraint, or interaction. Good gadgets have two properties:

  1. Completeness: every intended source assignment extends to a feasible target solution.
  2. Soundness: every relevant target solution decodes to a valid source assignment.

Unintended target configurations are the main source of incorrect reductions. Test gadgets locally before composing them, and state exactly how a target solution is decoded.

Weak versus strong NP-hardness

A reduction using numbers exponential in the source bit length may not be polynomial, even if writing the number in unary would make it look manageable. Pseudopolynomial algorithms are consistent with weak NP-hardness. Track bit length rather than numerical magnitude.

Worked problem: Independent set and vertex coverFact 56
For a graph 𝐺=(𝑉,𝐸) and integer 𝑘, 𝐺 has an independent set of size at least 𝑘 exactly when it has a vertex cover of size at most |𝑉|−𝑘. Map (𝐺,𝑘) to (𝐺,|𝑉|−𝑘). If 𝑆 is independent, no edge has both endpoints in 𝑆, so 𝑉−𝑆 covers every edge. Conversely, if 𝐶 is a vertex cover, no edge lies entirely within 𝑉−𝐶, so that complement is independent. The graph is unchanged and the threshold is computed in polynomial time.
Worked problem: Optimization from decisionFact 57
Suppose a decision oracle answers whether a graph has a vertex cover of size at most 𝑘. Binary search over 𝑘∈[0,|𝑉⟧ finds the optimum size using 𝑂(log|𝑉|) calls. To recover a cover, consider a vertex 𝑣. Query whether the current graph has an optimum cover avoiding 𝑣; equivalently, force every neighbor of 𝑣 into the cover and adjust the remaining budget. Depending on the answer, fix 𝑣 out or in and simplify. A rigorous self-reduction must specify these forced choices and maintain equivalence after each query.
Easy — 2–5 minutes: Reduction directionProposition 58

You know that Hamiltonian Cycle is NP-hard and construct a polynomial reduction Hamiltonian Cycle≤𝑝𝑋. What conclusion follows about 𝑋? What would a reduction in the reverse direction establish instead?

Write the decisive idea before filling in algebra or pseudocode.

Medium — 15 minutes: Clique and independent setProposition 59

Prove Clique≤𝑝Independent Set using graph complementation. State the mapping, prove both directions, and analyze the time required under adjacency- matrix and adjacency-list representations.

Write the decisive idea before filling in algebra or pseudocode.

Hard — 45 minutes: Three-dimensional matching to set packingProposition 60

In Three-Dimensional Matching, the input is a set 𝑇⊆𝑋×𝑌×𝑍 and an integer 𝑘; the question is whether there are at least 𝑘 triples no two of which share a coordinate. Set Packing asks whether a family of sets contains at least 𝑘 pairwise disjoint members. Give a formal polynomial-time reduction from Three-Dimensional Matching to Set Packing. Prove both directions and output-size bounds. Then explain why the superficially similar map that replaces each triple by its set of indices in the input list is unsound.

Write the decisive idea before filling in algebra or pseudocode.

Proof mechanics and invariants

At the start of every proof, classify the claim. A universal statement suggests an arbitrary object, induction, or a minimal counterexample. An existential statement suggests a constructive algorithm, a probabilistic argument, or an extremal choice. An equivalence requires two directions. An optimization claim requires both feasibility and a comparison with every competitor. This small classification step prevents many proofs from answering only half the question.

An invariant must be strong enough to imply the final result but weak enough to survive every transition. State it at a precise program point. The proof then has three parts: initialization before the first iteration, preservation from one iteration to the next, and use at termination. “The algorithm keeps making progress” is not an invariant until the preserved proposition and the well-founded progress measure are both named.

Proof ability is not a single talent. It is a sequence of controllable choices: parse the quantifiers, identify the mechanism, select a representation, state a strong enough intermediate claim, and audit every transformation. The purpose of this chapter is to make those choices explicit.

Direct proof, contrapositive, and contradiction

To prove 𝑃⇒𝑄 directly, assume 𝑃 and construct 𝑄. The contrapositive ¬𝑄⇒¬𝑃 is logically equivalent and is often easier when the failure of 𝑄 has concrete structure. Contradiction assumes 𝑃∧¬𝑄 and derives an impossibility. Use contradiction when the conflicting assumptions interact; do not use it merely to hide the desired conclusion.

For existence, distinguish constructive and nonconstructive proofs. An algorithm must usually do more than show that an object exists: it must expose how to find it and analyze the required resources.

Induction and strengthened claims

Induction succeeds when the statement is preserved by the recursive decomposition. If the inductive hypothesis lacks information needed at the next step, strengthen it. Typical strengthenings include:

  1. proving a claim for every prefix rather than only the full input;
  2. tracking both objective value and feasibility;
  3. allowing arbitrary boundary conditions;
  4. proving an invariant for every iteration;
  5. inducting simultaneously on two related quantities.

Strong induction is appropriate when a structure splits into pieces of unpredictable smaller sizes. It does not make an invalid recurrence valid: each piece must still be strictly smaller under the induction measure.

Loop invariants

A complete invariant proof has three parts:

  1. Initialization: it holds before the first iteration.
  2. Preservation: if it holds before an iteration, the iteration maintains it.
  3. Use at termination: invariant plus stopping condition implies the desired postcondition.

The invariant must mention the semantic object represented by mutable state. “The algorithm remains correct” is not an invariant. For BFS, a useful claim relates discovered distances to actual shortest paths and the queue order.

Disproof and proof auditing

To disprove ∀𝑥,𝑃(𝑥), one valid counterexample suffices. To refute an algorithmic guarantee, specify the input, trace the algorithm under its stated tie-breaking rules, compute its output, and compare with the required output. An intuition that the algorithm “might fail” is not a counterexample.

When auditing a proof, mark every sentence as one of: definition, assumption, previous result, algebraic consequence, or new claim needing justification. Most hidden gaps appear in the last category.

Worked problem: Strengthening an inductionFact 61
To prove that every tree on 𝑛 vertices has 𝑛−1 edges, remove a leaf 𝑣. The remaining graph must be known to be a tree, not merely a graph satisfying some numerical statement. Connectivity remains because a path between two remaining vertices never needs a leaf as an internal vertex; acyclicity is inherited. Strong enough structural information makes the induction close.
Worked problem: An invariant for insertion sortFact 62
Before iteration 𝑗, the subarray 𝐴[1…𝑗−1] contains exactly the original elements from those positions and is sorted. Initialization at 𝑗=2 is immediate. Inserting 𝐴[𝑗] shifts larger prefix elements right, preserving the multiset and producing a sorted prefix of length 𝑗. At termination the prefix is the entire array. Both sortedness and preservation of elements are needed; sortedness alone would allow an algorithm that overwrites every entry with zero.
Easy — 2–5 minutes: Negate preciselyProposition 63

Negate the following statement, moving every negation to an atomic predicate: “For every connected weighted graph, there exists a spanning tree such that for every non-tree edge, some edge on the induced cycle has no greater weight.”

Write the decisive idea before filling in algebra or pseudocode.

Medium — 15 minutes: Find the missing invariantProposition 64

Consider Euclid’s algorithm: while 𝑏≠0, replace (𝑎,𝑏) by (𝑏,𝑎mod𝑏). State and prove the invariant needed for correctness, then use the stopping condition to conclude that the output is gcd(𝑎,𝑏). Prove termination separately.

Write the decisive idea before filling in algebra or pseudocode.

Hard — 45 minutes: Majority candidate eliminationProposition 65

An array element is a majority if it occurs more than 𝑛2 times. Analyze the algorithm that maintains a candidate and counter, incrementing on a match, decrementing on a mismatch, and replacing the candidate when the counter is zero. Find a cancellation invariant that proves: if a majority exists, the final candidate is it. Explain why a second pass is still required when existence is not promised, and prove the 𝑂(𝑛) time and 𝑂(1) space bounds.

Write the decisive idea before filling in algebra or pseudocode.

Designing dynamic programs

A dynamic program is an induction whose hypotheses have been turned into table entries. The hard part is choosing the information retained at the boundary between the solved and unsolved parts. Too little information makes the future depend on hidden history; too much information makes the number of states explode. State design is therefore a sufficiency problem, not a notation problem.

Work backward from the last decision in an optimal solution. Ask what remains after fixing that decision and what facts about the removed portion can still affect the remainder. Those facts become state parameters. Then prove the recurrence in two directions: every optimal solution decomposes into one listed case, and combining optimal subsolutions from any listed case produces a feasible solution. The first direction prevents missing optima; the second prevents the recurrence from inventing infeasible ones.

Dynamic programming applies when an optimal or counting problem decomposes into overlapping subproblems whose interaction can be summarized by a compact boundary state. The hardest step is deciding what information the future needs from the past.

The design sequence

For every DP, write the following in order:

  1. State meaning: a complete sentence defining each entry.
  2. Structural choice: usually the first or last decision of an optimum.
  3. Recurrence: all possible cases for that decision.
  4. Base cases: including empty objects and impossible states.
  5. Evaluation order: a topological order of state dependencies.
  6. Answer location: the entry or aggregate that solves the original problem.
  7. Correctness: prove both that every recurrence choice is feasible and that every optimum is represented by some recurrence choice.
  8. Runtime: number of states times work per state, plus preprocessing and reconstruction.

State sufficiency

Two partial solutions may share a state only if every possible continuation interacts with them identically except through the stored value. This is the principle of optimality. When a proposed state is insufficient, construct two prefixes with the same recorded information but different best continuations.

More state makes correctness easier but runtime worse. DP design is therefore a compression problem: remember everything relevant and nothing else.

Correctness by optimal substructure

For a minimization recurrence

𝐷[𝑠]=min𝑎∈𝐴(𝑠)(𝑐(𝑠,𝑎)+𝐷[𝑁(𝑠,𝑎)]),

prove two inequalities. First, every action 𝑎 combined with an optimal subsolution gives a feasible solution, so the recurrence cannot be below the true optimum. Second, inspect the first action of an actual optimum; its remainder is feasible for the corresponding subproblem, so the recurrence cannot exceed the true optimum.

Common state geometries

  1. Prefixes: sequence alignment, knapsack, subsequences.
  2. Intervals: parenthesization, parsing, triangulation.
  3. Trees: condition on whether a node or boundary configuration is selected.
  4. Subsets: remember the chosen set and a small endpoint or status.
  5. Budgets: add a resource dimension, often yielding pseudopolynomial time.
Worked problem: Weighted interval schedulingFact 66

Sort intervals by finish time. Let 𝑝(𝑗) be the largest index 𝑖<𝑗 whose interval finishes before 𝑗 starts. Define 𝐷[𝑗] as the maximum weight of a compatible subset among intervals 1,…,𝑗. An optimum either excludes 𝑗, giving 𝐷[𝑗−1], or includes it, giving 𝑤𝑗+𝐷[𝑝(𝑗)]. Therefore

𝐷[𝑗]=max(𝐷[𝑗−1],𝑤𝑗+𝐷[𝑝(𝑗)]),𝐷[0]=0.

The two cases are exhaustive and each recurrence choice is feasible. Sorting and binary-search preprocessing take 𝑂(𝑛log𝑛); the DP takes 𝑂(𝑛).

Worked problem: Maximum-weight independent set on a treeFact 67

Root the tree. For each vertex 𝑣, let 𝐼[𝑣] be the best value in its subtree when 𝑣 is included and 𝐸[𝑣] the best when it is excluded. Then

𝐼[𝑣]=𝑤𝑣+∑𝑢∈𝐶(𝑣)𝐸[𝑢],𝐸[𝑣]=∑𝑢∈𝐶(𝑣)max(𝐼[𝑢],𝐸[𝑢]).

The state stores precisely the boundary fact a child needs: whether its parent is selected. A postorder traversal evaluates all children before their parent, and the runtime is Θ(|𝑉|).

Worked problem: Held–Karp subset DPFact 68

For a complete weighted graph with start vertex 𝑠, define 𝐷[𝑆,𝑣] as the minimum cost of a path starting at 𝑠, visiting exactly 𝑆, and ending at 𝑣, where 𝑠,𝑣∈𝑆. Then

𝐷[𝑆,𝑣]=min𝑢∈𝑆−{𝑣}(𝐷[𝑆−{𝑣},𝑢]+𝑤(𝑢,𝑣)).

The final tour cost is min𝑣≠𝑠(𝐷[𝑉,𝑣]+𝑤(𝑣,𝑠)). There are Θ(𝑛2𝑛) states and up to 𝑛 transitions per state, for 𝑂(𝑛22𝑛) time and 𝑂(𝑛2𝑛) space.

Easy — 2–5 minutes: DAG pathsProposition 69

Give a recurrence and evaluation order for counting the number of directed paths from 𝑠 to every vertex of a DAG. State the correct value at 𝑠 and at unreachable vertices.

Write the decisive idea before filling in algebra or pseudocode.

Medium — 15 minutes: Maximum-sum nonadjacent subsequenceProposition 70

Given possibly negative numbers 𝑎1,…,𝑎𝑛, find a maximum-sum subset of indices containing no adjacent pair. Design the DP, decide whether the empty set is allowed, prove the recurrence, and show how to reconstruct a solution.

Write the decisive idea before filling in algebra or pseudocode.

Hard — 45 minutes: Exact-change tree selectionProposition 71

You are given a rooted tree with nonnegative vertex profits and an integer 𝑘. Select exactly 𝑘 vertices forming a connected subgraph that contains the root and has maximum total profit. Design a polynomial-time DP. Define the state, explain how children are combined, prove correctness, and derive a runtime in terms of 𝑛, 𝑘, and the vertex degrees. A recurrence that merely says “try all connected sets” does not receive credit.

Write the decisive idea before filling in algebra or pseudocode.

Extremal and minimal-counterexample proofs

Extremality converts a global claim into local structure. Assuming a counterexample exists is not enough; choose one minimizing a parameter whose decrease corresponds to a simplifying operation you know how to perform. A minimum-vertex counterexample invites deletion, a minimum-edge connected counterexample invites cycle-edge removal, and a shortest bad cycle constrains possible chords. The extremal measure is part of the proof design.

After choosing the object, immediately write what minimality permits you to assert. If deleting a vertex preserves the theorem’s hypotheses, the smaller object satisfies the conclusion and can be extended back. If deletion does not preserve the hypotheses, that failure itself often forces the desired local structure. This is induction expressed in the language of obstructions.

An extremal proof converts a global theorem into local structure. Assume the claim fails, then choose a counterexample that is smallest, shortest, sparsest, densest, or otherwise extreme. The choice is useful only if modifying the object produces something to which extremality applies.

Quantifiers first

Before choosing a counterexample, negate the theorem correctly. The negation of

∀𝐺,𝑃(𝐺)⇒∃𝐻,𝑄(𝐺,𝐻)

is

∃𝐺,𝑃(𝐺)∧∀𝐻,¬𝑄(𝐺,𝐻).

A proof can fail before it begins if the chosen object is not actually a counterexample to the quantified claim.

Choosing the extremal measure

Common choices produce different consequences:

  1. A counterexample with the fewest vertices supports vertex deletion and induction on induced subgraphs.
  2. One with the fewest edges supports edge deletion and cycle elimination.
  3. A shortest path or cycle has no shortcut of the forbidden kind.
  4. A maximal partial solution cannot be extended, so every remaining object is blocked in some useful way.
  5. A minimum-cost counterexample may allow an uncrossing or exchange that preserves feasibility while improving cost.

Use lexicographic extremality when one measure is insufficient: first minimize vertices, and among those minimize edges. State the ordering explicitly.

The deletion-process equivalence

Many minimal-counterexample proofs can be read algorithmically. Repeatedly delete an object that violates the desired local structure. If the process deletes everything, summing what was removed contradicts the global assumption. If it stops early, the remainder has the desired property. The process and the extremal proof express the same mechanism in different forms.

Worked problem: Average degree forces a dense coreFact 72
Let 𝐺 have average degree at least 2𝑘, so |𝐸|≥𝑘|𝑉|. Repeatedly delete any vertex of degree at most 𝑘. If every vertex is deleted, charge each edge when its first endpoint is removed. At each deletion at most 𝑘 edges are charged, so initially |𝐸|≤𝑘|𝑉|. Under a strict average-degree assumption |𝐸|>𝑘|𝑉|, this is an immediate contradiction; under |𝐸|≥𝑘|𝑉|, equality requires every deletion to remove exactly 𝑘 edges, including the last nonempty stage, which is impossible. Thus a nonempty subgraph remains, and it has minimum degree at least 𝑘+1.
Worked problem: A shortest odd obstructionFact 73
Suppose a graph contains no odd cycle. In each connected component, choose a root and place every vertex into 𝐿0 or 𝐿1 according to the parity of its shortest-path distance from the root. If an edge (𝑢,𝑣) has endpoints of the same parity, combine shortest root-to-𝑢 and root-to-𝑣 paths with (𝑢,𝑣). After removing their common prefix, one obtains an odd cycle. Hence all edges cross between 𝐿0 and 𝐿1, proving bipartiteness. The shortest-path choice controls the shape of the alleged obstruction.
Easy — 2–5 minutes: Two leavesProposition 74

Prove that every finite tree with at least two vertices has at least two leaves. Use a longest simple path and state exactly why an endpoint cannot have another neighbor.

Write the decisive idea before filling in algebra or pseudocode.

Medium — 15 minutes: Minimal connected subgraphProposition 75

Choose a connected spanning subgraph with the fewest edges. Prove it is a tree, and hence prove that every finite connected graph has a spanning tree. Identify where connectedness is preserved after the proposed modification.

Write the decisive idea before filling in algebra or pseudocode.

Hard — 45 minutes: A degeneracy consequenceProposition 76

Suppose every nonempty subgraph of 𝐺 contains a vertex of degree at most 𝑑. Prove that 𝐺 is (𝑑+1)-colorable. Give both a minimal-counterexample proof and a deletion-order algorithm. Then prove that the algorithm runs in 𝑂(|𝑉|+|𝐸|) time when degrees are maintained in buckets. Carefully separate the structural proof from the data-structure analysis.

Write the decisive idea before filling in algebra or pseudocode.

Exchange arguments and greedy algorithms

An exchange proof does not show that a greedy choice looks reasonable. It shows that committing to the choice cannot destroy all optimal solutions. The clean invariant is usually: after the first 𝑖 greedy choices, there exists an optimal solution containing those choices. At the first disagreement with a fixed optimum, identify what is removed, what is inserted, why feasibility is preserved, and why the objective does not worsen.

Before proving a greedy rule, try to break it. Use the smallest instance on which the rule makes a forced first choice, then arrange the remaining objects so that this choice blocks a better combination. This does more than catch a false rule: it reveals which property a successful exchange would need. In matroids, the augmentation axiom supplies that property; ordinary graph independent sets lack it.

A greedy algorithm makes an irrevocable local choice. Its proof must establish that some optimum is compatible with that choice. An exchange argument does this by transforming an arbitrary optimum into another optimum that agrees with the greedy solution for one additional step.

The exchange template

Let the greedy choices be 𝑔1,𝑔2,…. Maintain the statement:

After the first 𝑖 greedy choices, there exists an optimal solution containing or agreeing with 𝑔1,…,𝑔𝑖.

For the next choice:

  1. Select an optimum 𝑂 agreeing with the established prefix.
  2. If 𝑔𝑖+1 is already used, continue.
  3. Identify an object 𝑜 in 𝑂 that conflicts with or replaces 𝑔𝑖+1.
  4. Define 𝑂′=𝑂−{𝑜}∪{𝑔𝑖+1} or the appropriate structured change.
  5. Prove 𝑂′ feasible and no worse than 𝑂.

An argument that says only “swap the choices” is missing the central proof. The swap may destroy feasibility elsewhere.

Staying-ahead arguments

Sometimes individual exchanges are awkward. Instead prove that after every prefix, the greedy solution is at least as advanced as any competitor. This is common in scheduling and path problems. Staying ahead is still structural: it defines an order in which partial solutions can be compared.

Counterexamples before proofs

Test a greedy rule on the smallest instances that contain a genuine conflict. For interval scheduling, two intervals are often too few: several short compatible intervals may need to compete with one long interval. For weighted problems, use one locally attractive object whose selection blocks several objects of slightly smaller individual value but larger total value.

Worked problem: Interval schedulingFact 77

The earliest-finish-time algorithm selects a compatible interval with minimum finish time, removes conflicting intervals, and repeats. Let 𝑔 be its first choice and let 𝑜 be the first interval in an optimal schedule 𝑂. Since 𝑔 finishes no later than 𝑜, replacing 𝑜 by 𝑔 leaves every later interval in 𝑂 feasible. The number of intervals is unchanged. Thus some optimum begins with 𝑔, and induction on intervals starting after 𝑔 proves optimality.

Notice that the relevant inequality compares finish times. Shorter length or earlier start does not imply that the remaining feasible region is larger.

Worked problem: The MST cut propertyFact 78
Let (𝑆,𝑉−𝑆) be a cut and let 𝑒 be a minimum-weight edge crossing it. Choose an MST 𝑇 containing as many already required edges as possible. If 𝑒∉𝑇, adding 𝑒 creates a cycle. That cycle crosses the cut at another edge 𝑓. Because 𝑒 is lightest across the cut, 𝑤(𝑒)≤𝑤(𝑓). Then 𝑇′=𝑇−𝑓+𝑒 is a spanning tree of no greater weight, hence also an MST, and it contains 𝑒. This is the exchange underlying Kruskal’s and Prim’s algorithms.
Easy — 2–5 minutes: Break a greedy ruleProposition 79

Give the smallest clear counterexample you can to the rule “for interval scheduling, repeatedly choose the shortest remaining interval.” Explain the failed structural comparison in one sentence.

Write the decisive idea before filling in algebra or pseudocode.

Medium — 15 minutes: Kruskal from the cut propertyProposition 80

Prove Kruskal’s algorithm correct. At each iteration, identify a cut crossed by the chosen edge but by no edge already in the forest. Your proof must also explain why accepting the edge does not create a cycle and why the final forest is spanning when the input is connected.

Write the decisive idea before filling in algebra or pseudocode.

Hard — 45 minutes: Greedy and abstract independenceProposition 81

An independence system is a pair (𝐸,ℐ︀) where ℐ︀ is nonempty and closed downward. Suppose it also satisfies: if 𝐴,𝐵∈ℐ︀ and |𝐴|<|𝐵|, then some 𝑒∈𝐵−𝐴 has 𝐴∪{𝑒}∈ℐ︀. Prove that sorting elements by nonincreasing nonnegative weight and greedily adding feasible elements returns a maximum-weight independent set. Use a sequence of exchanges or a prefix-rank argument. Then exhibit an independence system lacking the augmentation property on which greedy fails.

Write the decisive idea before filling in algebra or pseudocode.

Graph-theoretic algorithm design

Graph algorithms become easier to prove when each data structure is tied to a certificate. A BFS level is a certificate about the number of edges on a shortest unweighted path. A DFS finishing order certifies the absence or direction of certain unexplored edges. A spanning tree certifies connectivity; a cut with matching capacity certifies that a flow is optimal. State the certificate first, then show how the algorithm constructs it.

Representation is part of the runtime proof. With adjacency lists, scanning all neighbor lists costs Θ(|𝑉|+|𝐸|) in an undirected graph because every edge appears twice. With an adjacency matrix, merely looking for neighbors can cost Θ(|𝑉|) per vertex. Do not claim a graph runtime until the input model and the operations being counted are explicit.

Graph algorithms are organized around certificates. A traversal tree certifies reachability; a topological order certifies acyclicity; a cut can certify disconnection, an MST choice, or a flow upper bound; a negative cycle certifies that a shortest-path optimum is undefined.

Traversal and representation

With adjacency lists, breadth-first and depth-first search take Θ(|𝑉|+|𝐸|) time: each vertex is initialized or discovered a constant number of times, and each directed adjacency entry is inspected once. With an adjacency matrix, merely searching for neighbors can cost Θ(|𝑉|2). Runtime statements must specify the representation.

BFS discovers vertices in nondecreasing unweighted distance from the source. The proof uses the queue order: when a vertex at distance 𝑑 is processed, all undiscovered neighbors receive distance 𝑑+1, and no shorter path can reach them later. DFS instead exposes nesting, finish times, back edges, and decomposition structure.

DAGs and topological order

A directed graph is acyclic exactly when it has a topological ordering. Every finite DAG has a source: otherwise repeatedly follow an incoming edge, and a repeated vertex eventually creates a directed cycle. Deleting a source and recursing gives an ordering. Kahn’s algorithm implements this proof with indegrees; reverse DFS finish order gives another implementation.

Shortest paths

Dijkstra’s greedy step is valid with nonnegative edge weights. When a vertex 𝑢 of minimum tentative distance is finalized, any hypothetical shorter path to 𝑢 must first cross from the finalized set to an unfinalized vertex. The prefix to that first unfinalized vertex already has length at least the current minimum, and nonnegative remaining edges cannot repair the inequality.

Bellman–Ford uses a DP invariant instead: after 𝑖 complete relaxation rounds, distances are correct among paths with at most 𝑖 edges. A simple shortest path has at most |𝑉|−1 edges unless a reachable negative cycle allows indefinite improvement.

Flows and cuts

For an 𝑠–𝑡 flow 𝑓, conservation causes all internal contributions to cancel, so for every 𝑠–𝑡 cut (𝑆,𝑉−𝑆),

|𝑓|=𝑓(𝑆,𝑉−𝑆)−𝑓(𝑉−𝑆,𝑆)≤𝑐(𝑆,𝑉−𝑆).

Thus every cut capacity is an upper bound on every flow value. When an algorithm produces a flow and a cut of equal value, it has produced primal and dual-style certificates of optimality.

Worked problem: DAG shortest pathsFact 82
Topologically order the vertices. Set 𝑑[𝑠]=0 and all other distances to ∞. Process vertices in topological order, relaxing outgoing edges. Every predecessor of 𝑣 is processed before 𝑣, so when 𝑣 is reached, 𝑑[𝑣]=min(𝑢,𝑣)∈𝐸(𝑑[𝑢]+𝑤(𝑢,𝑣)). Induction over the topological order proves correctness. Negative edge weights cause no problem because no dependency can return to an earlier state.
Worked problem: A flow certificateFact 83
Suppose a feasible flow has value 12 and we find an 𝑠–𝑡 cut of capacity 12. Weak duality of flows and cuts says every flow has value at most 12. The displayed flow attains that upper bound, so both objects are optimal. No search over all alternative flows or cuts is needed; matching certificates settle optimality.
Easy — 2–5 minutes: Topological obstructionProposition 84

Prove that if Kahn’s topological-sort algorithm stops before outputting every vertex, then the remaining directed graph contains a cycle.

Write the decisive idea before filling in algebra or pseudocode.

Medium — 15 minutes: When Dijkstra failsProposition 85

Construct a three- or four-vertex directed graph with a negative edge but no negative cycle on which Dijkstra’s algorithm finalizes a wrong distance. Trace the algorithm, then identify the exact inequality in the usual proof that is invalidated.

Write the decisive idea before filling in algebra or pseudocode.

Hard — 45 minutes: Edge-disjoint pathsProposition 86

In a directed graph, assign capacity one to every edge. Prove that the maximum number of pairwise edge-disjoint 𝑠–𝑡 paths equals the minimum number of edges whose deletion separates 𝑠 from 𝑡. You may use max-flow/min-cut, but you must prove why an integral flow decomposes into paths and cycles and why the cycles can be discarded. Give the resulting polynomial-time algorithm and its runtime using a standard augmenting-path implementation.

Write the decisive idea before filling in algebra or pseudocode.

Time-complexity analysis with calculus

Calculus helps with algorithm analysis in three distinct ways. Integrals estimate nonuniform sums, derivatives locate the worst input parameter or best tuning parameter, and continuous approximations reveal the scale of a recurrence. In each case the continuous calculation proposes or bounds a discrete answer; floors, integer endpoints, and monotonicity still require a discrete justification.

For a monotone increasing nonnegative function 𝑓, rectangles give

∫1𝑛𝑓(𝑥)d𝑥≤∑𝑖=1𝑛𝑓(𝑖)≤𝑓(𝑛)+∫1𝑛𝑓(𝑥)d𝑥.

For decreasing 𝑓, the inequalities shift by one index. Draw the rectangles when uncertain. The integral is useful because it preserves how work varies with the loop index, whereas replacing every iteration by the maximum work can lose an entire logarithmic or polynomial factor.

Calculus becomes useful when a running time is expressed as a sum whose terms change smoothly. It provides bounds and asymptotic scale; it does not excuse us from first identifying what the algorithm counts.

Integral comparison

If 𝑓 is nonnegative and increasing, then rectangles give

∫0𝑛𝑓(𝑥)d𝑥≤∑𝑖=1𝑛𝑓(𝑖)≤∫1𝑛+1𝑓(𝑥)d𝑥.

If 𝑓 is nonnegative and decreasing, then

∫1𝑛+1𝑓(𝑥)d𝑥≤∑𝑖=1𝑛𝑓(𝑖)≤𝑓(1)+∫1𝑛𝑓(𝑥)d𝑥.

Therefore

∑𝑖=1𝑛1𝑖=Θ(log𝑛),∑𝑖=1𝑛𝑖=Θ(𝑛32),∑𝑖=1𝑛log𝑖=Θ(𝑛log𝑛).

For a runtime, a tight asymptotic bound requires both directions. An integral upper bound alone proves only 𝑂(𝑔(𝑛)).

Differentiation for worst-case parameters

Algorithms often have a tunable parameter 𝑏. If an upper bound is

𝐹(𝑏)=𝑛𝑏+𝑛2𝑏,

then treating 𝑏 temporarily as a positive real gives 𝐹′(𝑏)=𝑛−𝑛2𝑏2. The stationary point is 𝑏=𝑛, and 𝐹″(𝑏)=2𝑛2𝑏3>0, so it is a minimum. Rounding 𝑏 to a nearby integer changes the value only by a constant factor.

The arithmetic–geometric mean inequality gives the same conclusion: 𝑛𝑏+𝑛2𝑏≥2𝑛32. Calculus locates an optimum; an inequality can sometimes certify it more cleanly.

Continuous approximations and factorials

The logarithm of a product is a sum, and the sum can be integrated:

log(𝑛!)=∑𝑖=1𝑛log𝑖=𝑛log𝑛−𝑛+Θ(log𝑛).

The displayed refinement is Stirling-scale information. For most algorithm analysis, the weaker Θ(𝑛log𝑛) bound is sufficient. Use only the precision required by the problem.

Limits and hierarchy

L’Hopital’s rule can compare smooth extensions of functions, but elementary arguments are usually more robust. For every fixed 𝑎,𝑏>0,

(log𝑛)𝑎=𝑜(𝑛𝑏),

and for every fixed 𝑐>1 and 𝑏>0,

𝑛𝑏=𝑜(𝑐𝑛).

One proof sets 𝑛=𝑒𝑡: then (log𝑛)𝑎𝑛𝑏=𝑡𝑎𝑒𝑏𝑡, whose denominator eventually dominates every fixed-degree polynomial.

Worked problem: Harmonic inner loopFact 87

Suppose iteration 𝑖 performs ⌊𝑛𝑖⌋ operations. The total is ∑𝑖=1𝑛⌊𝑛𝑖⌋. Since 𝑛𝑖−1<⌊𝑛𝑖⌋≤𝑛𝑖,

𝑛𝐻𝑛−𝑛<∑𝑖=1𝑛⌊𝑛𝑖⌋≤𝑛𝐻𝑛,

where 𝐻𝑛=Θ(log𝑛). Hence the runtime is Θ(𝑛log𝑛). Keeping the floor changes the total by at most 𝑛.

Worked problem: Choosing a batch sizeFact 88
An algorithm preprocesses 𝑛𝑏 batches at cost 𝑛 per batch and later spends 𝑛𝑏 time scanning within batches. Its bound is 𝑇(𝑏)=𝑛2𝑏+𝑛𝑏. Differentiation gives 𝑏=𝑛 and 𝑇(𝑛)=2𝑛32. The endpoints are worse: 𝑏=1 or 𝑏=𝑛 yields Θ(𝑛2). Thus the stationary point is globally meaningful over 1≤𝑏≤𝑛.
Easy — 2–5 minutes: Integral scaleProposition 89

Use an integral comparison to obtain a tight asymptotic bound for ∑𝑖=1𝑛𝑖23.

Write the decisive idea before filling in algebra or pseudocode.

Medium — 15 minutes: Nested irregular loopProposition 90

An algorithm executes the inner statement for every pair (𝑖,𝑗) satisfying 1≤𝑖≤𝑛 and 1≤𝑗≤𝑛𝑖. Derive a tight runtime including a matching lower bound. Then explain why replacing every inner length by its maximum gives a valid but non-tight analysis.

Write the decisive idea before filling in algebra or pseudocode.

Hard — 45 minutes: Optimizing a three-term algorithmProposition 91

For 1≤𝑏≤𝑛, an algorithm has 𝑇(𝑏)=Θ(𝑛2𝑏+𝑛𝑏log𝑛+𝑏2). Determine an asymptotically optimal choice of 𝑏 and the resulting tight bound. Your solution must check whether the term ignored during any pairwise balancing becomes dominant, and must address the integer constraint on 𝑏.

Write the decisive idea before filling in algebra or pseudocode.

Review day: one integrated problem

Set aside four hours and use only the separate exam cheat sheet. Spend the first ten minutes reading every part and allocating time. This is one coherent network-design problem with several deliverables, not a list of unrelated short questions. If a later part depends on a result you could not prove, state the needed result and continue conditionally.

The resilient research network

A research consortium has an undirected connected graph 𝐺=(𝑉,𝐸). Edge 𝑒 has positive integer construction cost 𝑐𝑒 and integer latency ℓ𝑒∈{0,…,𝐿}. A distinguished vertex 𝑟 is the central cluster. Each vertex 𝑣 has nonnegative integer scientific value 𝑝𝑣 and generates one unit job per round. The consortium must construct a cheap backbone, select monitoring sites, route jobs, and predict congestion.

Part A: Backbone exchange proof

The consortium constructs a minimum-cost spanning tree using Kruskal’s algorithm. Give a complete exchange proof. Your invariant must say that after each accepted edge, some MST contains every accepted edge. When Kruskal considers an edge joining two forest components, explicitly identify the cut and the exchange edge. Analyze the runtime with adjacency-list input and a union–find implementation.

Then test the following alternative: “repeatedly select the cheapest edge incident to the most recently added vertex.” Either prove it or give a minimal counterexample.

Part B: Connected monitoring DP

Root the resulting tree 𝑇 at 𝑟. The consortium must select exactly 𝑘 vertices that induce a connected subgraph containing 𝑟, maximizing total scientific value. Design a tree DP.

Your answer must define a state for every subtree and budget, give the child- combination recurrence, handle impossible states, specify evaluation order, prove correctness in both directions, reconstruct the selected sites, and derive a polynomial runtime. Use a calculus or algebraic sum where needed to bound the total work over all child merges.

Part C: Coverage LP and primal–dual design

Now return to the original graph. Opening a monitoring site 𝑖 costs 𝑓𝑖 and covers a known neighborhood 𝑁(𝑖). Every vertex must be covered, and each vertex belongs to at most 𝑑 neighborhoods.

Formulate the minimum-cost covering LP and derive its dual. Design a dual- growth algorithm that raises uncovered-vertex variables until site constraints become tight. State how simultaneous tightness is handled. Prove dual feasibility, primal feasibility, termination, and a 𝑑-approximation by reordering a double sum. Explain what complementary slackness would require for the algorithm to be exact.

Finally, prove that the decision version of this monitoring problem is at least as hard as Set Cover by giving a polynomial reduction in the correct direction.

Part D: Latency distributions and FFT

Two independent subsystems produce integer delays with count arrays 𝑎0,…,𝑎𝐿 and 𝑏0,…,𝑏𝐿. The number of combined configurations with total latency 𝑡 is 𝑞𝑡=∑𝑖+𝑗=𝑡𝑎𝑖𝑏𝑗.

Design an FFT algorithm computing every 𝑞𝑡. Specify the encoded polynomials, padding length, transform operations, inverse normalization, and runtime. Explain exactly what incorrect quantity is computed if arrays are padded only to length 𝐿+1 and a cyclic transform is used.

Part E: Random job placement

In one round, 𝑛 vertices independently hash their jobs uniformly to 𝑛 identical servers.

  1. Compute the expected number of empty servers.
  2. Compute the expected number of colliding job pairs.
  3. Prove an upper bound of order log𝑛loglog𝑛 on maximum load with high probability. You may select the constant in the bound.
  4. If instead 𝑛log𝑛 jobs arrive, use a Chernoff bound and union bound to show that every server’s load is within a constant factor of its mean with high probability.

State every independence claim. In particular, do not call server loads independent.

Part F: Load repair potential

After hashing, the system repeatedly moves one job from a server of load at least two above another server to the less loaded server. Construct an integer potential that strictly decreases after every move. Prove termination and derive a polynomial upper bound on the number of moves from the initial load vector. Determine what property holds at termination.

Part G: Tail-bound comparison

Suppose server 𝑖 processes a random centered load perturbation 𝑋𝑖, the variables are independent, |𝑋𝑖|≤𝑏, and ∑𝑖Var(𝑋𝑖)=𝑉.

  1. Write the Chebyshev, range-based Hoeffding, and Bernstein upper bounds for Pr(∑𝑖𝑋𝑖≥𝑡), stating any extra information needed by Hoeffding.
  2. Identify the moderate-deviation regime in which Bernstein is controlled by 𝑉 and the far-tail regime in which it is controlled by 𝑏𝑡.
  3. Starting from exponential Markov, explain the role of the MGF and the free parameter 𝜆.

Part H: Proof audit

Choose the weakest of your Parts A–G. On a fresh page, write:

  1. the exact claim you attempted;
  2. the proof mechanism you selected;
  3. the first sentence that is not justified by a definition, assumption, or previous line;
  4. a lemma that would repair the gap;
  5. whether that lemma appears true, false, or unresolved.

This audit is part of the problem. A mathematically honest isolation of an obstruction is better evidence of proof ability than disguising the gap.

Oral defense

After correcting the written attempt, explain without notes:

  1. Why an exchange preserves an MST.
  2. Why the tree-DP state contains enough information.
  3. Why dual feasibility makes a lower-bound certificate.
  4. Why the approximation factor is a charging multiplicity.
  5. Why zero-padding prevents cyclic convolution.
  6. Why expected load does not determine maximum load.
  7. Why a decreasing potential proves termination but not automatically a fast runtime.

Final checklist

Before the exam, verify that you can reconstruct each item without notes:

  1. integral comparison for sums and differentiation for parameter tuning;
  2. minimal-counterexample and deletion-process proofs;
  3. exchange, staying-ahead, and counterexample arguments for greedy rules;
  4. BFS/DFS, topological ordering, shortest-path, MST, and flow certificates;
  5. DP state, recurrence, order, proof, runtime, and reconstruction;
  6. both directions and size analysis of a reduction;
  7. primal, dual, weak duality, complementary slackness, rounding, and gaps;
  8. dual growth, tight constraints, feasibility, and charging multiplicity;
  9. amortized-cost telescoping and termination potentials;
  10. DFT definition, even–odd recursion, inverse, padding, and convolution;
  11. indicator variables, occupancy, birthday collisions, coupon collection, and maximum load;
  12. exponential Markov, Chebyshev, Hoeffding, Chernoff, and Bernstein, including the assumptions that distinguish them.

The standard is not perfect recall. It is the ability to identify the right mechanism, expose all proof obligations, and recognize precisely where an unfinished argument stops.