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

∑𝑖=1𝑛𝑖=𝑛(𝑛+1)2; ∑𝑖2=𝑛(𝑛+1)2𝑛+16.

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

𝐻𝑛=∑𝑖=1𝑛1𝑖=ln𝑛+Θ(1).

∑𝑆⊆[𝑛]|𝑆|=𝑛2𝑛−1.

For increasing 𝑓≥0: ∫0𝑛𝑓≤∑𝑖=1𝑛𝑓(𝑖)≤∫1𝑛+1𝑓. For decreasing 𝑓≥0: ∫1𝑛+1𝑓≤∑𝑓(𝑖)≤𝑓(1)+∫1𝑛𝑓.

ln(1+𝑥)≤𝑥; 1−𝑥≤𝑒−𝑥; take logs before optimizing products/powers.

Parameter tuning: relax integer 𝑏 to real; solve 𝐹′(𝑏)=0; 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 𝑛log𝑏𝑎, but expand when hypotheses are unclear.

Decrement recurrence: 𝑇(𝑛)=𝑇(𝑛−ℎ(𝑛))+𝑔(𝑛) suggests 𝑇′(𝑛)≈𝑔(𝑛)ℎ(𝑛) and 𝑇(𝑛)≈∫1𝑛𝑔(𝑥)ℎ(𝑥)d𝑥. Prove by comparison or substitution; the differential equation is a discovery tool.

Recursion-tree integral: if 𝑥=𝑛𝑏𝑗, summing over logarithmic levels uses measure d𝑥𝑥. Write the discrete level sum before integrating.

Unequal branches: 𝑇(𝑛)=∑𝑖𝑎𝑖𝑇(𝑏𝑖𝑛)+𝑔(𝑛). Find 𝑝 from ∑𝑖𝑎𝑖𝑏𝑖𝑝=1; then expect 𝑇(𝑛)=Θ(𝑛𝑝(1+∫1𝑛𝑔(𝑢)𝑢𝑝+1d𝑢)) 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:

min𝑐𝑇𝑥 s.t. 𝐴𝑥≥𝑏,𝑥≥0; max𝑏𝑇𝑦 s.t. 𝐴𝑇𝑦≤𝑐,𝑦≥0.

Weak duality: 𝑏𝑇𝑦≤(𝐴𝑥)𝑇𝑦=𝑥𝑇𝐴𝑇𝑦≤𝑥𝑇𝑐. Say where nonnegativity is used.

Complementary slackness: 𝑦𝑖((𝐴𝑥)𝑖−𝑏𝑖)=0 and 𝑥𝑗(𝑐𝑗−(𝐴𝑇𝑦)𝑗)=0. Still prove feasibility.

Rounding minimization LP: cost(𝑋)≤𝛼LP≤𝛼OPTint. Integrality gap =OPTintOPTLP.

Primal–dual algorithms

Start dual feasible (𝑦=0); 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: 𝑐𝑇𝑥≤𝛼𝑏𝑇𝑦≤𝛼OPT.

Vertex-cover dual: max∑𝑒𝑦𝑒 s.t. ∑𝑒∈𝛿(𝑣)𝑦𝑒≤𝑐𝑣. Each edge is charged to at most two selected endpoints ⇒2-approximation.

Potential functions

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

∑𝑐𝑖=∑𝑐̂𝑖+Φ(𝐷0)−Φ(𝐷𝑚). If Φ(𝐷0)=0,Φ≥0, 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: Φ𝑡+1≤(1−𝛿)Φ𝑡 implies Φ𝑡≤𝑒−𝛿𝑡Φ0.

FFT

DFT: 𝑦𝑘=∑𝑗=0𝑛−1𝑎𝑗𝜔𝑛𝑗𝑘=𝐴(𝜔𝑛𝑘).

𝐴(𝑥)=𝐴𝐸(𝑥2)+𝑥𝐴𝑂(𝑥2).

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

𝑇(𝑛)=2𝑇(𝑛2)+Θ(𝑛)=Θ(𝑛log𝑛).

Inverse uses 𝜔𝑛−1 and factor 1𝑛. Convolution: pad to at least 𝑑𝐴+𝑑𝐵+1; FFT both; pointwise multiply; inverse. Insufficient padding gives cyclic wraparound.

Balls and bins

𝑚 balls, 𝑛 bins. Fixed load 𝐿𝑗∼Bin(𝑚,1𝑛); 𝔼[𝐿𝑗]=𝑚𝑛. Loads across bins are dependent.

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

𝔼[colliding pairs]=(𝑚2)𝑛.

No collision: ∏𝑖=0𝑚−1(1−𝑖𝑛)≤𝑒−𝑚(𝑚−1)2𝑛; threshold 𝑛.

For 𝑚=𝑛: Pr(max𝑗𝐿𝑗≥𝑘)≤𝑛(𝑒𝑘)𝑘; maximum load scale Θ(log𝑛loglog𝑛) w.h.p.

Coupon collector expectation 𝑛𝐻𝑛=Θ(𝑛log𝑛). Linearity of expectation never requires independence.

Exponential Markov and concentration

Markov: 𝑌≥0⇒Pr(𝑌≥𝑎)≤𝔼[𝑌]𝑎.

Exponential Markov: Pr(𝑋≥𝑡)≤𝑒−𝜆𝑡𝔼[𝑒𝜆𝑋], 𝜆>0 in MGF domain. For lower tail apply to −𝑋. Independence factors MGFs. Optimize exponent; every admissible 𝜆 already gives a valid bound.

Chebyshev: Pr(|𝑋−𝜇|≥𝑡)≤Var(𝑋)𝑡2. For sums include covariance; pairwise independence makes covariances zero.

Hoeffding, independent 𝑋𝑖∈[𝑎𝑖,𝑏𝑖]: Pr(𝑆−𝔼[𝑆]≥𝑡)≤exp(−2𝑡2∑𝑖(𝑏𝑖−𝑎𝑖)2); same lower tail.

Chernoff for independent Bernoulli sum, mean 𝜇:

Pr(𝑋≥(1+𝛿)𝜇)≤(𝑒𝛿(1+𝛿)1+𝛿)𝜇≤𝑒−𝛿2𝜇3 for 0≤𝛿≤1.

Pr(𝑋≤(1−𝛿)𝜇)≤𝑒−𝛿2𝜇2 for 0≤𝛿≤1.

Bernstein, independent centered |𝑋𝑖|≤𝑏, 𝑉=∑𝑖Var(𝑋𝑖):

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

MGF step: 𝔼[𝑒𝜆𝑋𝑖]≤exp(𝜆2Var(𝑋𝑖)2(1−𝜆𝑏3)), 0<𝜆<3𝑏. Choose 𝜆=𝑡𝑉+𝑏𝑡3.

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?