7.1.1 — Master Rule Sheet (all rule cards merged)

Every Rule Card from the 47 lessons, grouped by phase, in course order. Use it for revision in the last weeks: read one phase per sitting, and for any line you cannot explain in your own words, open its lesson (the lesson ID links to it).

📝

How to revise with this sheet

• Cover the rules of a lesson with your hand; say them from its title alone.
• Check, and mark the lesson's ID on paper if you missed anything.
• Next day, re-test only the marked IDs (spaced recall).

🧭 Phase 0 · Foundations

0.1.1 Problems, instances and algorithms; correctness; counting basic steps

• Problem (what), instance (one input), algorithm (finite precise steps for all instances).
• Correct = halts with correct output on every instance; loop invariants prove it.
• RAM model: each basic operation = 1 step; T(n) = steps for input size n.
• Loop counts: step k from a to b → ⌊(b − a)/k⌋ + 1 runs; nested loops multiply.

0.1.2 Math toolkit: logarithms, floors and ceilings, sums (arithmetic, geometric, harmonic)

• log = log₂; bases differ by constants; a^(log_b n) = n^(log_b a).
• Halving to 1: ⌊log n⌋ steps; n has ⌊log n⌋ + 1 bits; doubling to ≥ n: ⌈log n⌉.
• Σi = n(n+1)/2; Σi² = n(n+1)(2n+1)/6; Σ2ⁱ (0..k) = 2ᵏ⁺¹ − 1; Hₙ ≈ ln n; log n! ≈ n log n.
• Decreasing geometric series: constant.

0.2.1 Arrays, linked lists, stacks and queues: what each operation costs

• Array: index O(1); insert/delete at k: n − k shifts; search unsorted n.
• Singly linked: front ops constant; delete needs predecessor; last node costs n.
• Doubly linked with tail: delete given node / last node constant.
• Stack push/pop and queue enqueue/dequeue (circular array or tail pointer): constant.

0.2.2 Trees, binary search trees and binary heaps: heights and operation costs

• Height h (edges): ≤ 2ⁱ nodes at level i; ≤ 2ʰ⁺¹ − 1 nodes; n nodes → h ≥ ⌊log n⌋.
• BST: left < node < right; operations O(h); inorder = sorted; sorted inserts make a chain.
• Max-heap: complete tree, parent ≥ children; 1-based children 2i, 2i+1, parent ⌊i/2⌋; leaves ⌊n/2⌋+1..n.
• Heap: max O(1); insert/extract O(log n); build O(n).

0.2.3 Graphs: vocabulary, adjacency matrix vs adjacency list

• Σ degrees = 2E (undirected); Σ in = Σ out = E (directed).
• Tree: connected, acyclic, n − 1 edges. Max edges: n(n−1)/2 undirected, n(n−1) directed.
• Matrix: Θ(V²) space, O(1) edge test. List: Θ(V + E) space, O(deg) neighbours, O(V + E) scan.

📈 Phase 1 · Asymptotic Analysis & Recurrences

1.1.1 Big-O, Big-Ω and Θ: definitions with constants

• O: f ≤ c·g eventually. Ω: f ≥ c·g eventually. Θ: both.
• Drop constant factors and lower-order terms; polynomial degree d → Θ(nᵈ).
• Log bases don't matter; exponential bases and exponent constants do.
• O and Ω need not be tight.

1.1.2 Little-o and little-ω; comparing and ordering functions

• o: f/g → 0; ω: f/g → ∞; constant limit → Θ.
• Compare logs when stuck (but equal logs ≠ equal growth).
• Ladder: 1 < log log n < log n < polylog < n^ε < n < n log n < n² < … < n^(log n) < 2ⁿ < 3ⁿ < n! < nⁿ.
• n^(1/log n) = 2; log n! = Θ(n log n); transitivity, reflexivity, symmetry (Θ), transpose (O/Ω).

1.1.3 Analysing loops: nested, dependent and logarithmic loops

• Inner i → n²/2; inner log i → n log n; inner n/i → n log n; inner log n → n log n.
• Doubling single loop log n; squaring log log n; i² ≤ n → √n.
• Doubling outer loop with inner up to i → Θ(n).
• i < j < k triple loop → C(n, 3) = Θ(n³).

1.2.1 Recurrences from recursive code; solving by unrolling (substitution)

• T(n) = Σ recursive calls + outside work; base case.
• T(n−1)+c → n; T(n−1)+n → n²; T(n/2)+c → log n; 2T(n/2)+n → n log n; 2T(n−1)+1 → 2ⁿ − 1.
• Unroll, find the pattern, sum; for exact values compute bottom-up.

1.2.2 The recursion-tree method

• Level i: aⁱ nodes of size n/bⁱ; cost aⁱ·f(n/bⁱ); depth log_b n; leaves n^(log_b a).
• Shrinking levels → Θ(f(n)); equal → Θ(f(n) log n); growing → Θ(n^(log_b a)).
• Unequal splits: fractions sum to 1 → n log n; less than 1 → n (for f = n).

1.2.3 The master theorem

• T(n) = aT(n/b) + f(n); w = n^(log_b a).
• f = O(w/n^ε) → Θ(w); f = Θ(w logᵏ n), k ≥ 0 → Θ(w logᵏ⁺¹ n); f = Ω(w·n^ε) + regularity → Θ(f).
• f = nᵈ: compare a with bᵈ.
• Not for T(n−1), a < 1, gaps (n/log n), non-constant a.

1.2.4 Harder recurrences: change of variables, T(n−1) forms, unequal splits

• T(n^(1/k)) → set m = log n; T(√n) + 1 → log log n; 2T(√n) + 1 → log n; 2T(√n) + log n → log n log log n.
• T(n−1) + f → Σ f; a·T(n−1) with a > 1 → exponential; Fibonacci → φⁿ.
• Uneven splits: fractions sum 1 → n log n; < 1 → n (for f = n).
• Substitution: guess, then prove by induction.

1.3.1 Best, worst and average case; space complexity and recursion depth; amortised cost

• Worst (default), best, average (needs a distribution).
• Linear search: 1 / n / (n+1)/2.
• Space: auxiliary memory + recursion depth × frame; in-place = O(1).
• Amortised = total ÷ operations; doubling array O(1) amortised (copies < 2n).

🔍 Phase 2 · Searching & Hashing

2.1.1 Linear search and binary search: comparisons and correctness

• Linear search: Θ(n); best 1, worst n, average (n+1)/2.
• Binary search: sorted + random access; ≤ ⌊log n⌋ + 1 probes; Θ(log n); iterative O(1) space.
• Invariant: x, if present, lies in A[lo..hi]. mid = ⌊(lo+hi)/2⌋.
• On a linked list binary search is Θ(n).

2.1.2 Binary search variants and the Ω(log n) lower bound for searching

• First occurrence: equal → record, go left. Last: equal → record, go right. Count = last − first + 1.
• Lower bound: first index with A[i] ≥ x (the final lo).
• Rotated array: one half is sorted at every step.
• Comparison-based search: Ω(log n) (decision tree with ≥ n leaves).

2.2.1 Hash tables, hash functions, load factor; separate chaining

• h(k) = k mod m (m prime); multiplication method ⌊m·frac(kA)⌋.
• α = n/m. Chaining: insert O(1); unsuccessful search expected α keys (Θ(1 + α)); successful ≈ 1 + α/2.
• Worst case Θ(n). α > 1 allowed.

2.2.2 Open addressing: linear probing, quadratic probing, double hashing

• Linear: (h + i) mod m; quadratic: (h + c₁i + c₂i²) mod m; double: (h₁ + i·h₂) mod m.
• Insert at the first empty slot; search until key or empty slot; deletion uses tombstones.
• Linear → primary clustering; quadratic → secondary; double hashing avoids both (h₂ coprime to m).
• Probe count includes the home slot.

2.2.3 Expected probes and collision probabilities

• Open addressing (uniform): unsuccessful ≤ 1/(1−α); successful ≤ (1/α)ln(1/(1−α)).
• Chaining: unsuccessful Θ(1 + α); successful ≈ 1 + α/2.
• P(no collision) = m(m−1)…(m−n+1)/mⁿ; P(k given slots empty) = (1 − k/m)ⁿ.
• E[empty slots] = m(1 − 1/m)ⁿ; E[colliding pairs] = C(n,2)/m.

🔢 Phase 3 · Sorting

3.1.1 Bubble sort and selection sort: passes, comparisons, swaps

• Bubble: adjacent swaps; pass k fixes the k-th largest; comparisons ≤ n(n−1)/2; best n − 1 (early exit); swaps = inversions; stable, in-place.
• Selection: min of the rest into place; always n(n−1)/2 comparisons; ≤ n − 1 swaps; in-place, not stable.

3.1.2 Insertion sort and inversions; stable and in-place sorting

• Insertion: insert A[i] into sorted prefix by shifting. Shifts = inversions; Θ(n + I).
• Best Θ(n) (sorted), worst Θ(n²) (reverse, I = n(n−1)/2), average n²/4.
• Binary insertion: O(n log n) comparisons, Θ(n²) shifts.
• Stable: insertion, bubble, merge, counting. In-place: bubble, selection, insertion, heap, quick.

3.2.1 Merge sort: merging, recurrence, comparison counts

• Merge p + q: ≤ p + q − 1 comparisons, ≥ min(p, q).
• Merge sort: Θ(n log n) all cases; Θ(n) extra space; stable; depth ⌈log n⌉.
• Worst comparisons W(n) = W(⌈n/2⌉) + W(⌊n/2⌋) + n − 1; n = 2ᵏ → n log n − n + 1.
• Bottom-up: ⌈log n⌉ passes.

3.2.2 Quicksort: partitioning, best, worst and average cases

• Lomuto: pivot = last; n − 1 comparisons; pivot ends in its final place.
• Best/average Θ(n log n); worst Θ(n²) (sorted or reverse with end pivot; all-equal with Lomuto).
• Constant-fraction splits → Θ(n log n). Median pivot (Θ(n)) → worst Θ(n log n).
• In-place, not stable; stack O(log n) best, O(n) worst.

3.2.3 Heapsort: build-heap in O(n), heapify, extract-max

• Sift down: swap with the larger child until in place.
• Build-heap bottom-up from ⌊n/2⌋ to 1: Θ(n). Repeated insertion: O(n log n).
• Heapsort: build, then n − 1 × (swap root with last, sift down): Θ(n log n) all cases; in-place; not stable.
• Max-heap check: A[⌊i/2⌋] ≥ A[i].

3.3.1 The Ω(n log n) lower bound for comparison sorting; comparing all sorts

• Comparison sorting needs ≥ ⌈log n!⌉ = Ω(n log n) comparisons (worst and average).
• Merge sort and heapsort are optimal; quicksort optimal on average.
• Table: insertion for nearly sorted; heapsort for O(1) space; merge for stable; quicksort fastest on average.

3.3.2 Counting sort, radix sort and bucket sort

• Counting sort: counts, prefix sums, place right-to-left; Θ(n + k); stable; needs k = O(n).
• LSD radix: stable digit sorts, least significant first; Θ(d(n + b)).
• Bucket sort: uniform keys, average Θ(n), worst Θ(n²).
• Non-comparison sorts escape the n log n bound.

3.3.3 Selection: minimum and maximum, second largest, k-th smallest

• Min (or max): n − 1. Min and max: 3n/2 − 2 (n even), 3⌊n/2⌋ (n odd).
• Second largest: n + ⌈log n⌉ − 2 (tournament).
• Quickselect: average Θ(n), worst Θ(n²). Median of medians: worst Θ(n).
• k smallest with a heap: Θ(n + k log n).

✂️ Phase 4 · Divide & Conquer and Greedy

4.1.1 Divide and conquer: fast exponentiation, counting inversions, maximum subarray

• D&C: divide into a pieces of size n/b, conquer, combine in f(n): T = aT(n/b) + f(n).
• Fast power: Θ(log n) multiplications (squarings + one per odd step).
• Inversions via merge: add remaining-left count; Θ(n log n).
• Max subarray D&C: left, right, crossing; Θ(n log n).

4.1.2 Karatsuba and Strassen multiplication; closest pair (brief)

• Karatsuba: 3T(n/2) + n → n^(log 3) ≈ n^1.585; 3ᵏ digit products for n = 2ᵏ.
• Strassen: 7T(n/2) + n² → n^(log 7) ≈ n^2.81; 7ᵏ scalar products.
• Block matrix with 8 products: n³. Closest pair: n log n.
• Fewer subproblems → smaller exponent.

4.2.1 The greedy method; activity selection

• Greedy: locally best choice, never undone; needs greedy-choice property + optimal substructure; prove by exchange.
• Activity selection: sort by finish; pick if start ≥ last finish; Θ(n log n).
• Shortest-first, earliest-start, fewest-conflicts can fail.

4.2.2 Fractional knapsack; job sequencing with deadlines

• Fractional knapsack: sort by v/w; fill greedily; last item fractional; optimal; Θ(n log n).
• 0/1 knapsack: greedy fails → DP.
• Job sequencing (unit jobs): profit descending; latest free slot ≤ deadline; optimal.

4.2.3 Huffman coding

• Prefix-free code ↔ binary tree; length = depth.
• Huffman: repeatedly merge the two smallest weights; Θ(n log n); optimal.
• Cost = Σ f·len = Σ merge weights; average = cost / Σ f.
• Ties: different codes, same cost.

4.2.4 Optimal merge pattern; when greedy fails

• Optimal merge: repeatedly merge the two smallest (min-heap); cost = Σ merges; = Huffman.
• Greedy fails: 0/1 knapsack, coin change with non-canonical coins, shortest-first activities, nearest-neighbour paths.
• Canonical coin systems: greedy works.

🧩 Phase 5 · Dynamic Programming

5.1.1 Overlapping subproblems: memoisation vs tabulation; counting calls

• DP = optimal substructure + overlapping subproblems.
• Memoisation (top-down, store results) vs tabulation (bottom-up order).
• Time = #subproblems × time each. Naive fib calls = 2F(n+1) − 1; memoised Θ(n).
• Recipe: subproblem, recurrence, base, order, answer.

5.1.2 0/1 knapsack

• K[i][w] = max(K[i−1][w], vᵢ + K[i−1][w − wᵢ]) if wᵢ ≤ w, else K[i−1][w].
• Θ(nW) time; pseudo-polynomial; one row right-to-left.
• Reconstruct: item i taken iff K[i][w] ≠ K[i−1][w].

5.1.3 Longest common subsequence

• L[i][j] = L[i−1][j−1] + 1 on match; else max(L[i−1][j], L[i][j−1]); zeros on the borders.
• Θ(mn); reconstruct from (m, n); ties give multiple LCSs.
• Common substring: diagonal + 1 on match, else 0.

5.2.1 Matrix-chain multiplication

• m[i][i] = 0; m[i][j] = min_k (m[i][k] + m[k+1][j] + p_{i−1}p_k p_j).
• Fill by chain length; s[i][j] stores the best k.
• Θ(n³) time, Θ(n²) space; parenthesisations C_{n−1}.

5.2.2 Subset sum, coin change and rod cutting

• Subset sum: R[x] |= R[x − s], x downward; Θ(n·t). Counting: +=.
• Coin ways: coins outer, amounts upward: W[x] += W[x − c].
• Min coins: D[x] = 1 + min D[x − c].
• Rod cutting: R[j] = max(pᵢ + R[j − i]); Θ(n²).

5.2.3 Longest increasing subsequence, edit distance and other sequence DPs

• LIS: L[i] = 1 + max L[j] (j < i, A[j] < A[i]); answer max L[i]; Θ(n²) (n log n possible).
• Edit distance: min(delete, insert, substitute/match); borders i and j; Θ(mn).
• BSTs on n keys: Catalan Cₙ.

🕸️ Phase 6 · Graph Algorithms

6.1.1 Breadth-first search: levels and unweighted shortest paths

• BFS: queue; mark on enqueue; levels in non-decreasing order.
• dist = fewest edges (unweighted shortest path); BFS tree has V − 1 edges (connected).
• Undirected non-tree edges join levels differing by ≤ 1.
• Θ(V + E) lists, Θ(V²) matrix.

6.1.2 Depth-first search: discovery and finish times, edge classification

• DFS: d[u] on discovery, f[u] on finish; times 1 … 2V; Θ(V + E).
• Parenthesis: intervals nested or disjoint; descendant ⇔ d[u] < d[v] < f[v] < f[u].
• Tree (white), back (grey), forward (black descendant), cross (black, d[v] < d[u]).
• Directed cycle ⇔ back edge. Undirected: only tree and back.

6.1.3 Topological sort, cycle detection, connected and strongly connected components

• Topological order (DAG only): decreasing finish time, or Kahn (in-degree 0); Θ(V + E).
• Cycle: back edge (directed), visited non-parent (undirected), Kahn stalls.
• Components: one BFS/DFS start per component; forest has V − E.
• SCCs (Kosaraju): DFS, reverse edges, DFS by decreasing finish; condensation is a DAG.

6.2.1 Minimum spanning trees: cut and cycle properties, uniqueness

• Spanning tree: V − 1 edges; Kₙ has nⁿ⁻² spanning trees.
• Cut property: lightest crossing edge is safe (unique ⇒ in every MST).
• Cycle property: strictly heaviest on a cycle ⇒ in no MST.
• Distinct weights ⇒ unique MST. Constant shift keeps MSTs, not shortest paths.

6.2.2 Kruskal's algorithm and union–find

• Kruskal: sort edges; add (u, v) if find(u) ≠ find(v); stop at V − 1 edges.
• O(E log E) = O(E log V); the partial result is a forest.
• Union by rank: height ≤ log n; plus path compression: ~O(α(n)) per operation.

6.2.3 Prim's algorithm; MST complexities

• Prim: grow one tree; add the outside vertex with the smallest key (cheapest edge in).
• Θ(V²) array (dense graphs); O(E log V) binary heap; O(E + V log V) Fibonacci heap.
• Prim one tree; Kruskal a forest; both via the cut property.

6.3.1 Relaxation and Dijkstra's algorithm

• Relax: dist[v] = min(dist[v], dist[u] + w).
• Dijkstra: finalise the closest unfinished vertex; non-negative weights only.
• Θ(V²) array; O((V + E) log V) binary heap; O(E + V log V) Fibonacci heap.
• Shortest-path tree ≠ MST in general.

6.3.2 Bellman–Ford, negative cycles, shortest paths in DAGs

• Bellman–Ford: V − 1 rounds relaxing all edges; extra pass detects negative cycles; Θ(VE).
• Round i fixes paths with ≤ i edges (DP on edge count).
• DAG: relax in topological order once; Θ(V + E); negative edges fine.

6.3.3 All-pairs shortest paths: Floyd–Warshall

• D⁽ᵏ⁾[i][j] = min(D⁽ᵏ⁻¹⁾[i][j], D⁽ᵏ⁻¹⁾[i][k] + D⁽ᵏ⁻¹⁾[k][j]); k outermost.
• Θ(V³) time, Θ(V²) space; negatives OK; negative cycle ⇔ D[i][i] < 0.
• Transitive closure: same loops on booleans.