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:
- Read the explanation actively. Re-derive every displayed equation.
- Cover the worked solution and attempt the problem for five minutes.
- Do the easy problem immediately, the medium problem under a 15-minute timer, and the hard problem under a 45-minute timer.
- When time expires, mark the precise obstruction before consulting notes.
- Rewrite one solution using the proof template below.
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
| Day | Primary work | Secondary work |
| Tuesday | Extremal arguments; exchange arguments | Graph theory; algebra |
| Wednesday | Dynamic programming; complexity with calculus | Recurrences; graph DPs |
| Thursday | LP proofs; primal–dual algorithms | Graph certificates; algebra |
| Friday | Potential functions; FFT | Balls and bins; probability review |
| Weekend | No work | Let consolidation happen |
| Monday | One integrated review problem | Correction and oral defense |
| Tuesday | Final exam | Fresh problems; closed notes |
Standards for a complete exam solution
A correct algorithmic answer contains four logically separate components:
- A precise algorithm or recurrence.
- A correctness argument covering every feasible output and every optimal solution, where appropriate.
- A termination or evaluation-order argument.
- 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:
- Write the quantifiers and negate the claim exactly.
- Test the smallest nontrivial instances and draw one example that is nearly false.
- Name what may change and what must be preserved under a modification.
- Propose three mechanisms: induction or extremality, exchange or local repair, and a numerical certificate such as a potential or dual solution.
- 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
and, for ,
The formula matters less than the scale. Thus , while . 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,
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
and, for ,
The first upper bound follows by comparing the derivative of with the derivative of . Such inequalities are the bridge between exact probabilities like and exponential approximations.
When manipulating asymptotic expressions, state the regime. For example, follows from
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:
- Expand enough levels to identify the sizes and multiplicities of subproblems.
- Express the work at one scale.
- Sum or integrate over the scales that actually occur.
- 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 steps to move through an interval of width , and each such step costs about . This suggests
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 , then and . The interpretation is concrete: when the current size is around , each step removes about , so roughly 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 . The answer follows from the finite sum : 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 and one unit of corresponds to a constant change in . Thus sums over recursion levels behave like integrals with measure , not :
That extra is why boundary terms such as behave differently from ordinary polynomial terms.
Unequal branches
For
there may be no uniform notion of a level. Find the exponent for which the total -mass of the children equals the parent’s:
If were proportional to , this equation would make recursive work balance. A continuous recursion-tree calculation then predicts
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 , 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.
Evaluate up to a tight asymptotic bound, and explain which level controls the sum.
Write the decisive idea before filling in algebra or pseudocode.
Solve 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.
Evaluate 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 work for every subset .
Write the decisive idea before filling in algebra or pseudocode.
Use the differential heuristic to guess a tight bound for . Then give a short discrete argument that the number of steps is both and .
Write the decisive idea before filling in algebra or pseudocode.
Solve 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.
Solve without using the Master theorem. First find the balance exponent from . 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 ,
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
so by linearity of expectation, without needing independence among bins,
Likewise, the probability that a specified pair of balls collides is . Summing pair indicators gives expected colliding pairs
This counts pairs, not the number of balls involved in any collision.
Birthday threshold
The probability of no collision among balls is
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
Choosing 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
This phase decomposition turns a dependent global process into waiting times whose expectations can be summed.
Throw 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.
Prove that if , the probability of any collision is . 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.
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 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 and ,
For any random variable and , monotonicity of the exponential makes nonnegative, so
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.
If , give an upper bound on without optimizing any parameter.
Write the decisive idea before filling in algebra or pseudocode.
Let be geometric with for . Compute its MGF and identify the range of for which it is finite. Apply exponential Markov to bound , and compare with the exact tail .
Write the decisive idea before filling in algebra or pseudocode.
Let satisfy for all real ; independence is not assumed. Use exponential Markov and a union bound to prove an upper-tail bound for . Then integrate or otherwise bound the tail to show . 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 :
Chebyshev needs only finite variance and no boundedness or independence. For a sum, compute variance carefully:
Independence makes covariance terms zero, but pairwise independence is already enough for this variance identity. Chebyshev usually gives polynomial rather than exponential decay.
If and , bound using Chebyshev.
Write the decisive idea before filling in algebra or pseudocode.
Let be pairwise independent Bernoulli() variables. Use Chebyshev to bound . Explain why mutual independence was not used.
Write the decisive idea before filling in algebra or pseudocode.
An unknown population has values in 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 ,
The same bound holds for the lower tail. Hoeffding’s lemma proves the centered MGF bound
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.
Let be independent Bernoulli(), , and . An incorrect majority implies . Since every range has length one, Hoeffding gives
The structural step is expressing the threshold as a deviation from the mean.
Independent . Bound .
Write the decisive idea before filling in algebra or pseudocode.
Independent measurements satisfy . Use Hoeffding to bound . 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.
Place each vertex of a graph independently on either side of a cut with probability . 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
for , and the convenient consequence
for . For the lower tail,
To derive the upper bound, independence gives
Exponential Markov at and the choice yield the exact multiplicative expression.
For a sum of independent Bernoulli variables with , bound using the convenient Chernoff upper tail.
Write the decisive idea before filling in algebra or pseudocode.
Starting from , differentiate with respect to , find the optimum, and derive . Check that the optimizer is admissible.
Write the decisive idea before filling in algebra or pseudocode.
Given fractional values with and , 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 .
Write the decisive idea before filling in algebra or pseudocode.
Bernstein’s inequality
Let independent centered variables satisfy , and write . Bernstein’s inequality states
It interpolates between a variance-controlled Gaussian regime and a range-controlled exponential regime .
The bounded-variable MGF proof begins with, for ,
so
Expanding the exponential series, using , and bounding the higher terms yields
for . Independence sums the variances in the exponent. Exponential Markov and the valid choice 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.
Let be independent Bernoulli() terminal decisions with weights , , and . Failure of a correct weighted majority is . Center for the lower tail. Then , , and . Bernstein gives
The quantities and distinguish diffuse from concentrated weight.
Independent centered satisfy and . Write Bernstein’s upper bound for without further simplification.
Write the decisive idea before filling in algebra or pseudocode.
Let independent equal with probability and otherwise. Compute their means, variances, and uniform bound. Write both Hoeffding and Bernstein bounds for , and identify a regime of small and moderate where Bernstein captures information Hoeffding ignores.
Write the decisive idea before filling in algebra or pseudocode.
Let independent centered satisfy . Starting from the power series for , prove the stated MGF bound, including the restriction . Apply exponential Markov to the sum, choose , 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
| Tool | Information | Typical tail | Use when |
| Markov | , mean | Only a first moment is available | |
| Chebyshev | Mean, variance | Dependence is allowed and variance is known | |
| Hoeffding | Independence, ranges | Variables are bounded; variances may be unknown | |
| Chernoff | Independent Bernoulli or suitable MGF | Relative deviations of counts | |
| Bernstein | Independence, variance, max range | 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:
- Amortization: expensive operations spend credit accumulated earlier.
- Termination: every operation strictly changes a bounded potential.
- 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
Summing telescopes:
If and , 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
then . Reaching takes steps. This is the deterministic analogue of many exponential tail calculations.
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.
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.
A dynamic table doubles when full and halves when its load falls below . Insertions and deletions cost one plus the number of copied items. Design a piecewise-linear nonnegative potential proving amortized cost per operation. Verify the analysis separately in the regimes above and below load , and explain why contracting at load 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 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:
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 be a primitive th root of unity. For coefficients , the discrete Fourier transform is
Thus for . Direct evaluation costs .
Important identities are
Distinct roots are orthogonal:
This geometric-sum identity explains the inverse transform.
Even–odd recursion
Split
At , both smaller polynomials are evaluated at . Moreover, the points for and have the same square and opposite signs. One pair of recursive transforms therefore produces two outputs:
The recurrence gives time for powers of two.
Inverse transform and convolution
The inverse DFT uses and divides by :
If , then at every evaluation point. Hence:
- zero-pad both coefficient arrays;
- compute their FFTs;
- multiply outputs coordinatewise;
- apply the inverse FFT.
If degrees are , use transform length at least . Insufficient padding computes cyclic convolution, causing high-degree coefficients to wrap around.
For , prove and . 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.
Compute the length-four DFT of using . Then recover the original coefficients with the inverse formula. Show every complex arithmetic step.
Write the decisive idea before filling in algebra or pseudocode.
Given , 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 to or .
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
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 give the first; and 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
for every primal constraint , and
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
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.
For a graph with costs , the relaxation is
Its dual assigns weight to edges:
The dual packs fractional edge weight into vertex capacities. For unit costs it is fractional matching. Rounding every upward covers each edge, because every edge constraint has at least one endpoint at least . Its cost is at most , giving a factor-two approximation.
Derive the dual of subject to , , and .
Write the decisive idea before filling in algebra or pseudocode.
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.
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:
- Start with , which is dual feasible.
- Choose an uncovered primal requirement.
- Raise its dual variable until some dual constraint becomes tight.
- Add the corresponding primal object or mark it eligible.
- Continue until all requirements are covered.
- Optionally reverse-delete redundant primal objects.
- Charge the primal cost to dual variables and bound the multiplicity.
The analysis has distinct proof obligations:
- Dual feasibility: no increase passes a constraint’s remaining slack.
- Primal feasibility: the stopping condition covers every requirement.
- Cost comparison: selected tight constraints express primal costs as dual contributions.
- Multiplicity bound: each dual contribution is charged at most times.
Then
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 . 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,
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.
In weighted vertex cover, a vertex has cost and incident dual variables currently sum to . 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.
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.
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:
- The construction of .
- A polynomial bound on the construction time and output size.
- The forward implication: a yes-certificate for yields one for .
- 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:
- Completeness: every intended source assignment extends to a feasible target solution.
- 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.
You know that Hamiltonian Cycle is NP-hard and construct a polynomial reduction . What conclusion follows about ? What would a reduction in the reverse direction establish instead?
Write the decisive idea before filling in algebra or pseudocode.
Prove 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.
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:
- proving a claim for every prefix rather than only the full input;
- tracking both objective value and feasibility;
- allowing arbitrary boundary conditions;
- proving an invariant for every iteration;
- 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:
- Initialization: it holds before the first iteration.
- Preservation: if it holds before an iteration, the iteration maintains it.
- 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.
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.
Consider Euclid’s algorithm: while , replace by . State and prove the invariant needed for correctness, then use the stopping condition to conclude that the output is . Prove termination separately.
Write the decisive idea before filling in algebra or pseudocode.
An array element is a majority if it occurs more than 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 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:
- State meaning: a complete sentence defining each entry.
- Structural choice: usually the first or last decision of an optimum.
- Recurrence: all possible cases for that decision.
- Base cases: including empty objects and impossible states.
- Evaluation order: a topological order of state dependencies.
- Answer location: the entry or aggregate that solves the original problem.
- Correctness: prove both that every recurrence choice is feasible and that every optimum is represented by some recurrence choice.
- 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
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
- Prefixes: sequence alignment, knapsack, subsequences.
- Intervals: parenthesization, parsing, triangulation.
- Trees: condition on whether a node or boundary configuration is selected.
- Subsets: remember the chosen set and a small endpoint or status.
- Budgets: add a resource dimension, often yielding pseudopolynomial time.
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 . An optimum either excludes , giving , or includes it, giving . Therefore
The two cases are exhaustive and each recurrence choice is feasible. Sorting and binary-search preprocessing take ; the DP takes .
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
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 .
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
The final tour cost is . There are states and up to transitions per state, for time and space.
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.
Given possibly negative numbers , 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.
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:
- A counterexample with the fewest vertices supports vertex deletion and induction on induced subgraphs.
- One with the fewest edges supports edge deletion and cycle elimination.
- A shortest path or cycle has no shortcut of the forbidden kind.
- A maximal partial solution cannot be extended, so every remaining object is blocked in some useful way.
- 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.
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.
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.
Suppose every nonempty subgraph of contains a vertex of degree at most . Prove that is -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 . Maintain the statement:
After the first greedy choices, there exists an optimal solution containing or agreeing with .
For the next choice:
- Select an optimum agreeing with the established prefix.
- If is already used, continue.
- Identify an object in that conflicts with or replaces .
- Define or the appropriate structured change.
- 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.
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.
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.
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.
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 . 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 , 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 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.
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.
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.
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
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
If is nonnegative and decreasing, then
Therefore
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
then treating temporarily as a positive real gives . The stationary point is , and , 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: . 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:
The displayed refinement is Stirling-scale information. For most algorithm analysis, the weaker 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 ,
and for every fixed and ,
One proof sets : then , whose denominator eventually dominates every fixed-degree polynomial.
Suppose iteration performs operations. The total is . Since ,
where . Hence the runtime is . Keeping the floor changes the total by at most .
Use an integral comparison to obtain a tight asymptotic bound for .
Write the decisive idea before filling in algebra or pseudocode.
An algorithm executes the inner statement for every pair satisfying and . 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.
For , an algorithm has . 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 . 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 and . 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 and a cyclic transform is used.
Part E: Random job placement
In one round, vertices independently hash their jobs uniformly to identical servers.
- Compute the expected number of empty servers.
- Compute the expected number of colliding job pairs.
- Prove an upper bound of order on maximum load with high probability. You may select the constant in the bound.
- If instead 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 .
- Write the Chebyshev, range-based Hoeffding, and Bernstein upper bounds for , stating any extra information needed by Hoeffding.
- Identify the moderate-deviation regime in which Bernstein is controlled by and the far-tail regime in which it is controlled by .
- 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:
- the exact claim you attempted;
- the proof mechanism you selected;
- the first sentence that is not justified by a definition, assumption, or previous line;
- a lemma that would repair the gap;
- 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:
- Why an exchange preserves an MST.
- Why the tree-DP state contains enough information.
- Why dual feasibility makes a lower-bound certificate.
- Why the approximation factor is a charging multiplicity.
- Why zero-padding prevents cyclic convolution.
- Why expected load does not determine maximum load.
- 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:
- integral comparison for sums and differentiation for parameter tuning;
- minimal-counterexample and deletion-process proofs;
- exchange, staying-ahead, and counterexample arguments for greedy rules;
- BFS/DFS, topological ordering, shortest-path, MST, and flow certificates;
- DP state, recurrence, order, proof, runtime, and reconstruction;
- both directions and size analysis of a reduction;
- primal, dual, weak duality, complementary slackness, rounding, and gaps;
- dual growth, tight constraints, feasibility, and charging multiplicity;
- amortized-cost telescoping and termination potentials;
- DFT definition, even–odd recursion, inverse, padding, and convolution;
- indicator variables, occupancy, birthday collisions, coupon collection, and maximum load;
- 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.