Ford-Fulkerson searches the RESIDUAL graph, rather than just the original graph's forward edges, chiefly because:

Backward residual edges let it undo part of an earlier suboptimal routing decision

The original graph has no edges at all

It guarantees the answer is always zero

It removes the need for a source or sink

FFT-based polynomial multiplication achieves its speedup over the naive O(n²) method chiefly by:

Converting to a point-value representation where multiplication is pairwise and cheap, then converting back

Skipping multiplication entirely

Only working for polynomials of degree exactly 1

Requiring an infinite number of points

The KMP string-matching algorithm avoids re-examining already-matched text characters chiefly by:

Precomputing a failure function from the pattern alone before scanning the text

Randomly guessing the next position

Reading the text backwards only

Requiring the pattern and text to be the same length

Which of the following correctly describe a Las Vegas versus a Monte Carlo randomized algorithm? (More than one option may be correct.)

A Las Vegas algorithm always produces a correct answer but has variable running time

A Monte Carlo algorithm runs in bounded time but has a small chance of an incorrect answer

Randomized quicksort's pivot choice is a Las Vegas technique

A Las Vegas algorithm always produces a correct answer but has variable running time

A Monte Carlo algorithm runs in bounded time but has a small chance of an incorrect answer

Both always give incorrect answers

Randomized quicksort's pivot choice is a Las Vegas technique

An approximation algorithm with a 2-approximation guarantee for a minimisation problem means its output is:

Never worse than twice the true optimal value

Always exactly equal to the optimal value

Always exactly half of the optimal value

Completely unrelated to the optimal value

Selected and Advanced Algorithms

This chapter closes Unit 7 with the topics its 'Selected Topics' and 'Advanced Algorithms' sub-items name: number-theoretic algorithms, polynomial arithmetic and the Fast Fourier Transform, string-matching algorithms, and the three families of advanced algorithms (parallel, approximation, randomized) — plus Maximum Flow, which the unit's graph-algorithms sub-item names alongside the BFS, DFS, MST and shortest-path material of the course's Algorithms chapters.

Maximum Flow and the Max-Flow Min-Cut Theorem

In a flow network (a directed graph with edge CAPACITIES, a source s and a sink t), a FLOW assigns each edge a value obeying capacity constraints (flow ≤ capacity) and conservation (inflow = outflow at every vertex except s and t). The Ford-Fulkerson method finds the maximum flow by repeatedly finding an AUGMENTING PATH — a path from s to t in the RESIDUAL GRAPH (which includes 'backward' edges representing flow that could be undone) along which more flow can still be pushed — and adding the bottleneck (minimum residual capacity along that path) to the flow, until no augmenting path remains. The max-flow min-cut theorem states that the value of the maximum flow EXACTLY EQUALS the capacity of the minimum CUT (a partition of vertices into two sets, one containing s and the other t, whose capacity is the sum of capacities of edges crossing from the s-side to the t-side) — so finding one problem's answer solves the other for free.

🎯 Why the residual graph, not the original graph, must be searched

Searching only the original graph's forward edges can get stuck at a locally-good-looking flow that is not globally maximum — the residual graph's backward edges let the algorithm 'undo' part of an earlier, suboptimal routing decision by rerouting flow away from an edge that turns out to be a bottleneck, which is exactly what makes Ford-Fulkerson provably reach the true maximum rather than merely a local optimum.

Number-Theoretic Algorithms, Polynomial Arithmetic and the FFT

The Euclidean algorithm computes gcd(a, b) by repeated division: gcd(a, b) = gcd(b, a mod b), terminating when the remainder is 0 — runs in O(log(min(a, b))) divisions, exponentially faster than trial factorisation, and its EXTENDED form additionally computes integers x, y such that ax + by = gcd(a, b), which is the basis for computing MODULAR MULTIPLICATIVE INVERSES needed throughout number-theoretic cryptography.
Modular exponentiation (computing aᵇ mod n efficiently) uses REPEATED SQUARING: writing b in binary and squaring-and-conditionally-multiplying at each bit, computing aᵇ mod n in O(log b) multiplications rather than b − 1 — this single technique is what makes RSA-style public-key cryptography (which needs modular exponentiation with enormous exponents) computationally feasible at all.
Polynomial multiplication and the FFT: multiplying two degree-n polynomials by the naive convolution formula costs O(n²); the FAST FOURIER TRANSFORM converts each polynomial to its point-value representation at 2n specially-chosen (complex root-of-unity) points in O(n log n), multiplies the point-values PAIRWISE in O(n) (since multiplying at each point is now a single scalar multiplication), then converts back (inverse FFT, also O(n log n)) — the same O(n log n)-versus-O(n²) speedup pattern seen wherever a problem can be moved into a domain where the expensive operation becomes cheap and then moved back.

String-Matching Algorithms

String-matching algorithms, in increasing sophistication
Algorithm	Idea and complexity
Naive matching	Try the pattern at every starting position in the text; on a mismatch, slide by exactly one and retry from scratch — O(nm) worst case, wasting all the partial-match information a mismatch reveals.
KMP (Knuth-Morris-Pratt)	Precomputes a FAILURE FUNCTION from the pattern alone (the length of the longest proper prefix of the pattern that is also a suffix of what matched so far), so on a mismatch it never re-examines a text character already matched — O(n + m), the text is scanned only once.
Rabin-Karp	Uses a rolling hash to compare a hash of the pattern against a hash of each text window in O(1) per shift (amortised); a hash match still needs a direct character comparison to rule out a false positive — average O(n + m), worst case O(nm) under many hash collisions.

Parallel, Approximation and Randomized Algorithms

Parallel algorithms (for sorting, searching, merging) exploit multiple simultaneous processing elements — the standard theoretical model is the PRAM (Parallel Random Access Machine), and a key metric beyond running time is SPEEDUP (sequential time ÷ parallel time) and how it scales with the number of processors, since simply throwing more processors at a problem does not guarantee proportionally more speedup once communication/synchronisation overhead or an inherently sequential bottleneck (Amdahl's law) dominates.
Approximation algorithms trade exactness for a solution PROVABLY within a bounded factor of optimal, computable in polynomial time — used specifically where the exact problem is NP-hard (e.g. the vertex cover approximation that picks both endpoints of every unmatched edge, provably within a factor of 2 of the true minimum vertex cover, in polynomial time). The APPROXIMATION RATIO is the standard way to state how good the guarantee is (a 2-approximation is never worse than twice optimal).
Randomized algorithms use randomness within the algorithm itself, in two named flavours: a LAS VEGAS algorithm always produces a correct answer but has a randomly variable running time (e.g. randomized quicksort's pivot choice, which avoids the O(n²) worst case being deterministically triggerable by an adversary), while a MONTE CARLO algorithm always runs in bounded time but has a small, controllable probability of an INCORRECT answer (e.g. randomized primality testing) — the two names attach to what randomness is being traded for (time guarantee versus correctness guarantee), not to how much randomness is used.

Key takeaways

Ford-Fulkerson finds max flow via repeated augmenting paths in the residual graph; the max-flow min-cut theorem equates the maximum flow's value to the minimum cut's capacity.
The Euclidean algorithm and its extended form underlie modular inverses; repeated squaring makes modular exponentiation (and hence RSA) feasible.
FFT-based polynomial multiplication achieves O(n log n) versus the naive O(n²), by moving to a point-value domain, multiplying pairwise, then converting back.
KMP precomputes a failure function to scan text only once (O(n+m)); Rabin-Karp uses a rolling hash with a direct-comparison check against false positives.
Approximation algorithms trade exactness for a provably-bounded near-optimal answer in polynomial time; Las Vegas algorithms trade running-time guarantees for correctness, Monte Carlo the reverse.

Practice questions (8)

Attempt each one before opening the answer. Every explanation names the tempting wrong option as well as the right one, because that is where marks are lost.

The max-flow min-cut theorem states that:
1. The value of the maximum flow equals the capacity of the minimum cut
2. The maximum flow is always zero
3. No cut ever exists in a flow network
4. The minimum cut is always larger than the maximum flow
Show answer
Answer: A — The value of the maximum flow equals the capacity of the minimum cut
This equality is precisely what lets an algorithm that finds one of the two quantities answer the other for free, and it is what certifies that Ford-Fulkerson has actually reached the true maximum when no augmenting path remains.
Ford-Fulkerson searches the RESIDUAL graph, rather than just the original graph's forward edges, chiefly because:
1. Backward residual edges let it undo part of an earlier suboptimal routing decision
2. The original graph has no edges at all
3. It guarantees the answer is always zero
4. It removes the need for a source or sink
Show answer
Answer: A — Backward residual edges let it undo part of an earlier suboptimal routing decision
Without the ability to reroute flow away from an edge that turns out to be a bottleneck, a purely forward search could get stuck at a locally good but globally suboptimal flow.
Modular exponentiation by repeated squaring computes aᵇ mod n in:
1. O(log b) multiplications
2. b − 1 multiplications
3. O(n²) multiplications
4. Zero multiplications
Show answer
Answer: A — O(log b) multiplications
Writing the exponent in binary and squaring-and-conditionally-multiplying per bit reduces the naive b − 1 multiplications to O(log b), which is exactly what makes exponentiation with cryptographically large exponents feasible.
FFT-based polynomial multiplication achieves its speedup over the naive O(n²) method chiefly by:
1. Converting to a point-value representation where multiplication is pairwise and cheap, then converting back
2. Skipping multiplication entirely
3. Only working for polynomials of degree exactly 1
4. Requiring an infinite number of points
Show answer
Answer: A — Converting to a point-value representation where multiplication is pairwise and cheap, then converting back
Evaluating both polynomials at enough points (O(n log n) via FFT), multiplying value-wise (O(n)) and interpolating back (O(n log n) via inverse FFT) together beat the naive O(n²) convolution for large n.
The KMP string-matching algorithm avoids re-examining already-matched text characters chiefly by:
1. Precomputing a failure function from the pattern alone before scanning the text
2. Randomly guessing the next position
3. Reading the text backwards only
4. Requiring the pattern and text to be the same length
Show answer
Answer: A — Precomputing a failure function from the pattern alone before scanning the text
The failure function, computed once from the pattern before any text scanning begins, tells KMP exactly how far to shift on a mismatch without losing any already-confirmed partial match, achieving O(n + m) with the text scanned only once.
Which of the following correctly describe a Las Vegas versus a Monte Carlo randomized algorithm? (More than one option may be correct.)
1. A Las Vegas algorithm always produces a correct answer but has variable running time
2. A Monte Carlo algorithm runs in bounded time but has a small chance of an incorrect answer
3. Both always give incorrect answers
4. Randomized quicksort's pivot choice is a Las Vegas technique
Show answer
Answer: A — A Las Vegas algorithm always produces a correct answer but has variable running time; B — A Monte Carlo algorithm runs in bounded time but has a small chance of an incorrect answer; D — Randomized quicksort's pivot choice is a Las Vegas technique
Las Vegas trades a fixed running time for guaranteed correctness (randomized quicksort's pivoting is the standard example); Monte Carlo trades guaranteed correctness for a fixed running time — neither is 'always incorrect'.
Name the metric, defined as sequential running time divided by parallel running time, used to measure how much a parallel algorithm actually gains from using multiple processors.
Numerical answer — type the value.
Show answer
Answer: speedup
Speedup is the standard metric, and how it scales with processor count (rather than its value at any one processor count alone) is what reveals whether communication/synchronisation overhead or Amdahl's law's sequential bottleneck is limiting the gain.
An approximation algorithm with a 2-approximation guarantee for a minimisation problem means its output is:
1. Never worse than twice the true optimal value
2. Always exactly equal to the optimal value
3. Always exactly half of the optimal value
4. Completely unrelated to the optimal value
Show answer
Answer: A — Never worse than twice the true optimal value
The approximation ratio bounds the worst-case gap between the algorithm's answer and the true optimum; a 2-approximation guarantees the returned value is at most twice the true minimum, computed in polynomial time despite the underlying problem being NP-hard.