Algorithms (Advanced)

1. Network Flow

1.1 Flow Networks

A flow network is a directed graph $G = (V, E)$ with:

• A source $s \in V$ and a sink $t \in V$.
• A capacity function $c : E \to \mathbb{R}_{\geq 0}$.
• For every edge $(u, v) \in E$The reverse edge $(v, u) \notin E$ (we can add reverse edges with capacity 0).

A flow is a function $f : V \times V \to \mathbb{R}_{\geq 0}$ satisfying:

1. Capacity constraint: $0 \leq f(u, v) \leq c(u, v)$ for all $(u, v) \in E$.
2. Flow conservation: $\sum_{v \in V} f(v, u) = \sum_{v \in V} f(u, v)$ for all $u \in V \setminus \{s, t\}$.

The value of a flow is $|f| = \sum_{v \in V} f(s, v) - \sum_{v \in V} f(v, s) = \sum_{v \in V} f(v, t) - \sum_{v \in V} f(t, v)$.

Theorem 1.1 (Max-Flow Min-Cut). The maximum value of a flow from $s$ to $t$ equals the minimum capacity of an $s$-$t$ cut.

Proof. Let $f^*$ be a maximum flow. Let $S$ be the set of vertices reachable from $s$ in the residual graph $G_f$ (the graph with edges of positive residual capacity). Since $f^*$ is maximum, $t \notin S$. The cut $(S, V \setminus S)$ has capacity equal to $|f^*|$:

1. Every edge from $S$ to $V \setminus S$ is saturated by $f^*$ (otherwise it would have residual capacity and $V \setminus S$ would contain a vertex reachable from $s$).
2. Every edge from $V \setminus S$ to $S$ carries zero flow (otherwise the reverse edge in the residual graph would provide a path from $s$ into $S$).

Therefore $|f^*| = \sum_{u \in S, v \in V \setminus S} f^*(u, v) - \sum_{u \in S, v \in V \setminus S} f^*(v, u) = \sum_{u \in S, v \in V \setminus S} c(u, v)$.

Since any flow has value at most the capacity of any cut, and we have found a cut with capacity $|f^*|$The maximum flow equals the minimum cut. $\blacksquare$

1.2 Ford-Fulkerson Method

The Ford-Fulkerson method iteratively finds augmenting paths in the residual graph and pushes flow along them.

Residual capacity: $c_f(u, v) = c(u, v) - f(u, v)$ (forward edge) or $c_f(u, v) = f(v, u)$ (reverse edge).

Algorithm:

Ford-Fulkerson(G, s, t, c):
    initialize f(u, v) = 0 for all (u, v)
    while there exists an augmenting path P from s to t in G_f:
        c_f(P) = min{c_f(u, v) : (u, v) in P}
        for each (u, v) in P:
            f(u, v) += c_f(P)
            f(v, u) -= c_f(P)
    return f

Theorem 1.2. If all capacities are integers, the Ford-Fulkerson method terminates with a maximum flow after at most $|f^*|$ augmentations, where $|f^*|$ is the value of the maximum flow.

Proof. Each augmentation increases the flow value by at least 1 (since capacities are integers, the residual capacity of any path is at least 1). The flow value cannot exceed $|f^*|$So at most $|f^*|$ augmentations occur. $\blacksquare$

Corollary. With integer capacities, the running time is $O(E \cdot |f^*|)$.

Note on irrational capacities. If capacities are irrational, Ford-Fulkerson may not terminate. It may converge to a value strictly less than the maximum.

1.3 Edmonds-Karp Algorithm

The Edmonds-Karp algorithm is Ford-Fulkerson where augmenting paths are found using BFS (shortest augmenting path in terms of number of edges).

Theorem 1.3. Edmonds-Karp runs in $O(VE^2)$ time.

Proof. The key insight is that each edge can become a “critical edge” (the bottleneck of an augmenting path) at most $O(V)$ times. Each time an edge $(u, v)$ becomes critical, the distance from $s$ to $u$ in the residual graph strictly increases. Since the distance from $s$ to any vertex is at most $V - 1$Each edge can become critical at most $V/2$ times (the distance increases by at least 2). With $E$ edges, the total number of augmentations is $O(VE)$. Each BFS takes $O(E)$Giving $O(VE^2)$. $\blacksquare$

1.4 Applications of Maximum Flow

Bipartite matching. Given a bipartite graph with partitions $L$ and $R$Create a flow network: source $s$ connected to all $u \in L$ with capacity 1, all edges $(u, v)$ with $u \in L$, $v \in R$ have capacity 1, all $v \in R$ connected to sink $t$ with capacity 1. Maximum flow = maximum matching.

Theorem 1.4. The maximum matching in a bipartite graph with $|L| = n_1$ and $|R| = n_2$ can be found in $O(V E^2)$ time using Edmonds-Karp.

Hall’s Theorem via max-flow. A bipartite graph has a matching covering $L$ if and only if $|N(S)| \geq |S|$ for all $S \subseteq L$. This follows from max-flow min-cut: the cut $(\{s\} \cup S \cup N(S), \ldots)$ has capacity $|L| - |S| + |N(S)|$. Hall’s condition ensures this is at least $|L|$.

Other applications:

• Image segmentation: Pixels are vertices, edges between adjacent pixels have capacity proportional to similarity. Source connects to foreground seeds, sink to background seeds.
• Project selection: Max-flow on a network encoding project profits (as source edges) and costs (as sink edges) finds the optimal set of projects.
• Baseball elimination: Determine if a team can still win its division by constructing a flow network.

1.5 Minimum Cost Maximum Flow

In a minimum cost maximum flow problem, each edge $(u, v)$ has a cost $w(u, v)$ per unit of flow, in addition to its capacity. The goal is to find a maximum flow of minimum total cost.

Total cost: $\mathrm{cost}(f) = \sum_{(u,v) \in E} f(u,v) \cdot w(u,v)$.

Algorithm (Successive Shortest Paths):

1. Start with zero flow.
2. While an augmenting path exists, find the shortest (minimum cost) path from $s$ to $t$ in the residual graph (using edge costs as weights, with reverse edges having negative costs).
3. Push as much flow as possible along this path.
4. Update the residual graph.

Theorem 1.5. If all edge costs are non-negative and there are no negative-cost cycles in the residual graph, the successive shortest paths algorithm finds the minimum cost maximum flow.

Running time: $O(F \cdot E \log V)$ where $F$ is the maximum flow value (using Dijkstra for shortest paths). With capacity scaling, this improves to $O(E \log V \cdot (E + V \log V) \cdot \log(UC))$ where $U$ is the maximum capacity and $C$ the maximum cost.

2. Advanced Dynamic Programming

2.1 Interval Scheduling and Weighted Interval Scheduling

Weighted interval scheduling. Given $n$ intervals $[s_i, f_i)$ with weights $w_i$Find a maximum-weight subset of non-overlapping intervals.

DP formulation. Sort intervals by finish time $f_1 \leq f_2 \leq \cdots \leq f_n$. Define $p(j)$ = the largest index $i < j$ such that interval $i$ does not overlap interval $j$ (i.e., $f_i \leq s_j$).

$OPT(j) = \max\{w_j + OPT(p(j)),\ OPT(j-1)\}$

Base case: $OPT(0) = 0$.

Running time: $O(n \log n)$ for sorting + computing $p(j)$ using binary search. $O(n)$ for the DP itself. Total: $O(n \log n)$.

Theorem 2.1. The weighted interval scheduling DP correctly computes the maximum weight of non-overlapping intervals.

Proof. By strong induction on $j$. For the optimal solution for intervals $\{1, \ldots, j\}$Either interval $j$ is included (then the remaining solution is optimal for $\{1, \ldots, p(j)\}$By optimal substructure) or it is not (then the solution is optimal for $\{1, \ldots, j-1\}$). The recurrence considers both cases. $\blacksquare$

2.2 Optimal Binary Search Tree

Given $n$ keys $k_1 < k_2 < \cdots < k_n$ with search probabilities $p_1, p_2, \ldots, p_n$ and dummy key probabilities $q_0, q_1, \ldots, q_n$ (for searches between keys), find a BST minimising the expected search cost.

Expected cost: $E[\text{cost}] = \sum_{i=1}^{n} (d(k_i) + 1) \cdot p_i + \sum_{j=0}^{n} (d(d_j) + 1) \cdot q_j$

Where $d$ is the depth of the node and $d_j$ is the depth of dummy key $j$.

DP formulation: Let $e[i, j]$ be the expected search cost for keys $k_i, \ldots, k_j$.

$e[i, j] = \begin{cases} q_{i-1} & \text{if} j = i - 1 \\ \min_{r=i}^{j}\{e[i, r-1] + e[r+1, j] + w(i, j)\} & \text{if} i \leq j \end{cases}$

Where $w(i, j) = \sum_{l=i}^{j} p_l + \sum_{l=i-1}^{j} q_l$ is the total probability of the subtree.

Running time: $O(n^3)$ (Knuth’s optimisation reduces this to $O(n^2)$ when the cost function satisfies the quadrangle inequality).

Theorem 2.2 (Knuth’s Optimisation). If the optimal root of $e[i, j]$ is monotone (i.e., $\mathrm{root}[i, j-1] \leq \mathrm{root}[i, j] \leq \mathrm{root}[i+1, j]$), then the DP can be computed in $O(n^2)$ time by restricting the search range for the root.

2.3 Bitmask Dynamic Programming

Bitmask DP is used when the state involves a subset of $n$ elements (with $n \leq 20$ ). The bitmask $S \subseteq \{0, \ldots, n-1\}$ is represented as an integer where bit $i$ is set iff $i \in S$.

The Travelling Salesman Problem (TSP). Find the shortest tour visiting all $n$ cities exactly once and returning to the start.

$dp[S][i] = \text{minimum} cost to visit all cities in S \text{ starting} from city 0, ending at city i$

Recurrence:

$dp[S][i] = \min_{j \in S, j \neq i} \{dp[S \setminus \{i\}][j] + \text{dist}(j, i)\}$

Base case: $dp[\{0\}][0] = 0$, $dp[S][i] = \infty$ for $i \notin S$.

Answer: $\min_i \{dp[\{0, 1, \ldots, n-1\}][i] + \text{dist}(i, 0)\}$.

Running time: $O(2^n \cdot n^2)$.

Theorem 2.3. The bitmask DP solves TSP exactly in $O(2^n \cdot n^2)$ time and $O(2^n \cdot n)$ space.

2.4 DP Optimisation Techniques

2.4.1 Divide and Conquer DP

When the recurrence has the form $dp[i][j] = \min_{k < j} \{dp[i-1][k] + C(k, j)\}$ and the optimal $k$ is monotone in $j$We can use divide and conquer to compute each row in $O(n \log n)$ instead of $O(n^2)$.

Theorem 2.4 (Monge / Quadrangle Inequality). If $C$ satisfies the quadrangle inequality $C(a, c) + C(b, d) \leq C(a, d) + C(b, c)$ for all $a \leq b \leq c \leq d$Then the optimal split point is monotone.

2.4.2 Convex Hull Trick

When the recurrence is $dp[i] = \min_j \{dp[j] + a[i] \cdot b[j] + c[j]\}$And the lines $y = b[j] \cdot x + (dp[j] + c[j])$ are added in order of slope, we can maintain a convex hull of lines and query in $O(\log n)$ per step.

Total time: $O(n \log n)$ instead of $O(n^2)$.

:::caution Common Pitfall When applying DP optimisations, always verify that the required conditions hold. Knuth’s optimisation requires the quadrangle inequality AND monotonicity of the optimal split point. The convex hull trick requires lines to be added in monotone order of slope. Applying these optimisations without verifying the conditions leads to incorrect results.

3. String Algorithms

3.1 String Matching

Naive algorithm: Try matching the pattern $P$ (length $m$) at every position in the text $T$ (length $n$). Worst case: $O(nm)$.

3.2 Knuth-Morris-Pratt (KMP) Algorithm

KMP precomputes a failure function (or “prefix function”) for the pattern, allowing the search to skip redundant comparisons.

Prefix function: $\pi[i] =$ the length of the longest proper prefix of $P[0..i]$ that is also a suffix of $P[0..i]$.

Construction: $O(m)$ time.

compute_prefix_function(P):
    pi[0] = 0
    k = 0
    for i = 1 to m-1:
        while k > 0 and P[k] != P[i]:
            k = pi[k-1]
        if P[k] == P[i]:
            k++
        pi[i] = k

Search: $O(n)$ time.

KMP_search(T, P):
    k = 0
    for i = 0 to n-1:
        while k > 0 and P[k] != T[i]:
            k = pi[k-1]
        if P[k] == T[i]:
            k++
        if k == m:
            report match at i - m + 1
            k = pi[k-1]

Theorem 3.1. KMP searches for a pattern of length $m$ in a text of length $n$ in $O(n + m)$ time.

Proof. The key observation is that the variable $k$ (the current match length) increases by at most 1 in each iteration of the outer loop, and decreases by at least 1 each time the while loop executes. Since $k$ starts at 0 and never exceeds $m$The total number of decreases across all iterations is at most $n$ (the number of increases). The total work is $O(n + m)$. $\blacksquare$

3.3 Rabin-Karp Algorithm

Rabin-Karp uses hashing to compare the pattern with substrings of the text in $O(1)$ average time per comparison.

Rolling hash. Given a hash function $h(s) = \left(\sum_{i=0}^{m-1} s[i] \cdot p^{m-1-i}\right) \bmod q$The hash of the substring $T[i+1..i+m]$ can be computed from the hash of $T[i..i+m-1]$ in $O(1)$:

$h(T[i+1..i+m]) = (h(T[i..i+m-1]) - T[i] \cdot p^{m-1}) \cdot p + T[i+m] \pmod q$

Expected time: $O(n + m)$ average, $O(nm)$ worst case (when many hash collisions occur).

3.4 Aho-Corasick Algorithm

The Aho-Corasick algorithm finds all occurrences of a set of patterns $\{P_1, P_2, \ldots, P_k\}$ in a text $T$ in $O(n + m + z)$ time, where $m = \sum |P_i|$ and $z$ is the number of matches.

Structure: A trie of all patterns augmented with failure links (similar to KMP’s prefix function but for a trie).

Failure link of node $v$: the longest proper suffix of the string represented by $v$ that is a prefix of some pattern.

Theorem 3.2. Aho-Corasick processes the text in $O(n + m + z)$ time and uses $O(m)$ space.

4. Computational Geometry Fundamentals

4.1 Line Segment Intersection

Bentley-Ottmann algorithm. Finds all $k$ intersections among $n$ line segments in $O((n + k) \log n)$ time.

Sweep line approach. Sweep a vertical line from left to right. Maintain two data structures:

• Event queue: Priority queue of x-coordinates of segment endpoints and intersection points.
• Status structure: Ordered set of segments currently intersected by the sweep line.

At each event point:

1. Add or remove segments from the status structure.
2. Check for new intersections between adjacent segments in the status structure.

4.2 Convex Hull

The convex hull of a set of points $S \subset \mathbb{R}^2$ is the smallest convex polygon containing $S$.

Graham scan. $O(n \log n)$ time.

1. Find the lowest point $p_0$ (leftmost if tie).
2. Sort remaining points by polar angle with $p_0$.
3. Process points in order, maintaining a stack. For each new point, pop from the stack while the last two points and the new point make a non-left turn.

Theorem 4.1. Graham scan computes the convex hull of $n$ points in $O(n \log n)$ time.

Andrew’s monotone chain. An alternative that sorts by x-coordinate (then y-coordinate) and builds the upper and lower hulls separately. Also $O(n \log n)$.

Chan’s algorithm. Combines Graham scan with a binary search to achieve $O(n \log h)$ time, where $h$ is the number of hull vertices. Useful when $h \ll n$.

4.3 Closest Pair of Points

Divide and conquer algorithm. $O(n \log n)$ time.

1. Sort points by x-coordinate. Divide into two halves by a vertical line.
2. Recursively find the closest pair in each half. Let $\delta = \min(\delta_L, \delta_R)$.
3. Find the closest pair with one point in each half. Only need to check points within distance $\delta$ of the dividing line, and within each such point’s $\delta \times 2\delta$ rectangle, there are at most 6 other points.

Theorem 4.2. The divide-and-conquer closest pair algorithm runs in $O(n \log n)$ time.

Proof. The recurrence is $T(n) = 2T(n/2) + O(n)$ (the combine step examines $O(n)$ points). By the Master Theorem, $T(n) = O(n \log n)$. $\blacksquare$

5. Approximation Algorithms

5.1 Introduction

An $\alpha$-approximation algorithm for a minimisation problem returns a solution with cost at most $\alpha \cdot \mathrm{OPT}$. For a maximisation problem, the solution has value at least $\mathrm{OPT} / \alpha$.

5.2 Vertex Cover — 2-Approximation

Problem. Find the minimum set of vertices that touches every edge.

Algorithm: Repeatedly pick an arbitrary edge $(u, v)$Add both $u$ and $v$ to the cover, and remove all edges incident to $u$ or $v$.

Theorem 5.1. This algorithm gives a 2-approximation for minimum vertex cover.

Proof. The algorithm picks a set $C$ of edges that form a matching (no two share a vertex). For each edge in $C$Both endpoints are added to the cover, so $|S| = 2|C|$. Any vertex cover must include at least one endpoint of each edge in $C$ (since $C$ is a matching), so $\mathrm{OPT} \geq |C|$. Therefore $|S| = 2|C| \leq 2 \cdot \mathrm{OPT}$. $\blacksquare$

5.3 Metric TSP — 2-Approximation

Problem. Find the shortest tour visiting all cities (triangle inequality assumed).

Algorithm:

1. Compute a minimum spanning tree (MST) of the cities.
2. Double every edge in the MST (creating an Eulerian graph).
3. Find an Eulerian tour of the doubled MST.
4. Shortcut the Eulerian tour (skip already-visited cities) to get a Hamiltonian cycle.

Theorem 5.2. This gives a 2-approximation for metric TSP.

Proof. The cost of the MST is at most OPT (removing any edge from the optimal tour gives a spanning tree). The doubled MST costs $2 \cdot \mathrm{MST} \leq 2 \cdot \mathrm{OPT}$. By the triangle inequality, shortcutting does not increase the cost. Therefore the final tour costs at most $2 \cdot \mathrm{OPT}$. $\blacksquare$

Christofides’ algorithm improves this to a $3/2$-approximation by finding a minimum-weight perfect matching on the odd-degree vertices of the MST and combining it with the MST to form an Eulerian graph. This was the best known approximation for 40 years until 2020, when a $(3/2 - \epsilon)$-approximation was discovered.

5.4 Set Cover — $\ln n$-Approximation

Problem. Given a universe $U$ of $n$ elements and a collection $\mathcal{S}$ of subsets of $U$Find the minimum number of subsets from $\mathcal{S}$ whose union is $U$.

Greedy algorithm: Repeatedly pick the set covering the most uncovered elements.

Theorem 5.3. The greedy algorithm gives a $(\ln n + 1)$-approximation for set cover. Furthermore, unless $\text{P} = \text{NP}$No polynomial-time algorithm can do better than $(1 - o(1)) \ln n$.

Proof (approximation ratio). Let $n_t$ be the number of uncovered elements after $t$ iterations. In iteration $t+1$The greedy algorithm picks a set covering at least $n_t / \mathrm{OPT}$ elements (since OPT sets cover all $n_t$ elements). So $n_{t+1} \leq n_t (1 - 1/\mathrm{OPT})$. After $k = \mathrm{OPT} \cdot \ln n$ iterations, $n_k \leq n(1 - 1/\mathrm{OPT})^{\mathrm{OPT} \cdot \ln n} \leq n \cdot e^{-\ln n} = 1$. $\blacksquare$