FIT2004 Unit Cheatsheet

Context: FIT2004_MOC · whole unit W1–W12, syllabus-ordered · the rigour layer (recurrences, bounds, invariants); links for depth only. Read order: untagged = PT-critical, must be automatic · [C] = Credit interview · ⛔ = precondition / trap where marks die · each section ends in a folded 🎓 Depth block (D/HD rigour + applied-sheet extensions) — open it only once the visible lines are fluent.

Quick Revision

• 🎯 Objective: write the recurrence → telescope to a level-sum → read the regime off the ratio → quote the tightest $\Theta$ with its case and its space.
• ⚡ Key Constraint: a growth class without the derivation line earns nothing — the marks are in the general form in $k$ and the base case that fixes it.

1️⃣ Analysis Discipline (W1)

Bound ≠ case sank Q1 of the 2026 S1 D/HD paper — every complexity claim names BOTH.

Case [C]	Analyses	W1 witness
Best	cheapest input of size $n$	naive D&C multiply ➔ best $=$ worst, no branching
Worst	dearest input of size $n$	quicksort, extreme pivot ➔ $\Theta (n^2)$
Average	expectation over an input distribution	quicksort, random pivot ➔ $\Theta (n\log n)$
Amortised	worst-case total over a sequence $÷$ length	a guarantee, not a probability

• Two independent axes [C] ➔ the case picks which function; the bound fences it · ⛔ every pairing is legal — ”$\Omega$ means best case” is the examined misconception.
• Bound axis ➔ $O$ upper · $\Omega$ lower · $\Theta =O\cap \Omega$ tight · pass-tier: answer $\Theta$ as $O$, but a D/HD question makes you justify the $\Omega$ side.
• Definitions [C] ➔ $O$: $\exists c,n_0>0$, $f\le cg\forall n\ge n_0$ · $\Omega$: $f\ge cg$ · $\Theta$: $c_{1}g\le f\le c_{2}g$ · ⛔ no witnesses $c,n_0$ ⟹ no marks.
• Valid ≠ tight ➔ $3n^2+15\log n+100n$ is $O(n^3)$ ($c=118,n_0=1$) and $\Omega (n)$, not $\Theta (n^3)$ since $T/n^3\to 0$ · ⛔ “not the tightest” never makes an $O$ claim false.
• Unqualified “complexity” = worst case ➔ best $\ne$ worst only with an early exit or item values steering control flow; otherwise state one $\Theta$ for all cases (selection, Merge Sort).
• Input size [C] ➔ element count for a collection, bit-length $n=\lceil {\log }_2(k+1)\rceil$ for a number ⟹ $k$ iterations on input $k$ is $O(2^n)$.
• Capped parameter = $\Theta (1)$ [C] ➔ $n\le 10^6\Rightarrow \Theta (nm)=\Theta (m)$ · ⛔ list which parameters may grow before quoting.
• Space = auxiliary ➔ total $=$ input $+$ auxiliary; quote auxiliary, in-place $\equiv O(1)$ auxiliary · ⛔ the recursion stack counts, $\Theta (\text{depth})$.
• Time $\ge$ auxiliary space ➔ self-check: $\Theta (\log n)$ time with $\Theta (n)$ auxiliary is impossible.
• Output size $W$ [C] ➔ reporting costs $\Theta (\text{locate}+W)$; $W$ grows with the instance so it can’t be dropped ➔ Output-Sensitive Complexity.
• Big-O algebra ➔ $O(g_1)+O(g_2)=O(\max )$ · $O(g_1)O(g_2)=O(g_1{g}_2)$ · ⛔ upper bounds only.
• Ladder ➔ $1\prec \log n\prec \sqrt{n}\prec n\prec n\log n\prec n^{1.585}\prec n^2\prec n^3\prec 2^n\prec n!$.

🎓 Depth

• Declare unit-cost [D] ➔ ”$+$ is $O(1)$” needs machine-word operands; iterative Fibonacci is $\Theta (n)$ word-ops but $\Theta (n^2)$ bit-ops.
• Per-op worst × count is an UPPER bound only [D] ➔ tightness needs a witness where the worst cases co-occur ($n$ sorted Binary Search Tree (BST) inserts ⟹ $\Theta (n^2)$).
• $\Omega$ for problems / $\Theta$ for algorithms is a convention [D] ➔ algorithm’s $O$ meets problem’s $\Omega$ ⟹ provably optimal; “any BST insert is $\Omega (1)$” is still well-formed and true.

2️⃣ Identities That Do the Work (W1)

Assume no formula sheet — memorise every closed form; prove both series by induction.

• Log algebra ➔ ${\log }_{b}b=1$ · ${\log }_{b}1=0$ · $\log (xy)=\log x+\log y$ · $\log (x/y)=\log x-\log y$ · $\log x^k=k\log x$ · $b^{{\log }_{b}x}=x$ · base change ${\log }_{b}x=\frac{{\log }_{a}x}{{\log }_{a}b}$ is a constant ⟹ $\Theta (\log n)$ needs no base.
• Arithmetic ➔ ${\sum }_{i=1}^{n}i=\frac{n(n+1)}{2}=\Theta (n^2)$ — shrink-by-one recurrences, quadratic sorts, sorted BST builds.
• Geometric ➔ ${\sum }_{i=0}^n{r}^i=\frac{r^{n+1}-1}{r-1}$ · ⛔ $r\ne 1$ (at $r=1$: $n+1$).
• $r=2$ ➔ $2^{n+1}-1$ — complete binary tree; the leaf level outweighs all levels above.
• $r=\frac{1}{2}$ ➔ $2-2^{-n}<2$ — halving work totals $<2\times$ the top level, independent of $n$.
• Induction blueprint [C] ➔ base → assume $P(k)$ → add the $(k+1)$-th term to the assumed closed form, refactor · ⛔ cite the hypothesis explicitly.
• Induct over the domain [C] ➔ $T(n/2)$ exists only at $n=2^k$: step $m\to 2m$, never $m+1$; closing move $b+c{\log }_{2}m+c=b+c{\log }_2(2m)$.

🎓 Depth

• Exponent swap [D] ➔ $a^{{\log }_{b}n}=n^{{\log }_{b}a}$, since $(b^{{\log }_{b}a}{)}^{{\log }_{b}n}=(b^{{\log }_{b}n}{)}^{{\log }_{b}a}$ — turns a leaf count into a power of $n$.
• Fibonacci doubling [D] ➔ $F(2k)=F(k)[2F(k+1)-F(k)]$ · $F(2k+1)=F(k+1{)}^2+F(k{)}^2$, from $[\begin{array}{cc}1& 1\\ 1& 0\end{array}{]}^n=[\begin{array}{cc}F(n+1)& F(n)\\ F(n)& F(n-1)\end{array}]$ via $M^{2k}=(M^k{)}^2$ · ⛔ $F(0)=0$ indexing; eliminate $F(k-1)=F(k+1)-F(k)$ · index halves ⟹ $\Theta (\log n)$ ➔ Fibonacci Sequence.

3️⃣ Recurrence Solving — Telescoping (W1)

Exam format — write every step (marks are for the steps; exemplar in Solving Recurrences (Telescoping))

0 levels $n,n/2,n/4,n/8$ · 1 substitute, keep $4cn/4$ visible · 2 general $T(n)=2^{k}T(n/2^k)+kcn$ · 3 base $n/2^k=1\Rightarrow k={\log }_{2}n$ · 4 closed form $nb+cn{\log }_{2}n$ · 5 $O(n\log n)$ · 6a check $n=1\Rightarrow b$ · 6b substitute back into the RHS (needs ${\log }_2(n/2)={\log }_{2}n-1$).

• Write it piecewise ➔ $T(n)=a$ for $n<k$ · $T(n)=⟨\#\text{calls}⟩T(\text{shrunk }n)+\text{work}$ for $n\ge k$ · ⛔ $k$ is the source’s guard (if n < 3 ⟹ $k=3$), not a reflexive $T(1)$.
• $a$ counts call sites, not coefficients ➔ 2 * f(n//3) + 4 ⟹ $T(n/3)+c=\Theta (\log n)$ · f(n//3) + f(n//3) + 4 ⟹ $2T(n/3)+c=\Theta (n^{{\log }_{3}2})$.
• Threshold base [C] ➔ if n < 3 with $n/3$: $k={\log }_{3}n-1=\Theta (\log n)$ — solve with the real threshold, drop constants at the end.
• Scope ➔ only shrinking arguments are assessed · telescoping is required (closed form ⟹ $\Theta$, handles $T(n-1)$) · Master Theorem is supplementary, gives $O$ only, fails on $T(n-1)$.

Recurrence	Depth $k$	Accumulates	Closed form
$T(N)=T(N-1)+c$	$N-1$	$k$ constants	$\Theta (N)$
$T(N)=T(N-1)+cN$	$N-1$	arithmetic $\frac{N(N+1)}{2}$	$\Theta (N^2)$
$T(n)=aT(n-1)+c$	$n$	geometric ratio $a$	$\Theta (a^n)$
$T(N)=T(N/2)+c$	${\log }_{2}N$	$k$ constants	$\Theta (\log N)$
$T(N)=T(N/2)+cN$	${\log }_{2}N$	geometric $r=\frac{1}{2}$	$\Theta (N)$
$T(n)=aT(n/b)+cn$	${\log }_{b}n$	geometric $r=a/b$	regime below
$T(N)=T(N-1)+T(N-2)+c$	$N$	branching tree, $\Theta ({\phi }^N)$ nodes	$O(2^N)$

• Level-sum [C] ➔ $T(n)={\sum }_{i=0}^{{\log }_{b}n}cn(a/b{)}^i$ — level $i$ holds $a^i$ subproblems of size $n/b^i$ · ⛔ equal-sized subproblems, $\Theta (n)$ combine.
• Regime from $r=a/b$ [C] ➔ $r<1$ root-dominated $\Theta (n)$ · $r=1$ $\Theta (n\log n)$ · $r>1$ leaf-dominated $\Theta (n^{{\log }_{b}a})$.
• Instances ➔ $(a,b)=(1,2)\to \Theta (n)$ · $(2,2)\to \Theta (n\log n)$ · $(3,2)\to \Theta (n^{1.585})$ · $(4,2)\to \Theta (n^2)$ · ⛔ $a$ = recursive calls, never the combine’s shifts/adds.
• Subtract ⟹ depth $\Theta (N)$ · divide ⟹ $\Theta (\log N)$ ➔ depth and per-level work are independent choices.
• Branching by subtraction = exponential ➔ $2T(n-1)+a=2^{n}b+(2^n-1)a=\Theta (2^n)$ vs $T(n-1)+a=\Theta (n)$ · ⛔ $T(n-1)+T(n-2)$ has two arguments ⟹ bound by the tree.
• “Prove by induction” ≠ Step 6b [C] ➔ closed form is given, nothing telescoped: base $+$ cited hypothesis $+$ step, over the domain ➔ §2️⃣.

🎓 Depth

• Leaf identity [D] ➔ $n(a/b{)}^{{\log }_{b}n}=n^{{\log }_{b}a}$ — the collapse behind every D&C exponent.
• 🔭 Master Theorem (supplementary) ➔ $T(n)=aT(n/b)+\Theta (n^d)$: $d<{\log }_{b}a\Rightarrow \Theta (n^{{\log }_{b}a})$ · $d={\log }_{b}a\Rightarrow \Theta (n^d\log n)$ · $d>{\log }_{b}a\Rightarrow \Theta (n^d)$ · ⛔ multiplicative shrink only — on $T(n-1)$ it gives a wrong answer.

4️⃣ Recursive Time and Space in One Pass (W2)

Protocol: read $a$ + argument shrink + per-call work → recurrence → telescope for time; same depth $k$ → auxiliary space ➔ Analysing Recursive Algorithms (Time and Auxiliary Space).

• Auxiliary $=\Theta (\text{max stack depth})$ ➔ never $\Theta (\text{total calls})$ · ⛔ siblings run sequentially — one root-to-leaf chain is live.
• Single-call recursion ⟹ time class $=$ space class ➔ only branching ($a\ge 2$) decouples them.
• Fibonacci decouples [C] ➔ $O(2^N)$ time counts nodes, $\Theta (N)$ auxiliary counts height · ⛔ say which you measure.
• Shrinking allocations sum [C] ➔ Merge Sort scratch $N+\frac{N}{2}+\cdots <2N$ ⟹ $\Theta (N)$, not $\Theta (N\log N)$.
• Iterative rewrite drops the stack ➔ same time, $O(1)$ auxiliary — why Binary Search and Linear Search are loops.

5️⃣ Divide & Conquer (W1–W2)

• Shape ➔ divide → conquer → combine · ⛔ subproblems independent; overlapping ones need DP.
• Balance sets depth [C] ➔ even halves ${\log }_{2}n$ levels · lopsided $n$ levels ⟹ $\Theta (n^2)$ · one half $+\Theta (1)$ work ⟹ $\Theta (\log n)$.
• Split/combine trade [C] ➔ Merge Sort trivial split, heavy combine · Quick Sort the reverse · Binary Search one subproblem.
• Unseen problem — ask in order ➔ (1) answer $=$ within-left $+$ within-right $+$ cross? (2) cross in $\Theta (n)$? (3) does per-call work shrink? · ⛔ (3) fails silently.
• Strengthen the contract [C] ➔ return more than the answer — Counting Inversions also returns the subarray sorted.
• Count the cross term in blocks ➔ emitting $B[j]$ with $A[i..mid]$ unconsumed adds $mid-i+1$ · ⛔ $+1$ counts merge steps, not inversions.
• Per-call work must shrink ➔ 2D Local Maximum (Peak Finding): column split keeps a $\Theta (n)$ scan ⟹ $\Theta (n\log n)$; cutting both axes ⟹ $T(n/2)+\Theta (n)=\Theta (n)$.
• Discarding needs an existence claim [C] ➔ “a peak lies in the kept quadrant — an increasing walk can’t re-cross the cross” is the marked sentence.

🎓 Depth

• The $\log$ is bought by the combine [D] ➔ $2T(n/2)+\Theta (1)=\Theta (n)$ but $2T(n/2)+\Theta (n)=\Theta (n\log n)$.

6️⃣ W1–W2 Algorithm Bounds

Algorithm	Recurrence	Time (B/A/W)	Auxiliary	Discriminator
Schoolbook multiply	—	$\Theta (n^2)$ all	$\Theta (n)$	every digit pair
Naive D&C multiply	$4T(n/2)+\Theta (n)$	$\Theta (n^2)$ all	$\Theta (n)$	$a=4$ ⟹ no gain
Merge Sort	$2T(n/2)+\Theta (n)$	$\Theta (n\log n)$ all	$\Theta (n)$	stable via <= from the left half
Quick Sort	avg $2T(n/2)+\Theta (n)$	$\Theta (n\log n)$ / W $\Theta (n^2)$	$O(\log n)$	pivot quality
find_min	—	$\Theta (n)$ all	$O(1)$	no early exit ⟹ B $=$ W
build_list(n)	—	$\Theta (n)$ all	$\Theta (n)$	input is a number
Linear Search (recursive)	$T(n-1)+c$	$\Theta (1)$ / $\Theta (n)$ / $\Theta (n)$	$\Theta (n)$	early return
Binary Search	$T(n/2)+c$	$\Theta (1)$ / $\Theta (\log n)$ / $\Theta (\log n)$	$O(1)$ iter · $\Theta (\log n)$ rec	early return
f(n)=2*f(n//3)+4	$T(n/3)+c$	$\Theta (\log n)$	$\Theta (\log n)$	one call site
f(n//3)+f(n//3)+4	$2T(n/3)+c$	$\Theta (n^{{\log }_{3}2})\approx \Theta (n^{0.63})$	$\Theta (\log n)$	two call sites
power	$T(N-1)+c$	$\Theta (N)$	$\Theta (N)$	decrement
power_better	$T(N/2)+c$	$\Theta (\log N)$	$\Theta (\log N)$	passes x*x — halving alone is wrong
POW(x,p/2)*POW(x,p/2)	$2T(p/2)+c$	$\Theta (p)$	$\Theta (\log p)$	call written twice fills the tree
y=POW(x,p/2); y*y	$T(p/2)+c$	$\Theta (\log p)$	$\Theta (\log p)$	bind once ⟹ $a$: $2\to 1$
naive fibonacci	$T(N-1)+T(N-2)+c$	$O(2^N)$	$\Theta (N)$	nodes vs height
Counting Inversions	$2T(N/2)+\Theta (N)$	$\Theta (N\log N)$	$\Theta (N)$	also returns sorted
Peak, gradient walk	—	$\Theta (1)$ / — / $\Theta (n^2)$	$O(1)$	ridge adversary
Peak, column split	$T(n/2)+\Theta (n)$, $n$ fixed	$\Theta (n\log n)$	$\Theta (\log n)$	scan never shrinks
Peak, window frame	$T(n/2)+\Theta (n)$	$\Theta (n)$	$\Theta (\log n)$	$r=\frac{1}{2}$
Range report, scan	—	$\Theta (N)$	$O(1)$	touches all $N$
Range report, search $+$ scan	—	$\Theta (\log N+W)$	$O(1)$	optimal: meets $\Omega (\log N+W)$

• Asymptotic win ≠ faster in practice [C] ➔ a lower exponent bought with extra additions carries a big constant — never a claim about a particular $n$.

7️⃣ Proof of Correctness (W3)

Correctness $=$ invariant $+$ termination. Invariant alone is partial correctness; termination alone may stop with the wrong answer.

• Answer template ➔ (1) invariant quantified over the counter (2) measure that strictly decreases (3) invariant $\wedge \neg \text{guard}\Rightarrow$ postcondition · ⛔ the invariant names the data — “i increases” is not one ➔ Invariant.
• Three-part induction ➔ initialisation · maintenance · termination.
• Termination ➔ finite domain · known start · monotone progress to the bound · recursive: name the shrinking argument and its base case.
• Variant [C] ➔ $V_k\in \mathbb{N}$, $V_{k+1}<V_k$ · ⛔ strictly — “may stay equal” is where infinite loops live.
• Design order [C] ➔ invariant first, then code; weakest statement that implies the postcondition.
• Exam shape ➔ “(1 mark) write a loop invariant for Floyd–Warshall…” — prose algorithm in, one quantified sentence out.

Algorithm	Loop invariant	Termination
find_min	my_min $=\min ($array[0…index]$)$	index from $1$, increments, finite array
Selection sort	my_list[0…i-1] sorted AND $\le$ all of my_list[i…N]	$i$, $j$ only increment
Insertion sort	my_list[0…i-1] sorted (not final)	$i$ increments; $j$ decreases to $0$
Binary Search	key in array[0…N] $\Rightarrow$ key in array[lo…hi]	$hi-lo$ must strictly shrink

• The lo = mid hang ➔ at $lo=5,hi=6$, $mid=5$ ⟹ no-op, never terminates · fix: mid + 1, or while lo < hi - 1 with exclusive hi = len(array).

8️⃣ Sorting — the Four-Axis Suite (W3)

Rank every sort on correctness · time B/A/W · auxiliary space · stability. Most-dropped factors: the $O(k)$ comparison cost and the recursion stack.

Algorithm	Best	Average	Worst	Auxiliary	Stable	In-place
Selection	$\Theta (N^2)$	$\Theta (N^2)$	$\Theta (N^2)$	$O(1)$	No	Yes
Insertion	$\Theta (N)$	$\Theta (N^2)$	$\Theta (N^2)$	$O(1)$	Yes	Yes
Heapsort	$\Theta (N\log N)$	$\Theta (N\log N)$	$\Theta (N\log N)$	$O(1)$	No	Yes
Merge Sort	$\Theta (N\log N)$	$\Theta (N\log N)$	$\Theta (N\log N)$	$\Theta (N)+\Theta (\log N)$	Yes	No
Quick Sort	$\Theta (N\log N)$	$\Theta (N\log N)$	$\Theta (N^2)$	$O(\log N)$	Depends	No
Counting Sort	$\Theta (N+M)$	$\Theta (N+M)$	$\Theta (N+M)$	$\Theta (M)$ · $\Theta (M+N)$ stable	engineered	No
Radix Sort	$\Theta (KN+KM)$	$\Theta (KN+KM)$	$\Theta (KN+KM)$	$\Theta (M+N)$	required	No

• $\Omega (N\log N)$ binds comparison sorts only ➔ merge/heap are optimal there; counting/radix escape it by assuming bounded integer keys.
• Comparison cost multiplies everything ➔ $O(k)$ per string/tuple compare ⟹ $O(k{N}^2)$, $O(kN\log N)$ · integers are $O(1)$ by hardware [C] — the item type decides whether $k$ drops.
• Recursion stack is auxiliary ➔ recursive sorts are never in-place ⟹ the only in-place $\Theta (N\log N)$ sort is Heapsort.
• Shift = stable, long-distance swap = unstable [C] ➔ insertion/merge/bubble shift · selection/heap/quick jump equal keys ([4a,2,3,4b,1]→[1,2,3,4b,4a]) · selection has no best case.
• Forcing stability costs space, never time ➔ parallel index list compared on ties ⟹ auxiliary $O(1)\to \Theta (N)$.
• Comparisons $\ge$ swaps [C] ➔ self-check on any derived count.
• Counting Sort phases ➔ max $\Theta (N)$ → allocate $\Theta (M)$ → tally $\Theta (N)$ → rebuild $\Theta (N+M)$ · ⛔ quote $\Theta (N)$ only if $M$ is capped (alphabet $26$, digits $10$).
• Which variant? ➔ unstated ⟹ bucket · “count array and position array” ⟹ prefix-sum variant (PT-01 signature).
• Stable (prefix-sum) variant ➔ position[first] = 1, $\text{pos}[i]=\text{pos}[i-1]+\text{count}[i-1]$; scan input forwards, write output[position[key]], increment.
• Bucket space $\Theta (M+N)$, not $\Theta (MN)$ ➔ buckets partition the input, $\sum \text{count}=N$ — lecturer’s “very common misconception”.
• Bucket drain [C] ➔ extend(), never pop(0) ($O(n)$ shift ⟹ $\Theta (N^2)$).
• Negative keys [C] ➔ store at $\text{key}-\min$, range $\max -\min +1$, add $\min$ back.
• Radix Sort $=K$ stable counting sorts, LSD first ➔ ⛔ every pass stable, or lower digits’ order is destroyed.
• $M$ clash [C] ➔ counting sort: max key · radix sort: base — say which.
• Digit $j$ of $x$ ➔ $\lfloor x/b^j\rfloor \mathrm{mod}b$ · columns $c=\lfloor {\log }_{b}M\rfloor +1$ — radix’s only use of max (counting uses it to size the array) · lecturer’s recurring code-review error.
• Base buys linearity ➔ $b\le N$ keeps a pass $\Theta (N)$; $M=O(N^d)$ ⟹ $c=\Theta (1)$ ⟹ $\Theta (N)$ · ⛔ $b>N$ lets the count array dominate · [C] raising $b$ shrinks $K$ but grows $\Theta (KM)$.
• Ragged keys [C] ➔ pad with a filler below every symbol · right-aligned $=$ numeric order, left-aligned $=$ lexicographic.

🎓 Depth

• Auxiliary carries no $K$ [D] ➔ count/position/output arrays are reused each pass; only the input is $\Theta (KN)$.
• “Radix is $\Theta (N)$” needs a hypothesis [D] ➔ capped key width; $N$ distinct base-$M$ keys force $K\ge {\log }_{M}N$ ⟹ $\Theta (N\log N)$.
• Ragged-string radix in $\Theta (n)$ [D] ➔ counting-sort by length ascending $\Theta (\ell +k)$, sweep $i=\ell \to 1$ sorting only the window of strings with length $\ge i$ · ⛔ ascending, so cat precedes cats; naive padding is $\Theta (\ell k)$.
• Constant-factor base [D] ➔ minimise $\frac{W}{{\log }_{2}b}(N+b)$; $W=64,N=10^6$ ⟹ $b=2^{16}$, $4$ passes · pick $b=2^t$, $t\mid W$ ⟹ shift-and-mask.
• Comparison model proves $\Omega$, never $O$ [D] ➔ binary-insertion sort makes $\Theta (N\log N)$ comparisons yet runs $\Theta (N^2)$ — it still shifts.
• “In-place” depends on the cost model [D] ➔ $O(1)$ machine words; strict RAM pointers need $\Theta (\log n)$ bits ⟹ relaxed to $O(\log n)$, $O(1)$ excluding pointers, or $o(n)$ — say which.

9️⃣ Quicksort, Selection and the Applied Suite (W3 applied · W4 · PT-01)

Every W4 bound is a pair — expected and worst differ. Quoting one without naming it is unmarkable ➔ §1️⃣.

Partition scheme	Writes	Extra space	Returns	Stable	Pick it when
Out-of-place	$\Theta (N)$ copies	$\Theta (N)$ $+$ stack	pivot’s final index	No · Yes with a 3rd buffer	stability contractual, memory free
Hoare’s	$\le 1$ swap per item	$O(1)$	pivot’s final index (this unit)	No	large records ⟹ writes dominate
Lomuto’s	1 swap per item $<p$	$O(1)$	pivot’s final index	No	correctness under exam time
Dutch flag (3-way)	1 swap per misplaced item	$O(1)$	two boundaries	No	many duplicates, $d\ll N$

• Return contracts ➔ Lomuto and this unit’s Hoare return the pivot’s final index $j$ ⟹ recurse (start, j-1), (j+1, end) · textbook Hoare returns a split point ⟹ (start, j), (j+1, end) · ⛔ name the contract first ➔ Partitioning (Quicksort).
• Hoare invariants ➔ left of L_bad $\le p$ · right of R_bad $>p$ · between is unprocessed, empty when pointers cross · ⛔ guard the final pivot swap.
• Dutch flag invariants ➔ [1 … boundary1-1] $<p$ · [boundary1 … j-1] $=p$ · [boundary2+1 … N] $>p$ · [j … boundary2] unprocessed, exit j > boundary2 · ⛔ the $>p$ branch must not advance j.
• 3-way for duplicates [C] ➔ recurse on the outer two ⟹ depth $O(\log d)$, all-equal input $\Theta (N)$ · a 2-way split never retires equal keys.
• Schemes differ in writes, not comparisons [C] ➔ Hoare $\approx 3\times$ fewer writes than Lomuto — matters for large records.
• Stability [C] ➔ Hoare’s final pivot swap jumps the pivot ⟹ unstable regardless · out-of-place ≤ pivot is still unstable ⟹ add an == pivot buffer.
• Average height (“green area”) ➔ middle-half pivot w.p. $\frac{1}{2}$ leaves $\le \frac{3N}{4}$ ⟹ $h={\log }_{4/3}N$, average depth $\approx 2h=\Theta (\log N)$, $\times \Theta (N)$ per level.
• Pivot judged on fraction, not balance ➔ fixed $1:9$ split is still $\Theta (\log N)$ depth · $\Theta (N^2)$ needs a constant-size split every level (minimum pivot ⟹ every input).
• Random vs guarantee ➔ random pivot makes the bad input unconstructible (expected $\Theta (N\log N)$, worst $\Theta (N^2)$) · Median of Medians makes it impossible (worst $\Theta (N\log N)$) — the W4 hinge.
• Quicksort is never in-place ➔ live frames are auxiliary: $O(N)$ worst, $O(\log N)$ by recursing the smaller side first and looping on the larger.
• Order statistics [C] ➔ $Q_1$ at $k=N/4$ · median $N/2$ · $Q_3$ $3N/4$ — one algorithm.
• Sort-then-slice is the baseline ➔ $O(MN\log N)+O(k)$, $M$ = comparison cost · counting/radix can’t be assumed.
• Quickselect ➔ partition at $j$: $j=k$ return · $k<j$ left · $k>j$ right, $k$ unchanged (absolute indices) ⟹ $N+\frac{N}{2}+\cdots =\Theta (N)$ expected, $\Theta (N^2)$ worst.
• Quickselect best is $\Theta (N)$ ➔ one full partition is unavoidable · tail call ⟹ $O(1)$ auxiliary as a loop [C].
• Median of Medians ➔ $T(N)=T(N/5)+T(7N/10)+cN$, $\frac{1}{5}+\frac{7}{10}<1$ ⟹ $\Theta (N)$ · ⛔ groups of $3$ sum to $1$ ⟹ $\Theta (N\log N)$ · examinable since 2023 — a hand skill.
• MoM by hand ➔ groups of $5$ → insertion-sort each → read medians → quickselect their median → partition on it · base $N\le 5$.
• The $30\%$ ➔ $\frac{1}{2}\cdot \frac{N}{5}\cdot 3=\frac{3N}{10}$ on each side ⟹ worst split $70:30$.
• Co-recursion [C] ➔ MoM ↔ quickselect; both arguments shrink ($\frac{N}{5}$, $\frac{7N}{10}$), $N\le 5$ is the shared base.
• K-way Merge ➔ scanning $k$ heads $\Theta (Nk)$ → min-Heap of heads $\Theta (N\log k)$, auxiliary $\Theta (k)$ · entries (value, list id, index) [C] · ⛔ heap stays size $k$ — seeding all $N$ is heapsort.
• Online vs offline decides admissibility first ➔ online $=$ valid answer at every arrival · quickselect is $\Theta (N)$ yet unusable on a stream · insertion sort / heap add online; merge sort / build_heap not ➔ Online Algorithm.
• $k$ smallest ⟹ size-$k$ MAX-heap ➔ root $=$ eviction threshold; arrival $\ge$ root rejected in $O(1)$ ⟹ $\Theta (N\log k)$, $\Theta (k)$ · $k$ largest ⟹ min-heap.
• Sort as preprocessing [C] ➔ buys adjacency and binary search · dedup with read/write pointers $\Theta (N)$ (shift-delete $\Theta (N^2)$).
• An “in-place” spec picks the sort ➔ Heapsort is the only valid $\Theta (N\log N)$ choice — naming it is the marked step.
• Optimality by reduction [C] ➔ $N$ singleton lists $+$ $k$-way merge $=$ a comparison sort ⟹ $\Omega (N\log k)$ for merging.

W4 algorithm	Time (B/A/W)	Auxiliary	Online?	Discriminator
Quick Sort (random pivot)	$\Theta (N\log N)$ / $\Theta (N\log N)$ / $\Theta (N^2)$	$O(\log N)$ smaller-first · $O(N)$ naive	No	smallest constant of the $N\log N$ sorts
Quick Sort $+$ Median of Medians	$\Theta (N\log N)$ all	$O(\log N)$	No	worst case eliminated, big constant
Quickselect (random pivot)	$\Theta (N)$ / $\Theta (N)$ / $\Theta (N^2)$	$O(1)$ iterative	No	one rank
Quick Sort $+$ exact-median Quickselect	$\Theta (N\log N)$ / $\Theta (N\log N)$ / $\Theta (N^2)$	$O(\log N)$	No	no gain — inherits quickselect’s worst
Quickselect $+$ Median of Medians	$\Theta (N)$ all	$O(\log N)$	No	linear worst-case selection
K-way Merge (min-heap)	$\Theta (N\log k)$ all	$\Theta (k)$	Yes	external sorting
K-way Merge (scan heads)	$\Theta (Nk)$ all	$\Theta (k)$	Yes	only for $k\lesssim 4$
Size-$k$ heap	$\Theta (N\log k)$ all	$\Theta (k)$	Yes	$N$ unbounded or memory cap

🎓 Depth

• Average case from the recurrence (NOT examinable) ➔ $T(N)=2+\frac{N+1}{N}T(N-1)$ after subtracting the $(N-1)$ instance ⟹ $O(N\log N)$ via the harmonic tail $\le {\int }_1^N\frac{dx}{x}$.
• Exact-median pivot doesn’t fix quicksort [D] ➔ quickselecting it is $\Theta (N^2)$ worst ⟹ $N^2+\frac{N^2}{2}+\cdots =\Theta (N^2)$; a $30/70$ pivot in linear worst time is what closes it.
• The mean is not the median [D] ➔ on $a_i=i!$ the element nearest the mean is the second-largest ⟹ $T(n-2)+\Theta (n)=\Theta (n^2)$ · no guaranteed proportional cut ⟹ no log depth.
• Naive 3-way groups duplicates, Hoare scatters them [C] ➔ [7,1,12,9,3,3,10,6,7,14,4], pivot $7$: naive [1,3,3,6,4,7,7,12,9,10,14] · Hoare [6,1,4,7,3,3,7,10,9,14,12].
• $k$-partitioning [C] ➔ sequential $\Theta (nk)$ · middle pivot then recurse both halves $\Theta (n\log k)$ · $k=n$ is sorting ⟹ $\Omega (n\log k)$.
• Quickselect expected $O(n)$ by coins [C] ➔ good pivot (middle $50\%$) leaves $\le 0.75n$, $\mathrm{Pr}=\frac{1}{2}$ ⟹ $2$ tries ⟹ $\mathbb{E}[T]\le 8cn$.
• Weighted median [C] ➔ compare weight sums, not ranks; recurse into the heavier side with $w$ reduced · ⛔ permute weights in unison.
• $k$ closest to the median in $\Theta (n)$ [C] ➔ quickselect $m$, then the $k$-th smallest $|a_i-m|$, take strictly smaller and top up from ties · read a[i] as $|a_i-m|$ in place ⟹ $O(1)$ extra.
• Hybrid merge + insertion [C] ➔ $\Theta (nk+n\log \frac{n}{k})$ · ⛔ $k$ constant, or $nk$ dominates.
• Locks and keys [D] ➔ pivot keys on a lock, locks on the matching key ⟹ $\Theta (n\log n)$ average.
• Order statistic of two sorted arrays [D] ➔ $\text{order}(a[i])=i+|\{j:b[j]<a[i]\}|$ is monotone ⟹ nested search $\Theta (\log n\log m)$ · simultaneous searches $\Theta (\log n+\log m)$.

🔟 Graphs, Traversal and Shortest Paths (W5)

Every graph bound has two parameters and a representation: $\Theta (V+E)$ is adjacency-list ($\Theta (V)$ sparse, $\Theta (V^2)$ dense); the same code on a matrix is $\Theta (V^2)$.

• Definitions ➔ $G=(V,E)$ · directed $(u,v)$ from $u$ to $v$ · weighted $(u,v,w)$ · simple $=$ no self-loops or multi-edges (assumed unless told).
• Max edges ➔ directed $V(V-1)$, undirected $\frac{V(V-1)}{2}$, both $O(V^2)$ · sparse $E=O(V)$, dense $E\approx V^2$ — picks the representation and turns $O(E\log V)$ into $O(V^2\log V)$.

	Space	Edge exists?	Neighbours of $u$	Traversal
Adjacency matrix	$\Theta (V^2)$ always	$O(1)$	$O(V)$ row scan	$\Theta (V^2)$
Adjacency list	$\Theta (V+E)$	$O(X)$, early exit if sorted	$O(X)$	$\Theta (V+E)$

• Sorted linked list ≠ $O(\log X)$ [C] ➔ only early exit; binary search needs a sorted array.
• Traversal $\Theta (V+E)$ ➔ each vertex served once $+$ each undirected edge seen twice · ⛔ “discovered?” is an $O(1)$ flag, not a queue search ($\Theta (VE)$).
• Three states ➔ undiscovered → discovered (in the collection) → visited (served) · hand trace: a Discovered row and a Visited row every step.
• The frontier ADT is the algorithm ➔ queue BFS · stack DFS · min-Heap Dijkstra — every other line identical.
• Tie-breaks apply at insertion ➔ alphabetical: BFS appends A→Z, DFS pushes Z→A · ⛔ same-layer vertices leave in queue order · order depends on adjacency order — state it [C].
• BFS = unweighted shortest distance ➔ at discovery v.distance = u.distance + 1, v.previous = u · ⛔ FIFO and uniform cost · DFS depths are not distances [C].
• Traversal uses [C] ➔ reachability · components · cycle detection · unweighted shortest path · Topological Sort.
• Dijkstra $=$ DP $+$ greedy ➔ closest unfinalised vertex is finalised on serve · ⛔ $w\ge 0$ — a negative edge cheapens a detour after finalisation.
• Relaxation ➔ $v$ not finalised: undiscovered ⟹ set $d_u+w$; else update only if $d_v>d_u+w$; rewrite v.previous on every success.
• Dijkstra bounds ➔ binary heap $O(E\log V)$ (dense: the slide’s $O(V^2\log V)$) · Fibonacci heap $O(E+V\log V)$ · ⛔ update needs a vertex → heap-slot index map, else $O(V)$ each.
• Update vs duplicate heap ➔ duplicates (heapq): one push per relaxation, heap $O(E)$, stale entries skipped on serve · $\log V^2=2\log V$ ⟹ same bound.
• Matrix Dijkstra [C] ➔ $O(V^2+E\log V)$ — reads are $V^2$, heap ops only per edge · ⛔ not $O(V^2\log V)$.
• Single target [C] ➔ stop when the target is visited; backtrack previous, reverse.
• DAG ➔ no directed cycle (undirected cycles fine) · $⟨A,B⟩$ = $A$ before $B$.
• Topological Sort ➔ $u$ before $v$ for every edge · not unique · exists $⟺$ DAG.
• Kahn’s ➔ count in-degrees → seed zeros → pop, emit, decrement out-neighbours, push new zeros ⟹ $\Theta (V+E)$ · $|\text{sorted}|<V$ ⟹ cycle · queue or stack both valid.
• Modified DFS ➔ push on finish, then reverse ⟹ $\Theta (V+E)$ · ⛔ DFS pre-order is not topological (top error) · seed every vertex.
• Which one [C] ➔ Kahn’s: free cycle check, layered batches, no recursion · DFS when a traversal already exists · process never $>1$ ⟹ the order is unique.

🎓 Depth

• Parametrised re-derivation [D] ➔ append $A$, serve $B$, update $C$: $T=O(V+VA+VB+EC)$ — on a swapped heap re-derive, never re-quote ➔ Dijkstra’s Algorithm.
• Dijkstra correctness [D] ➔ suppose shorter $P:s⇝u$; $x$ last vertex of $P$ in $S$, $y$ its successor; $\text{len}(s⇝y)\le \text{len}(P)<\text{dist}[u]$ ⟹ $y$ served first, or $\text{dist}[u]<\text{dist}[u]$ · ⛔ that first $\le$ is where $w\ge 0$ is spent.

🔟.b The W5 Applied Sheet — Traversal, Recast

W5-applied task	Time	Auxiliary	Discriminator
Two-colour / bipartiteness	$\Theta (V+E)$	$\Theta (V)$	first colour free, rest forced
Count two-colourings	$\Theta (V+E)$	$\Theta (V)$	$2^c$, or $0$
Directed cycle	$\Theta (V+E)$	$\Theta (V)$	edge into an active vertex
Undirected cycle	$O(V)$	$\Theta (V)$	halts early; independent of $|E|$
Shortest cycle (directed)	$O(V(V+E))$	$\Theta (V)$	one BFS per source
Count pure-cycle components	$\Theta (V+E)$	$\Theta (V)$	conjunction of $\mathrm{deg}=2$
Multi-source BFS / super source	$\Theta (V+E)$	$\Theta (V)$	subtract $1$ for the extra hop
State-graph BFS	$\Theta (kV+kE)$	$\Theta (kV)$	one slot per state
Universal sink (matrix)	$O(V)$	$\Theta (V)$	one candidate killed per cell
Bridges	$\Theta (V+E)$	$\Theta (V)$	beats delete-and-recount
Guaranteed top-$m$ in a DAG	$O(V^2+VE)$	$\Theta (V)$	two DFS per vertex
Hamiltonian path in a DAG	$\Theta (V+E)$	$\Theta (V)$	unique topological order

• Two-colouring is greedy, not search ➔ first vertex of a component is free, the rest forced · ⛔ fail only on a neighbour with the same colour · bipartite $⟺$ two-colourable.
• Directed cycles need three states ➔ unvisited / active / inactive; fire only on an edge into an active vertex ➔ Cycle Detection · ⛔ the undirected rule false-positives on the diamond $a\to b\to d$, $a\to c\to d$.
• Multi-source shortest path ➔ seed the queue with all sources at $0$, or a super source and subtract $1$ · transform the input, keep the algorithm a black box.
• State-graph BFS [C] ➔ when the optimum revisits a vertex, use $⟨\text{vertex},\text{extra}⟩$, wire only legal transitions, answer $\min$ over accepting states · constant $k$ is free; an input capacity must appear in the bound ➔ State-Space Graph Modelling.

🎓 Depth

• Counting two-colourings [C] ➔ $0$ if any component fails, else $2^c$ · ⛔ isolated vertices are components.
• Undirected cycle is $O(V)$ [D] ➔ acyclic ⟹ $E\le V-1$; cyclic ⟹ halts at the first non-tree edge · bound by work before the halt.
• Shortest cycle [C] ➔ BFS from every vertex, test if v == s · one BFS orders by distance from its source, missing a short far cycle.
• Pure-cycle components [C] ➔ every $\mathrm{deg}(v)=2$ · ⛔ never early-return, or the remainder is recounted as a new component.
• Iterative DFS [C] ➔ explicit stack, test visited on pop — filtering at push breaks $\Theta (V+E)$ · neighbours come off reversed.
• Universal sink [D] ➔ $A[i][j]=1$ kills $i$, $A[i][j]=0$ ($i\ne j$) kills $j$; linked list of live candidates ⟹ $\le V-1$ reads $+$ $O(V)$ verify ➔ Graph Representations §3.
• Bridges by low-link [D] ➔ bridge $⟺$ on no cycle $⟺$ $\text{low\_link}[v]>\text{dfs\_ord}[u]$ for tree edge $u\to v$ · $\text{low\_link}[v]=\min (\text{dfs\_ord}[v],\min \text{low\_link}[u])$ · ⛔ mixed and strict comparison; mark the tree edge before recursing ➔ Bridges (Low-Link).
• Guaranteed position in every topological order [D] ➔ $r(v)=$ $\#$reachable, $s(v)=$ $\#$reaching · always in first $m$ $⟺r\ge n-m$ · never $⟺s\ge m$.
• Hamiltonian path in a DAG [D] ➔ exists $⟺$ topological order unique $⟺$ consecutive pairs adjacent ⟹ $\Theta (V+E)$ — acyclicity leaves one candidate ➔ Topological Sort §5.

1️⃣1️⃣ Minimum Spanning Trees, Union-Find and Greedy (W6)

Most-examined W6 sentence: "can Prim/Kruskal run on negative weights?" — YES. Non-negativity is Dijkstra's precondition; importing it here loses the mark.

• MST ➔ acyclic undirected spanning subgraph minimising $\sum w(e)$; every spanning tree has $V-1$ edges · ⛔ connected and undirected, else spanning forest · $V-1$ = min to connect = max without a cycle [C] ➔ Spanning Tree.
• Cost unique, tree not ➔ write an MST, state the tie-break, quote the selection order.
• Negatives are legal ➔ both only compare weights · adding $c$ to every edge adds $(V-1)c$ to every tree ⟹ same MST.
• Maximum spanning tree [C] ➔ max-heap Prim · descending Kruskal · or negate every weight.
• Prim $=$ Dijkstra with one line changed ➔ v.distance = w (distance to the tree) ⟹ finalisation order not nondecreasing · no cycle test needed [C].
• Prim bounds ➔ $O(E\log V)$ with heap $+$ index map · $O(V^2)$ array scan on dense graphs.
• Kruskal ➔ sort ascending → accept iff find(u) != find(v) → union → stop at $V-1$ edges · ⛔ comparison sort unless integer weights are stated.
• Kruskal ladder ➔ set copy $O(EV)$ · smaller-into-larger $O(E\log V)$ · union-find $O(E\log E)=O(E\log V)$ since $\log E\le 2\log V$ — sort dominates.
• Prim vs Kruskal [C] ➔ dense / matrix ⟹ Prim · sparse / edge list / presorted ⟹ Kruskal.
• Union-find encoding ➔ one parent array: positive $=$ parent, negative $=$ root with size/rank magnitude, init $-1$ · ⛔ magnitude meaningful only at a root — find first.
• Union by size ➔ smaller under larger; tie ⟹ first argument’s root wins · $\text{size}\ge 2^{\text{height}}$ ⟹ height $\le {\log }_{2}V$ ⟹ $O(\log V)$ per op.
• $+$ path compression [C] ➔ re-point the walked path at the root ⟹ ~$O(1)$ amortised · fires on refused unions too · stored rank becomes an upper bound.
• Greedy ➔ ranking rule $+$ feasibility $+$ irrevocable commit · needs greedy-choice and optimal substructure (DP: substructure only).
• Interval scheduling ➔ max count: earliest finish first ⟹ $\Theta (n\log n)$ · proof: $f_{i_k}\le f_{j_k}$ by induction.
• Rules that fail [C] ➔ shortest duration: $(1,10),(9,12),(11,20)$ · earliest start: first request finishes last · kill rivals by counterexample first.
• Weighted intervals ⟹ DP [C] ➔ substructure survives, greedy choice doesn’t.
• $0$-$1$ BFS [C] ➔ deque: $0$-edges to front, $1$-edges to back, d == dist[u] staleness guard ⟹ $\Theta (V+E)$.
• State-graph Dijkstra [C] ➔ cost depends on more than location ⟹ state in the vertex, e.g. $⟨\text{town},\text{litres}⟩$ with refuel edges $⟨u,c⟩\to ⟨u,c+1⟩$ weight $p_u$ ➔ State-Space Graph Modelling.
• Buggy-Dijkstra witness ➔ to break “update only on first discovery”: $s\to a(1),a\to c(1000),s\to b(2),b\to c(1)$ locks $c$ at $1001$, not $3$.

W6 algorithm	Time	Auxiliary	Weights	Discriminator
Prim’s Algorithm (heap)	$\Theta (E\log V)$	$\Theta (V)$	any sign	one tree, no cycle test
Prim’s Algorithm (array)	$\Theta (V^2)$	$\Theta (V)$	any sign	dense graphs
Kruskal’s Greedy Algorithm $+$ union-find	$\Theta (E\log V)$	$\Theta (V)$	any sign	presorted ⟹ $\Theta (E\alpha (V))$
Kruskal’s Greedy Algorithm $+$ naive sets	$O(EV)$	$\Theta (V)$	any sign	the $V$ is in union
Union-Find (Disjoint Set) by size/rank	$O(\log V)$/op	$\Theta (V)$	—	$O(V\log V)$ for all unions
$+$ path compression	~$O(1)$ amortised	$\Theta (V)$	—	flattens on refused unions
Interval scheduling	$\Theta (n\log n)$	$\Theta (1)$ beyond sort	—	count, not value
$0$-$1$ BFS (deque)	$\Theta (V+E)$	$\Theta (V)$	$\{0,1\}$	two-key priority queue
Dijkstra $+$ bucket queue	$\Theta (V+E)$	$\Theta (cV)$	integer $0\le w\le c$	minimum never decreases

🎓 Depth

• MST cut-and-swap [D] ➔ invariant: chosen set $\subseteq$ some MST $M$; if $M$ omits $e$, $M+e$ has a cycle re-crossing the cut at $e^{\prime }$ with $w(e)\le w(e^{\prime })$ ⟹ $M-e^{\prime }+e$ is an MST containing $e$ · never uses $w\ge 0$.
• Reverse-delete [D] ➔ sort descending, delete $e$ iff $T-e$ stays connected; invariant $T\supseteq$ some MST ➔ Minimum Spanning Tree §5.
• A true invariant can be too weak [D] ➔ “each Kruskal component is an MST of its vertices” can’t close the proof — counterexample $ab(10),cd(10),bc(1),ad(1)$ ➔ Invariant.
• Bottleneck paths [D] ➔ every MST path minimises its largest edge (swap its heaviest edge for a lighter crossing edge) · converse false.
• Union-by-size lemma [D] ➔ base $1\ge 2^0$; $h(r)>h(s)$ keeps height; $h(r)\le h(s)$ gives ${\text{size}}^{\prime }\ge 2\text{size}(s)\ge 2^{h(s)+1}$.
• Amortised ≠ per-op [D] ➔ one compressed find can still cost $\Theta (\log V)$.
• Greedy proof templates [D] ➔ exchange (edit an optimum to contain your choice — MST) · stays ahead (your $k$-th choice no worse — scheduling) · both still owe termination.
• Bucket-queue Dijkstra [D] ➔ $0\le w\le c$: $cV$ linked-list buckets, $O(1)$ insert/update, one forward sweep $O(cV)$.

1️⃣2️⃣ Dynamic Programming (W7 · PT-02)

PT-02's recurrence describes the value stored in the MEMO — not PT-01's time-complexity recurrence. Same word, different object.

• Two ingredients ➔ overlapping subproblems (reuse pays) $+$ optimal substructure (sub-optima compose).
• DP vs D&C ➔ same skeleton; DP’s sub-solutions are optimal and reused because they overlap · no repeats ⟹ a memo buys nothing.
• DP vs greedy ➔ greedy also needs the greedy-choice property and commits; DP defers · no safe ranking rule ⟹ DP.
• Brute force with a table [C] ➔ still enumerates every choice; saves recomputation, paid in auxiliary space · Fibonacci $O(2^N)\to \Theta (N)$.
• MEMO as an English sentence ➔ DP[i] = {max profit from a subset of houses [1..i]} — the recurrence is read off it · ⛔ no sentence, no DP.
• Three case groups ➔ base (written in; needed for backtracking) · general (the $\max$/$\min$ decision) · edge (boundary, no decision) · if two can fire, “first match wins”.
• Auxiliary $=$ number of subproblems ➔ one per MEMO dimension · ⛔ the choice set is not a dimension (coin change: $O(V)$ space, $O(VN)$ time).
• Time $=$ subproblems $\times$ work each ➔ quote both factors.
• Answer location ➔ fixed cell (coin change, LCS, interval DP) or scan (LIS, max subarray) · anchored “ending at $i$” always costs a $\max$ scan.
• Top-down vs bottom-up [C] ➔ same complexity · top-down skips unneeded subproblems · bottom-up fill order is a correctness condition ➔ Interval Dynamic Programming.
• Reconstruction ➔ decision array (faster) vs backtracking (less auxiliary, same class) · store the last decision, never the whole combination ($O(N^2)$).
• Backtracking = inclusion test ➔ compare against the skip branch: $0/1$ knapsack vs row above (differs ⟹ taken, move up and left $w_i$) · salesman takes $i$ iff $\text{DP}[i]>\text{DP}[i-1]$ · ⛔ strict; a $\ge$ invents a choice.
• Memo sentinel outside the answer range ➔ $-1$, never $\infty$ (a legal “unreachable” answer).
• Syllabus ➔
  • pass: Fibonacci · coin change · unbounded and $0/1$ knapsack · neighbour houses · LIS · maze
  • pass, off-deck: rod cutting (= unbounded knapsack, length as weight) · edit distance (tutorial videos, with LCS)
  • credit: LCS · LIS · matrix chain · the applied sheet
• Coin change ➔ $\text{MinCoins}[v]=0$ if $v=0$ · $\infty$ if every $c_i>v$ · else ${\min }_{c_i\le v}(1+\text{MinCoins}[v-c_i])$ · PT-02 sample is this with microwave keys $\{1,10,60\}$.
• Greedy coin change fails ➔ $\{1,5,6,9\}$ for $12$: greedy $9+1+1+1$ ($4$) vs $6+6$ ($2$) · canonical currencies prove nothing.
• Coin hand-table ➔ $\{1,5,6,9\}$, $v=\mathrm{0..12}$: $0,1,2,3,4,1,1,2,3,1,2,2,2$ · last coin $-,1,1,1,1,5,6,1,1,9,5,6,6$ ⟹ $12\stackrel{6}{\to }6\stackrel{6}{\to }0$ · ⛔ not monotone.
• Unbounded knapsack ➔ coin change with $\max$ and init $0$: $\text{memo}[w]=\max (\text{memo}[w-1],{\max }_{w_i\le w}(v_i+\text{memo}[w-w_i]))$ · ⛔ the $\text{memo}[w-1]$ carry fixes “exactly $w$”.
• $0/1$ knapsack ➔ $\text{DP}[i][w]=\text{DP}[i-1][w]$ if $w_i>w$, else $\max (\text{DP}[i-1][w],v_i+\text{DP}[i-1][w-w_i])$; bases $0$ · ⛔ read the row above, or the item becomes reusable.
• Why 1-D vs 2-D ➔ unlimited items ⟹ weight alone is a sufficient state · single-use ⟹ row $i$ encodes “first $i$ items on offer”.
• Knapsack instance [C] ➔ $A(6,230)$, $B(1,40)$, $C(5,350)$, $D(9,550)$, capacity $12$: unbounded $780$ ($2C+2B$) · $0/1$ $620$ ($\{A,B,C\}$) · ⛔ swapping the two answers loses the question.
• Two-row trick [C] ➔ value only ⟹ roll two rows · which items ⟹ keep the matrix.
• Salesman / neighbour houses ➔ $\text{DP}[i]=\max (\text{DP}[i-1],\text{DP}[i-2]+c_i)$, $\text{DP}[0]=0$, $\text{DP}[1]=c_1$ · $50,10,12,65,40,95,100,12,20,30\Rightarrow 252$ (houses $1,4,6,8,10$) · ⛔ the $100$ is not taken.
• Grid DP ➔ paths $\text{DP}[i,j]=\text{DP}[i+1,j]+\text{DP}[i,j+1]$ (disjoint sets add) · max money $c_{i,j}+\max (\cdot ,\cdot )$ · $O(n^2)$, answer $\text{DP}[1,1]$ · top row / right column have one move.
• Four subproblem shapes [C] ➔ prefix/suffix · cut a sequence everywhere, $\text{DP}[i]={\min }_{j>i}(\text{block}[i..j-1]+\text{DP}[j])$ · two prefixes of two sequences · a contiguous range.
• Add a dimension [C] ➔ if the optimum revisits a position, position isn’t a sufficient state (two-sided street: DPleft, DPright).

W7 DP problem	Subproblems	Work each	Time	Aux	Answer
Coin change	$M$ values	$O(N)$	$O(NM)$	$\Theta (M)$	$\text{DP}[M]$
Unbounded knapsack	$M$ weights	$O(N)$	$O(NM)$	$\Theta (M)$	$\text{DP}[M]$
$0/1$ knapsack	$NM$	$O(1)$	$O(NM)$	$\Theta (NM)$	$\text{DP}[N][M]$
Salesman houses	$n$	$O(1)$	$\Theta (n)$	$\Theta (n)$	$\text{DP}[n]$
Grid paths / max money	$n^2$	$O(1)$	$\Theta (n^2)$	$\Theta (n^2)$	$\text{DP}[1,1]$
LIS	$n$	$O(n)$	$\Theta (n^2)$	$\Theta (n)$	scan ${\max }_i$
Box stacking	$6n$	$O(n)$	$\Theta (n^2)$	$\Theta (n)$	scan ${\max }_i$
LCS / SCS	$nm$	$O(1)$	$\Theta (nm)$	$\Theta (nm)$	$\text{DP}[n][m]$
Interleaving	$nm$	$O(1)$	$\Theta (nm)$	$\Theta (nm)$	$\text{DP}[1][1]$
Max subarray (prefix sums)	$n$	$O(n)$	$\Theta (n^2)$	$\Theta (n)$	$\max (\text{DP}[j]-\text{DP}[i])$
Max subarray (anchored)	$n$	$O(1)$	$\Theta (n)$	$\Theta (1)$	scan ${\max }_j$
Max-sum submatrix	$n^2$	$O(n)$	$O(n^3)$	$\Theta (n)$	scan
Palindromic subsequence	$n^2$	$O(1)$	$\Theta (n^2)$	$\Theta (n^2)$	$\text{DP}[1][n]$
Coin game	$n^2$	$O(1)$ w/ prefix sums	$\Theta (n^2)$	$\Theta (n^2)$	$\text{DP}[1][n]$
Boolean parenthesisation	$n^2$	$O(n)$	$O(n^3)$	$\Theta (n^2)$	$\text{DP}[1][n][\text{T}]$
Ferry (two lanes)	$nL$	$O(1)$	$\Theta (nL)$	$\Theta (nL)$	$\text{DP}[1][L]$
Word break	$n$	$O(mn)$	$O(n^{2}m)$	$\Theta (n)$	$\text{DP}[1]$
Text justification	$n$	$O(n)$	$O(n^2)$	$\Theta (n)$	$\text{DP}[1]$
Tree broadcast	$n$	$O(n_C(v))$	$O(n)$	$\Theta (n)$	$\text{DP}[r]$

🎓 Depth

• Delete a redundant parameter [D] ➔ derivable index ≠ dimension: ferry $L_2=2L-L_1-{\sum }_{j<i}{\ell }_j$ ⟹ $O(n{L}^2)\to \Theta (nL)$ · interleaving $k=i+j-1$ ⟹ $\Theta (nm)$ · ⛔ prefix sums keep it $O(1)$.
• Collapse the table [D] ➔ look-back $O(1)$ cells: max subarray $\Theta (1)$ auxiliary, LCS length $\Theta (\min (n,m))$ · ⛔ no rolling when asked which.
• Tree DP [D] ➔ $\text{DP}[v]={\max }_i(i+\text{DP}[C_v[i]])$, children sorted descending (slowest subtree first) · counting sort ⟹ $O(n)$.
• Non-crossing bridges [D] ➔ state (house, furthest-right bridge): $\text{DP}[i,j]=\max (1+\text{DP}[i+1,f[i]],\text{DP}[i+1,j])$ if $f[i]>j$ · keep only the monotone frontier.
• Grouping with spread $\le d$ [D] ➔ sort, $\text{DP}[i]={\bigvee }_{j\ge i+k-1,a[j]-a[i]\le d}\text{DP}[j+1]$ $O(n^2)$ → monotone pointer $+$ partial sums $O(n)$ · sorting safe by exchange ➔ Greedy Algorithm §3.
• Ordered cases [D] ➔ wildcard matching: first match wins; cache “any $\text{DP}[k][j+1]$ true” filling descending ⟹ $O(n^{2}m)\to O(nm)$.
• DP over a DAG [D] ➔ reverse topological order: paths $\text{DP}[u]={\sum }_{(u,v)}\text{DP}[v]$ ⟹ $\Theta (V+E)$ · $\max$ for critical path · unbounded knapsack $=$ critical path on $\mathrm{0..}C$.

1️⃣3️⃣ Shortest Paths With Negative Weights (W8)

The sign of the weights picks the algorithm; the number of sources picks it again. Dijkstra with one negative edge is wrong, not suboptimal.

• Bellman-Ford is DP, not greedy ➔ nothing finalised · relaxation identical to Dijkstra’s, every edge every round.
• $V-1$ rounds ➔ a shortest path is simple, $\le V-1$ edges · invariant: after round $i$, every $\le i$-edge distance is correct.
• $V$-th pass $=$ negative-cycle test ➔ any improvement ⟹ negative cycle ⟹ no shortest distances — raise an error.
• Bounds ➔ $\Theta (VE)$ time, $\Theta (V)$ auxiliary (dist, pred only; the trace grid is a revision device) · dense $\Theta (V^3)$.
• Early exit (required) ➔ changed flag; a quiet round is a fixed point ⟹ break · best $\Theta (V+E)$.
• Detection scope [C] ➔ reachable cycles only · weight-$0$ super source ⟹ one $O(VE)$ run · or the Floyd-Warshall diagonal.
• Extract the cycle [C] ➔ walk pred to the first repeat · ⛔ updated vertices may be downstream, not on the cycle.
• Guard $\infty$ [C] ➔ test dist[u] != INF before relaxing.
• Constant shift doesn’t legalise Dijkstra [C] ➔ adds $kc$ to a $k$-edge path, favouring few-edge paths.
• Warshall’s closure ➔ m[i][j] = m[i][j] or (m[i][k] and m[k][j]) ⟹ $\Theta (V^3)$, $\Theta (V^2)$ · directed: $u⇝v\nRightarrow v⇝u$.
• Floyd-Warshall ➔ m[i][j] = min(m[i][j], m[i][k] + m[k][j]) · init diagonal $0$, edges, $\infty$ elsewhere.
• $k$ must be outermost ➔ invariant: after iteration $k$, $\text{m}[i][j]$ is shortest using intermediates $\{\mathrm{1..}k\}$ · ${\text{dist}}^{(k)}[i][j]=\min ({\text{dist}}^{(k-1)}[i][j],{\text{dist}}^{(k-1)}[i][k]+{\text{dist}}^{(k-1)}[k][j])$ · in-place safe (row/col $k$ fixed).
• FW bounds ➔ $\Theta (V^3)$ time, $\Theta (V^2)$ space, all cases · $E$ never appears.
• Negative cycle $⟺$ $\text{m}[u][u]<0$ ➔ finds any cycle in $G$ · every pair routed through it is $-\infty$ · post-process [C]: for negative $\text{m}[k][k]$ set $\text{m}[u][v]=-\infty$ where $\text{m}[u][k],\text{m}[k][v]<\infty$.
• Arbitrage [C] ➔ profit $⟺\prod r_i<1⟺\sum \log r_i<0$ ⟹ FW, read the diagonal.
• Path reconstruction [C] ➔ succ[u][v] = v per edge; on update succ[i][j] = succ[i][k]; follow i = succ[i][j].
• All-pairs selection ➔ $V\times$Dijkstra $O(VE\log V)$ · $V\times$Bellman-Ford $O(V^{2}E)$ · FW $\Theta (V^3)$ · sparse ⟹ Dijkstras (after Johnson’s if some $w<0$), dense ⟹ FW.

Requirement	Algorithm	Time	Aux	Negatives	Detects negative cycle?
Unweighted, single source	BFS	$\Theta (V+E)$	$\Theta (V)$	—	—
$w\ge 0$, single source	Dijkstra	$O(E\log V)$	$\Theta (V)$	❌	❌
Some $w<0$, single source	Bellman-Ford	$\Theta (VE)$	$\Theta (V)$	✅	✅ reachable only
Any negative cycle in $G$	Bellman-Ford $+$ super source	$O(VE)$	$\Theta (V)$	✅	✅ anywhere
Reachability, all pairs	Warshall’s closure	$\Theta (V^3)$	$\Theta (V^2)$	—	—
All pairs, dense	Floyd-Warshall	$\Theta (V^3)$	$\Theta (V^2)$	✅	✅ anywhere
All pairs, sparse, $w\ge 0$	$V\times$ Dijkstra	$O(EV\log V)$	$\Theta (V)$	❌	❌
All pairs, sparse, some $w<0$	Johnson’s	$O(VE\log V)$	$\Theta (V+E)$	✅	✅ via its Bellman-Ford

🎓 Depth

• Johnson’s potentials [D] ➔ $p=$ Bellman-Ford distances from a weight-$0$ super source; $w^{\prime }(u,v)=p[u]-p[v]+w(u,v)\ge 0$ by the triangle inequality; path weights telescope ⟹ $V$ Dijkstras, undo $d=d^{\prime }-p[u]+p[v]$ · $O(VE\log V)$.

1️⃣4️⃣ Tries, Suffix Tries and Suffix Trees (W9 · PT-03)

PT-03 is draw $+$ count: the root is a node, $ alone is a suffix, every word/suffix ends in $. One omission shifts every count by one.

• Trie node ➔ links = [None]*27, $ at $0$, a..z at $\mathrm{1..26}$ ⟹ $O(1)$ child · $ makes app a word after apple; slot $0$ sorts it first.
• Search ➔ $O(M)$ worst, $O(1)$ best, $M$ = query length — $N$ never appears (sorted array / BST: $O(M\log N)$).
• Properties ➔ $N$ words, longest $M$, $T$ total chars incl. $: nodes $\le N(M+1)$, $O(T)$ · leaves $\le N$ · height $M+1$ (count the $ edge).
• Sorted output ➔ in-order DFS, $ first, $O(T)$ · ⛔ prefix + c copies strings ⟹ $O(TM)$.
• Iterative vs recursive [C] ➔ same $O(M)$; auxiliary $O(1)$ vs $O(M)$ · recurse when information flows up.
• Trie vs hash table [C] ➔ exact membership $+$ tight memory ⟹ Hash Table · prefix, order or worst-case bound ⟹ trie.
• Payloads [C] ➔ distinct strings $=$ $ nodes · prefix count: +1 on every node passed at insert ⟹ $O(m)$ query · max of $w_i\times \text{depth}$.
• Suffix trie ➔ trie of the $n+1$ suffixes of S$ · substring $=$ prefix of a suffix ⟹ $O(m)$ · occurrences $=$ leaves below · longest repeat $=$ deepest node with $\ge 2$ children · build $O(n^2)$.
• Suffix tree ➔ compress one-child chains, label edges [start, end] ⟹ $\le 2n+1$ nodes, $\Theta (n)$ space · ⛔ index labels, not text · naive build still $O(n^2)$ (Ukkonen $O(n)$ is FIT3155) · (i, l) $=$ 1-based start $+$ length $\equiv$ [i-1, i+l-2].

PT-03 counts ($D$ = distinct non-empty substrings)	Suffix trie	Suffix tree
Nodes	$D+n+2$	$n+2$ to $2n+1$
Inner nodes	$D+1$	$1$ to $n$
Leaves	$n+1$	$n+1$
Height	$n+1$	$1$ to $n$
$\sum$ edge lengths	$D+n+1$	$D+n+1$
Smallest on	aaaa ($2n+2$ nodes)	all-distinct ($n+2$)
Largest on	all-distinct, $\Theta (n^2)$	aaaa ($2n+1$)

• Distinct substrings [C] ➔ trie: nodes − root − $(n+1)$ $ nodes, $O(n^2)$ · tree: $\sum (\text{end}-\text{start}+1)-(n+1)$ in $O(n)$.
• Think in the trie, answer in the tree [C] ➔
  • longest common substring: tree of s1#s2$, deepest node with leaves from both
  • fewest substrings forming $T$: greedy longest match, restart at root, $O(n+m)$
  • shortest unique: shallowest node with a non-$ leaf edge, depth $+1$
  • shortest absent: shallowest point missing a character
• Suffix array / prefix doubling ➔ not examinable 2026 S2 (🔭 block in Suffix Trie and Suffix Tree).

Query	Structure	Time	Space
Word membership / insert	Trie	$O(M)$	$O(T)$
Words with prefix $p$	Trie $+$ counter	$O(m)$	$O(T)$
Predecessor of a query	Trie	$O(m+n)$	$O(T)$
Substring test / occurrences	tree	$O(m)$ $+$ leaves below	trie $O(n^2)$ · tree $\Theta (n)$
Distinct substrings	suffix tree	$O(n)$ after build	$\Theta (n)$
Longest repeated / common substring	suffix tree	$O(n)$ / $O(n+m)$ after build	$\Theta (n)$
Naive build, either suffix structure	—	$O(n^2)$	—

🎓 Depth

• Predecessor [C] ➔ walk the query remembering the deepest node with a child smaller than the next character; on failure go there, take its greatest smaller child, then greatest children to a leaf ⟹ $O(m+n)$.
• Binary trie [D] ➔ max $x\oplus a_i$: prefer the opposite bit, $O(w)$ · max subarray XOR $=P_R\oplus P_{L-1}$, query-then-insert ⟹ $O(nw)$.
• Trie inside a DP [D] ➔ word break’s prefix test becomes one trie walk ⟹ $O(n^{2}m)\to O(n^2+nm)$ ➔ §1️⃣2️⃣.

1️⃣5️⃣ Self-Balancing Search Trees (W10 · PT-03)

PT-03 may hand you a half-built tree and mix inserts with deletes. Fix the lowest violation first, then keep checking to the root — deletes cascade.

• Why balance ➔ BST ops cost $O(\text{height})$; sorted input ⟹ $O(N)$ · an invariant forces height $O(\log N)$.
• AVL invariant ➔ $bf=h(L)-h(R)\in \{-1,0,1\}$ at every node · hand convention: empty $0$, leaf $1$, annotate h,bf.
• AVL insert/delete ➔ BST op at a leaf (internal delete: swap with predecessor or successor, as asked) → update heights upward → restructure the lowest $|bf|>1$ → continue up.
• Trinode restructure ➔ from $z$ step twice toward the taller child (tie on step 2 ⟹ repeat step 1’s direction ⟹ single rotation) → median key becomes root → re-hang $T_1..T_4$ in order · covers LL, RR, LR, RL.
• AVL bounds ➔ search/insert/delete $O(\log N)$ · heights stored, only the path updated · $\le 2$ rotations per fix, at most one per level.
• 2-3 tree ➔ 2-node: $1$ key, $2$ children · 3-node: $2$ keys, $3$ children · all leaves on one level · $N\ge 2^{h+1}-1$ ⟹ $h=O(\log N)$.
• 2-3 insert ➔ descend (key met anywhere ⟹ do nothing) → insert at the leaf → a 4-node splits, median up → repeat · root split is the only way height grows.
• 2-3 delete (top-down) ➔ never enter a 2-node; internal key ⟹ swap with pred/succ first
  • 2-node root over two 2-nodes ⟹ merge into a 4-node
  • 3-node sibling ⟹ rotate (sibling key up, parent key down)
  • 2-node sibling ⟹ merge child $+$ parent key $+$ sibling
  • remove at the leaf, then split leftover 4-nodes on the way up
• LLRB encoding ➔ colour lives on the child edge · 2-node $=$ black · 3-node $[ab]$ $=$ black $b$ with red left $a$ · no red–red · root black · black-height $=$ 2-3 height.
• LLRB insert ➔ new red leaf → right red, left not red ⟹ rotate left · both children red ⟹ flip · two left reds in a row ⟹ rotate right, then flip · red right of a red left ⟹ rotate left first → propagate → root black · no delete in FIT2004.
• 2-3 ⟷ LLRB [C] ➔ flip $=$ split · root recoloured black $=$ root split · rotate left $=$ redraw a 3-node leaning left — check one answer with the other.

Tree	Balance rule	Insert fix	Delete fix	Time
AVL Tree	$|bf|\le 1$ per node	trinode restructure	swap to leaf $+$ restructure, cascades	$O(\log N)$
2-3 Tree	all leaves level	split $+$ promote	top-down rotate / merge	$O(\log N)$
LLRB	equal black edges per path	rotate L / rotate R / flip	not in FIT2004	$O(\log N)$

🎓 Depth

• AVL height is $O(\log n)$ [D] ➔ sparsest tree $n(h)=1+n(h-1)+n(h-2)=F(h+2)-1$; $F(h)\ge 1.5^{h-1}$ ⟹ $h\le {\log }_{1.5}(n+1)-1$.
• Rotation correctness [C] ➔ read subtree heights off the given $bf$s, rebuild, show $bf=0$ at the three moved nodes.
• BST insert/delete correctness [C] ➔ successor of a two-child $x$ has no left child · for $x\notin T$ exactly one of “successor has no left child” / “predecessor has no right child” ⟹ unique insertion slot.
• Minimal-height BST [C] ➔ sort, median as root, recurse ⟹ $H(n)\le 1+H(n/2)$ · $\Theta (n\log n)$ is optimal, else sorting beats its lower bound.
• LLRB height [D] ➔ no two reds in a row ⟹ drawn height $\le 2\times$ black-height $+1$.

1️⃣6️⃣ Network Flow (W11 · PT-03)

Two sign rules: the residual backward edge has capacity $f$; a cut's capacity counts $S\to T$ edges only, while its flow subtracts $T\to S$ flow.

• Flow network ➔ directed, $c\ge 0$, source $s$ (no in-edges), target $t$ (no out-edges) · $0\le f\le c$ · conservation in $=$ out at $v\notin \{s,t\}$ · $|f|=$ net out of $s$ $=$ net into $t$.
• Residual network $G_f$ ➔ edge $u\to v$ gives forward $c-f$ and backward $f$; drop zeros, merge parallels · $\le 2E$ edges · check $r(u,v)+r(v,u)=c(u,v)+c(v,u)$.
• Augment ➔ any $s⇝t$ path in $G_f$ · $b=\min$ residual · forward $+b$, backward cancels $-b$ · no path ⟹ maximum · forward and backward edges traversed alike (BFS is best).
• Why backward edges ➔ the lecture network stalls at $19$ with forward pushes only; cancelling $4$ via backward $b\to c$ reaches $23$.
• Reading $G$ off $G_f$ ➔ flow $=$ backward weight · capacity $=$ forward $+$ backward (the sanity-check sheet’s “flow $=$ forward” is a slip).
• FF bounds [C] ➔ $O(V+E)$ per augment, $\le F$ augments ⟹ $O(FE)$ pseudo-polynomial · unit capacities $O(VE)$ · Edmonds–Karp $O(V{E}^2)$ · space $\Theta (V+E)$ · integer capacities ⟹ integer flows.
• Answer not unique ➔ max-flow value fixed; the edge assignment and min cut may differ.
• Cut $(S,T)$ ➔ $s\in S,t\in T$ · capacity $=\sum c(S\to T)$ · flow $=\sum f(S\to T)-\sum f(T\to S)$.
• Find the min cut ➔ FF to completion → search from $s$ in the final residual → $S=$ reached → sum $S\to T$ capacities, confirm $=|f|$ · ⛔ searching $G$ instead of $G_f$.
• PT-03 run question ➔ may start mid-stage (expect a backward augment) · self-check: re-run from blank — same max flow, maybe a different cut.
• PT-03 modelling checklist ➔ vertices · directed edges · edge count · capacities · lower bounds · demands — each read off the question.
• Reductions ➔ transform the input, never modify FF · owe construction $+$ why max flow $⟺$ answer $+$ read-off.
• $\infty$ edge [C] ➔ never crosses $S\to T$ in a finite min cut ⟹ "$u\in S\Rightarrow v\in S$" — prerequisites, pinned cells.

Question asks	Build	Read off
how much gets through	the network as given	$|f|$
several sources / sinks	$s^{\ast }\to s_i$ cap out-capacity of $s_i$ · $t_j\to t^{\ast }$ cap in-capacity	$|f|$, value unchanged
node throughput limit	split $v_{in}\to v_{out}$ cap $c(v)$ ⟹ $V^{\prime }=2V-2$	$|f|$
pair two groups	$s\to L$, $L\to R$, $R\to t$ all cap $1$ · quota: $s\to \ell$ cap $q$	middle edges with flow
exact counts per row / category	$s\to a_i$ cap $r_i$ · $a_i\to b_j$ cap $1$ · $b_j\to t$ cap $c_j$	feasible $⟺|f|=\sum r_i$, $X_{ij}=f(a_i,b_j)$
edge- / vertex-disjoint paths	unit capacities ($+$ split, cap $1$)	$|f|$, $O(VE)$
cheapest two-way assignment	$s\to j$ cap cost on computer-s · $j\to t$ cap cost on computer-t · two opposite penalty edges per pair	$j\in S$ ⟹ computer-t; cut $=$ min cost
subset with prerequisites, max profit	$s\to x$ cap $p$ ($p>0$) · $x\to t$ cap $-p$ ($p<0$) · $x\to y$ cap $\infty$	$S$ $=$ chosen; profit $=\sum p^{+}-$ min cut
fencing / segmentation	$s\to$ boundary $\infty$ · $s\to$ ground $c_{\text{dig}}$ · hole $\to t$ $c_{\text{fill}}$ · paired $c_{\text{fence}}$	min cut $=$ min cost
fewest paths covering a DAG	$u_L\to v_R$ per edge, max matching $M$	$|V|-|M|$
“at least” on a link, fixed supplies / needs	circulation (§1️⃣7️⃣)	feasible $⟺$ super-edges saturated

🎓 Depth

• Every cut carries $|f|$ [D] ➔ sum conservation over $S$: only $s$ is non-zero, $S$–$S$ edges cancel.
• Weak duality [D] ➔ $|f|=f(S,T)\le c(S,T)$ ⟹ a flow equal to some cut capacity is maximum.
• Max-flow $=$ min-cut [D] ➔ at FF’s exit, $S=$ reachable in $G_f$: every $S\to T$ edge saturated, every $T\to S$ edge empty ⟹ $|f|=c(S,T)$ — this $+$ termination is FF’s correctness proof.
• Edmonds–Karp $O(V{E}^2)$ [D] ➔ BFS distances never shrink; each edge is the bottleneck $\le V/2$ times ⟹ $O(VE)$ augments $\times O(E)$ (beyond the provided material).
• Min-cut split drill [C] ➔ cost $13$, $S=\{s,a,b\}$; penalty $p$ gives $\min (11+p,17)$, flipping at $p=6$.
• Path cover, why [C] ➔ each match picks a successor; unmatched left copies are path ends.

1️⃣7️⃣ Circulation with Demands and Lower Bounds (W12)

$d_v<0$ is a supplier (edge from $s$); lower bounds enter $d^{\ast }$ as minus incoming, plus outgoing.

• Circulation ➔ $0\le f\le c$ · $\text{in}(v)-\text{out}(v)=d_v$ at every $v$ · no $s$/$t$ · feasibility, not optimisation.
• Feasibility by max flow ➔ $s\to v$ cap $-d_v$ ($d_v<0$), $v\to t$ cap $d_v$ ($d_v>0$), run FF ⟹ feasible $⟺$ every super-edge saturated $⟺|f|=D^{+}$ · delete $s,t$ to read off · quick reject $\sum d_v\ne 0$ (necessary, not sufficient).
• Lower bounds ➔ per edge $⟨u,v,\ell ,c⟩$: $d_u+=\ell$, $d_v-=\ell$, $c-=\ell$ → solve $G^{\ast }$ → $f=\ell +f^{\ast }$ · check $\sum d_v^{\ast }=\sum d_v$.
• Infeasibility certificate [C] ➔ a cut of capacity $<D^{+}$ · Clayton network: $d_w^{\ast }=4$ but in-capacity $3$.
• Modelling ➔ exact count at a vertex $=$ demand · range on a link $=[\ell ,c]$ · per-item ranges with a fixed total ⟹ extra vertex carrying $-D$ · cap on a group of edges ⟹ selector vertex.
• Lecture applications [C] ➔ survey: $q\to c_i$ $[c_i^{-},c_i^{+}]$, $c_i\to p_j$ $[0,1]$, $p_j\to f$ $[p_j^{-},p_j^{+}]$, closing $f\to q$ · airline: route $[1,1]$, $s\to \text{dep}$ / $\text{arr}\to t$ / chain $[0,1]$, $s\to t$ $[0,k]$, $d_s=-k$, $d_t=k$.

🎓 Depth

• Why the test is exact [D] ➔ (⟸) saturated $s\to v$ supplies exactly $-d_v$ · (⟹) feasible circulation $+$ full super-edges has value $D^{+}=c(\{s\},\cdot )$ ⟹ maximum by weak duality.
• Cost [D] ➔ transform $O(V+E)$, FF $O(D^{+}(V+E))$ — pseudo-polynomial in demands; space $\Theta (V+E)$.
• Baseball elimination [D] ➔ $x$ wins all ⟹ $y$ · $G_{i,j}$ ($d=-r_{ij}$) $\to T_i,T_j$ cap $r_{ij}$ · $T_i\to A$ cap $y-w_i$ · $d_A=\sum r_{ij}$ ⟹ feasible $⟺$ $x$ can finish at least tied.