TCS Cheat Sheet
Proof design
Quantifiers. Negate to , to , and move negations through the predicate. To refute a universal claim, one fully traced counterexample suffices.
Induction. State measure; base cases; assume claim for strictly smaller instances; prove structural pieces are smaller; reconstruct. Strengthen the claim when the hypothesis lacks boundary information.
Invariant. Initialization; preservation; invariant + termination implies postcondition. Prove termination separately.
Minimal counterexample. Assume failure; choose minimum under an explicit measure; delete/contract/split; apply minimality; reconstruct contradiction.
Proof audit. Label each step definition / assumption / prior theorem / algebra / unsupported claim. Isolate the first unsupported claim.
Algebra and calculus
; .
for .
.
.
For increasing : . For decreasing : .
; ; take logs before optimizing products/powers.
Parameter tuning: relax integer to real; solve ; check endpoints, second derivative or monotonicity; round and verify neglected terms.
Recurrence level : number of nodes times cost per node. Sum levels and leaves separately. For compare with , but expand when hypotheses are unclear.
Decrement recurrence: suggests and . Prove by comparison or substitution; the differential equation is a discovery tool.
Recursion-tree integral: if , summing over logarithmic levels uses measure . Write the discrete level sum before integrating.
Unequal branches: . Find from ; then expect under the usual regularity assumptions. Certify simple cases by substitution.
Substitution: calculus/expansion guesses the bound; induction proves it. If the induction does not close, retain lower-order slack before changing the guess.
Exchange and greedy
Invariant: after greedy choices, some optimum agrees with them. For next choice: choose such optimum ; identify conflicting ; define ; prove feasibility; prove value no worse; prove agreement increases.
MST cut property: a lightest edge crossing a cut is safe. Add it to an MST; remove another cycle edge crossing the cut with no smaller weight.
Before proving greedy, test: locally attractive object blocking several objects of larger total value; tie-breaking; zero/negative weights; smallest conflict.
Graph certificates
BFS/DFS on adjacency lists: . BFS certifies unweighted distance; DFS gives nesting/finish-time structure.
DAG iff topological order exists. Kahn: repeatedly remove indegree-zero vertex; early stop leaves a directed cycle.
Dijkstra: nonnegative weights; finalized minimum tentative distance is exact. Bellman–Ford invariant: after rounds, shortest paths using at most edges are correct.
Flow–cut: for every – cut. Equal feasible values certify optimality. Unit integral flow decomposes into paths and removable cycles.
Dynamic programming
Checklist: state meaning; last/first choice; recurrence; base/impossible states; dependency order; answer; two-direction correctness; states times work/state; reconstruction.
State sufficiency test: partial solutions placed in one state must have identical future interactions except through stored value.
Common geometries: prefix, interval, tree boundary condition, subset + endpoint, budget/resource. Budget DP may be pseudopolynomial.
Correctness: (1) each recurrence choice builds a feasible solution, so computed value cannot be improperly optimistic; (2) decompose an optimum by its decisive choice, so recurrence includes an equally good alternative.
Reductions
: transform instances of to ; if then ; if NP-hard then NP-hard.
Many-one proof: define ; polynomial construction and output size; ; reverse direction. Give decoding map. Track bit length, not numeric magnitude.
Optimization from decision: binary-search value if range supports it; recover a witness by self-reduction; count oracle calls and instance sizes.
Linear programming
Covering primal / packing dual:
s.t. ; s.t. .
Weak duality: . Say where nonnegativity is used.
Complementary slackness: and . Still prove feasibility.
Rounding minimization LP: . Integrality gap .
Primal–dual algorithms
Start dual feasible (); choose uncovered requirement; raise its dual until a constraint is tight; select/mark primal object; repeat; possibly reverse-delete.
Four claims: termination; dual feasibility; primal feasibility; cost bound. For selected tight objects, swap sums and bound how many times each is charged: .
Vertex-cover dual: s.t. . Each edge is charged to at most two selected endpoints -approximation.
Potential functions
.
. If , actual total amortized total.
Design: identify stored future liability; expensive step should release comparable potential. Check every operation type. Decreasing bounded potential proves termination; bound initial range and per-step decrease for runtime.
Multiplicative: implies .
FFT
DFT: .
.
, .
.
Inverse uses and factor . Convolution: pad to at least ; FFT both; pointwise multiply; inverse. Insufficient padding gives cyclic wraparound.
Balls and bins
balls, bins. Fixed load ; . Loads across bins are dependent.
.
.
No collision: ; threshold .
For : ; maximum load scale w.h.p.
Coupon collector expectation . Linearity of expectation never requires independence.
Exponential Markov and concentration
Markov: .
Exponential Markov: , in MGF domain. For lower tail apply to . Independence factors MGFs. Optimize exponent; every admissible already gives a valid bound.
Chebyshev: . For sums include covariance; pairwise independence makes covariances zero.
Hoeffding, independent : ; same lower tail.
Chernoff for independent Bernoulli sum, mean :
for .
for .
Bernstein, independent centered , :
.
MGF step: , . Choose .
Selection: only mean Markov; variance/no independence Chebyshev; independent ranges Hoeffding; Bernoulli relative deviation Chernoff; independent variance + range Bernstein.
Final proof checklist
What is random/optimized? What is the bad event? What are the quantifiers? What theorem hypotheses hold? What state/certificate is maintained? Does every transformation preserve feasibility? Why does it progress? Did I prove both directions? Are floors, ties, empty cases, signs, independence, and bit lengths handled? Number of states/iterations times work each? What is the first line I cannot justify?