COMP3252 Final Exam Ultimate Cheat Sheet

This document serves as the ultimate summary and cheat sheet for the COMP3252 Algorithm Design and Analysis (advanced) course, mapping directly to the lecture sequence from the slides. It contains step-by-step guides, mathematical correctness proofs, complexity analysis, and exam problem reflections for every algorithm covered.

Quick Ref

1. Algorithm Selection Guide

If you see these keywords in an exam problem, immediately apply this algorithm

• "Shortest path" + "No negative edges": Dijkstra's Algorithm
• "Shortest path" + "Negative edges allowed": Bellman-Ford
• **"All-pairs shortest path" (Every node to every node)****: Floyd-Warshall
• "Tree connecting all nodes" + "Minimum cost/wire/distance": Prim's or Kruskal's (MST)
• "Order tasks" + "Prerequisites/Dependencies": Topological Sort
• "Maximize value" + "Capacity limit" (Items can't be physically split): 0/1 Knapsack (DP)
• "Max throughput" | "Bottlenecks" | "Network capacity": Ford-Fulkerson / Edmonds-Karp
• "Bipartite matching" / "Assigning workers to jobs": Max Flow (Add dummy Source/Sink)
• "Optimal ordering for evaluating expressions": Matrix-Chain Multiplication (DP)
• "Polynomial multiplication" / "Signal convolution": FFT (Fast Fourier Transform)

2. The Master Complexity Table

3. "Red Flags" & Trick Questions (When do they fail?)

Professors love to test edge cases. Watch out for these trap scenarios:

• Greedy fails on 0/1 Knapsack: Picking the absolute max "value-to-weight ratio" fails mathematically if items cannot be fractionally split. You MUST use DP.
• Dijkstra fails on Negative Edges: It permanently locks nodes assuming paths only cleanly increase in geometric sum; negative edges break this invariant mathematics.
• Bellman-Ford fails on Negative Cycles: If a cycle sum is $<0$, you can mathematically loop infinitely to $-\infty$. (However, Bellman-Ford can explicitly DETECT this by running an optional $n$-th iteration!)
• Topological Sort fails on Graph Cycles: It strictly only functions on DAGs.
• Master Theorem fails: If the mapping division fraction doesn't perfectly fit the 3 explicit mathematical bounding boundaries (e.g. non-polynomial gap sizes limit boundaries).

Lecture 1: Divide and Conquer

The Divide and Conquer paradigm generally involves three steps:

1. Divide the problem into a number of subproblems that are smaller instances of the same problem.
2. Conquer the subproblems by solving them recursively. If the subproblem sizes are small enough, simply solve the subproblems in a straightforward manner as the "base case".
3. Merge/Combine the solutions to the subproblems into the solution for the original problem.

1. The Master Theorem

Before analyzing specific algorithms, we need a mathematical tool to systematically evaluate the runtime complexity of divide-and-conquer algorithms based on their recurrence relations.

Theorem Statement:
Let $a \ge 1$ and $b > 1$ be constants. Let $f(n)$ be an asymptotically positive function. Let $T(n)$ be defined on non-negative integers by the recurrence:
$$T(n) = aT(n/b) + f(n)$$
where $n/b$ is interpreted as either $\lceil n/b \rceil$ or $\lfloor n/b \rfloor$. Let $c = \log_b a$.

The asymptotic bound of $T(n)$ is determined by comparing $f(n)$ with $n^c$:

• Case 1 (Leaves dominate): If $f(n) = O(n^{c-\epsilon})$ for some constant $\epsilon > 0$, then $T(n) = \Theta(n^c)$. (Meaning: the cost of merging $f(n)$ is asymptotically smaller than the cost of the split tree leaves $n^c$).

• Case 2 (Perfect balance): If $f(n) = \Theta(n^c)$, then $T(n) = \Theta(n^c \log n)$. (Meaning: the cost is equally distributed across all $\log n$ levels of the recursion tree).

  If $f(n) = \Theta(n^c \log^k n)$ for some $k \ge 0$, then $T(n) = \Theta(n^c \log^{k+1} n)$.

• Case 3 (Root dominates): If $f(n) = \Omega(n^{c+\epsilon})$ for some constant $\epsilon > 0$, and if $a f(n/b) \le d f(n)$ for some constant $d < 1$ and all sufficiently large $n$ (the regularity condition), then $T(n) = \Theta(f(n))$.

2. Merge Sort

Merge Sort is a fundamental sorting algorithm utilizing Divide and Conquer to sort a sequence of $n$ numbers, $a_1, a_2, \dots, a_n$, in ascending order.

2.1 How to use the algorithm (Step-by-step)

Variables: $A$ is the input array; left index $l$; right index $r$.

1. Divide Step: Cut the input array $A[1:n]$ completely in half. That is, split it into $A[1 : \lceil n/2 \rceil]$ and $A[\lceil n/2 \rceil + 1 : n]$.
2. Conquer Step: Recursively call Merge Sort on the two halves until the base case is reached. The base case is when an array has only 1 element, which is trivially sorted.
3. Merge Step: Take the two sorted sequences $A_{left}$ and $A_{right}$, and merge them into a new sorted array.
   • Maintain two pointers, $i=1$ pointing to the current element in $A_{left}$ and $j=1$ pointing to the current element in $A_{right}$.
   • While both sequences are not exhausted, compare $A_{left}[i]$ and $A_{right}[j]$.
   • If $A_{left}[i] \le A_{right}[j]$, append $A_{left}[i]$ to the output sequence and increment $i$.
   • Else, append $A_{right}[j]$ to the output sequence and increment $j$.
   • Once one pointer hits the end of its sequence, append all remaining elements of the unexhausted sequence to the output.

2.2 Correctness Proof

Goal: Prove that Merge Sort correctly sorts any array $A$ of size $n$ into ascending order.
Proof by Strong Mathematical Induction on $n$ (the size of the array):

• Base Case: When $n=1$, the array contains only one element. A single element is automatically sorted. The algorithm correctly returns the single element.
• Inductive Hypothesis: Assume that for any integer $k < n$, Merge Sort correctly sorts an array of size $k$ in ascending order.
• Inductive Step: We must show that Merge Sort correctly sorts an array of size $n$.
  1. The algorithm divides the array of size $n$ into two halves of size $\lceil n/2 \rceil$ and $\lfloor n/2 \rfloor$. Since $n \ge 2$, both halves have sizes strictly smaller than $n$.
  2. By the Inductive Hypothesis, the recursive calls perfectly sort both the left half (let's call it $L$) and the right half ($R$). Thus, we have two properly sorted sequences $L$ and $R$.
  3. Now we prove the correctness of the Merge step. We maintain the loop invariant: At any iteration, the output array contains the sorted elements composed of the currently processed elements from $L$ and $R$, and any remaining element in $L$ and $R$ is greater than or equal to the largest element currently in the output array.
  4. In every step, the merge algorithm compares the smallest unmerged element of $L$ ($L[i]$) with the smallest unmerged element of $R$ ($R[j]$). Since $L$ and $R$ are internally sorted, the global smallest unmerged element must be exactly $\min(L[i], R[j])$. The algorithm selects this exact minimum and appends it to the output, preserving the invariant.
  5. Once one array is exhausted, the other array's remaining elements (which are sorted and strictly $\ge$ everything in the output) are appended. It guarantees a holistically sorted output. By the Principle of Mathematical Induction, Merge Sort is correct for all $n$. $\blacksquare$

2.3 Complexity Analysis

• Time Complexity:
  The recurrence relation is $T(n) = 2T(n/2) + O(n)$.
  Why is it $O(n \log n)$? Using the Master Theorem: $a=2$ (halving), $b=2$, and $f(n)=\Theta(n^1)$ (linear merge step). Here limit bounds $c = \log_2 2 = 1$. Since $f(n) = \Theta(n^c)$, this is exactly Case 2. Thus, bounds $T(n) = \mathbf{O(n \log n)}$.
  (Alternatively, solving by recursion tree shows $\log_2 n$ levels. At each level, the total merge cost across all nodes is exactly $cn$. Summing over $\log_2 n$ levels gives $O(n \log n)$).
• Space Complexity: $\mathbf{O(n)}$ auxiliary space is required for the temporary output arrays during the Merge step.

2.4 Common Exam Problem Types

• Inversion Counting: Modify Merge Sort to count pairs where $i < j$ but $A[i] > A[j]$. In the merge step, when $R[j]$ is strictly less than $L[i]$, it means $R[j]$ is smaller than all remaining elements in $L$ (since $L$ is sorted). So you simply add the number of remaining elements in $L$ to your inversion tally.
• Trace the Recursion Tree: You will be given a small array and asked to draw the sequence of subdivides and then the sequence of sorted merges.

3. Finding the k-th Largest Element (Linear Time Selection)

Problem: Given an unsorted sequence of $n$ elements, find the $k$-th largest (or smallest) element. The median is incredibly important ($k = \lceil n/2 \rceil$).

3.1 How to use the algorithm (Step-by-step)

Variables: Sequence $A$, integer $k$. Our recursive function is Select(A, k). We need $O(n)$ time, so we must avoid sorting (which is $O(n \log n)$).

1. Find an Approximate Median $x$:
   • Divide the sequence $A$ into groups of $5$. (There are $\lceil n/5 \rceil$ groups).
   • Find the exact median of each 5-element group by quick-sorting it ($O(1)$ time per group). This gives a set of medians $X = {x_1, x_2, \dots, x_{\lceil n/5 \rceil}}$.
   • Recursively call the linear selection algorithm on $X$ to find the exact median of these medians! Let this be our "pivot" $x$: $x = \text{Select}(X, \lceil |X|/2 \rceil)$.
2. Partition the Array against $x$:
   • Iterate through $A$ to construct three sequences:
     • $L$: elements $< x$
     • $M$: elements $= x$
     • $R$: elements $> x$
3. Recurse into the correct partition:
   • If $k \le |R|$, the $k$-th largest element lies strictly in $R$. Return Select(R, k).
   • Else if $k \le |R| + |M|$, the $k$-th largest element is $x$ itself. Return $x$.
   • Else, the element lies in $L$. We are looking for the element that is the $(k - |R| - |M|)$-th largest inside $L$. Return Select(L, k - |R| - |M|).

3.2 Correctness Proof

Goal: Prove the median-of-medians partition correctly finds the exact $k$-th largest element in $O(n)$ time.

• Why it finds the target: Notice that the recurrence logic mirrors binary search trees/Quickselect. The actual elements of the array are preserved across mutually exclusive sets $L, M, R$. Thus if we just want the $k$-th element from the combined descending sequence, and we know exactly how many elements are strictly bigger than $x$ ($|R|$), if $k \le |R|$ the answer must be in $R$. If $k$ sits inside the window representing $x$, it's $x$. Otherwise, it's in $L$, with its index "shifted" by the elements we bypassed.
• Why is it strictly $O(n)$ bounds? (The Pivot Quality)
  Why use groups of 5? It guarantees that the partition sizes shrink by a constant fraction, ensuring we avoid the worst-case $O(n^2)$ associated with randomly picking a bad pivot (like in naive Quickselect).
  • Half of the $n/5$ groups have their group median $\ge x$ (since $x$ is the median of medians). So there are about $n/10$ groups.
  • In each of these $n/10$ groups, there are at least 3 elements $\ge$ the group median (because the group size is 5).
  • Hence, there are at least $3 \times (n/10) = 3n/10$ elements that are definitely $\ge x$.
  • This identically means that at most $n - 3n/10 = \mathbf{7n/10}$ elements can be smaller than $x$. (To be precise, it's roughly $3n/4$ in worst case bounds due to floors/ceilings, see syllabus).
    So, neither $L$ nor $R$ will ever be larger than $\frac{3}{4}n$.
    The recurrence relation becomes: $T(n) \le T(\frac{n}{5}) + T(\frac{3n}{4}) + cn$.
• Proof of Complexity via Induction:
  We want to prove $T(n) \le 20cn$.
  • Base Case: For small $n$ ($n \le 5$), $T(n) \le O(1) \le 20cn$.
  • Inductive Step: Assume $T(k) \le 20ck$ for $k < n$. Evaluated at $n$:
    $T(n) \le 20c(\frac{n}{5}) + 20c(\frac{3n}{4}) + cn$
    $T(n) \le 4cn + 15cn + cn = 20cn$.
    Since $T(n) \le 20cn$, the selection algorithm runs strictly in $\mathbf{O(n)}$ time. $\blacksquare$

3.3 Common Exam Problem Types

• Altering group sizes: E.g., "What if we use groups of 3 instead of 5?". You need to re-prove the tree sum. Groups of 3 give $T(n) \le T(n/3) + T(2n/3) + O(n)$. Since $n/3 + 2n/3 = n$, the work done at each level does not geometrically decay, the sum diverges, yielding $O(n \log n)$! Hence $\ge 5$ is required for $O(n)$.
• Deterministic Quickselect Tracing: Be prepared to partition a list of numbers deterministically using to the algorithm.

4. Closest Pair of Points in 2D

Problem: Given $n$ points on a 2D plane, find the pair with the minimum Euclidean distance. Brute force tests all pairs resulting in $O(n^2)$. We need an $O(n \log n)$ approach using D&C.

4.1 How to use the algorithm (Step-by-step)

Variables: Array of points $P = {p_1, \dots, p_n}$.

1. Pre-sort: Sort the set of points $P$ by their $x$-coordinates, enabling quick division. (This is done once).
2. Divide: Find a vertical line (the median $x$-coordinate $x_{mid}$) that splits $P$ exactly into a Left half $P_L$ and Right half $P_R$.
3. Conquer: Recursively call the algorithm on $P_L$ to find its closest pair distance $d_L$, and on $P_R$ for $d_R$.
4. Merge: Let $d = \min(d_L, d_R)$.
   So far, the global minimum is bounded by $d$. The only way a smaller distance exists is if one point of the pair is in $P_L$ and the other is in $P_R$, bridging the median line.
   • Define a "strip" area containing only points whose $x$-coordinates are within a distance $d$ of the dividing median line: $x_{mid} - d \le x \le x_{mid} + d$.
   • Create an array $S$ comprising points strictly inside this strip.
   • Sort $S$ by their $y$-coordinates. (To achieve $O(n \log n)$ overall, this sorting must be done as a linear merge step similar to MergeSort, otherwise sorting at every step makes it $O(n \log^2 n)$).
   • Scan $S$. For each point $p_i$, calculate its distance to the next 11 points down the list (or 7, bounds proved in class). If the distance is $< d$, update $d$ with this new minimum.
5. Return $d$.

4.2 Correctness Proof

Goal: Prove it's sufficient to only check the next 11 points in the $y$-sorted strip.
Geometric Pigeonhole Proof:

• We partitioned the $2d$-wide strip around $x_{mid}$ into small square boxes of size $\frac{d}{2} \times \frac{d}{2}$.
• Both the left side and the right side of the median line enforce that any two points on the exact same side are at least distance $d$ apart (since $d = \min(d_L, d_R)$).
• Because the diagonal of a $\frac{d}{2} \times \frac{d}{2}$ box is $\sqrt{\frac{d^2}{4} + \frac{d^2}{4}} = \frac{d}{\sqrt{2}} < d$, no box can contain more than 1 point.
• If we look at a point $p_i$ and wish to find out how many points could possibly be within a distance $d$ of it, we only need to look at boxes within a strictly horizontal/vertical geometric window of roughly $2d \times 2d$.
• By evaluating the grid rows, we realize there are at most a constant number of points bounded within the $d$-radius of $p_i$. Analysis from the lecture shows the maximum number of neighbors whose $y$-coordinates differ by $\le d$ from $p_i$ is at most 11 (sometimes bounded tighter to 7 by refined geometry).
• Thus, verifying more than 11 elements ahead in the $y$-sorted array is mathematically redundant as their $y$-distance strictly guarantees the Euclidean distance is $> d$. Checking constant bounds secures $O(n)$ in the merge phase. $\blacksquare$

4.3 Complexity Analysis

If $y$-coordinate sorting is done via linear merge simultaneously with returning from recursion limits the split step to:
$T(n) = 2T(n/2) + O(n)$.
By Master Theorem (Case 2, identical to MergeSort), $T(n) = \mathbf{O(n \log n)}$.
Note: If one blindly calls sort() on the strip array inside every recursive call, the recurrence $T(n) = 2T(n/2) + O(n \log n)$ yields $O(n \log^2 n)$, which loses marks in exams!

5. Fast Integer Multiplication (Karatsuba Algorithm)

Problem: Multiply two $n$-bit integers $x$ and $y$. Brute-force vertical multiplication takes $O(n^2)$ time.

5.1 How to use the algorithm (Step-by-step)

Divide each $n$-bit integer into two $n/2$-bit halves:
$x = a \cdot 2^{n/2} + b$
$y = c \cdot 2^{n/2} + d$

Standard distribution yields:
$x \cdot y = ac \cdot 2^n + (ad + bc) \cdot 2^{n/2} + bd$
This involves 4 recursive multiplications of $n/2$-bit numbers (yielding $T(n)=4T(n/2)+O(n) = O(n^2)$, no improvement).

Karatsuba Trick ($O(n^{1.558})$):

1. Compute $P_1 = a \cdot c$
2. Compute $P_2 = b \cdot d$
3. Compute $P_3 = (a + b) \cdot (c + d)$
4. Express the middle cross-terms using the calculated chunks: $ad + bc = P_3 - P_1 - P_2$.
5. Substitute to format the answer shift: $x \cdot y = P_1 \cdot 2^n + (P_3 - P_1 - P_2) \cdot 2^{n/2} + P_2$.

5.2 Complexity Analysis

This strategy replaces 4 recursive multiplications with exactly 3 recursive multiplications, plus some additions which natively execute in $O(n)$ time.
$T(n) = 3T(n/2) + O(n)$.
Using Master Theorem: $a=3$, $b=2$, and $f(n)=O(n)$. Comparing $n^1$ vs $n^{\log_2 3}$, we fall into Case 1 since $\log_2 3 \approx 1.558 > 1$.
Thus $T(n) = \mathbf{O(n^{\log_2 3})} \approx \mathbf{O(n^{1.558})}$.

6. Fast Matrix Multiplication (Strassen's Algorithm)

Problem: Multiply two $n \times n$ matrices $A$ and $B$ to yield matrix $C$. Standard row-by-column calculation is $O(n^3)$.

6.1 The Algorithm & Analysis

Using naive D&C, a matrix is blocked into four $n/2 \times n/2$ quadrants.
$C_{11} = A_{11}B_{11} + A_{12}B_{21}$.
Calculating all 4 quadrants entails 8 multiplications of $n/2$ submatrices.
$T(n) = 8T(n/2) + O(n^2)$. The Master Theorem ($c = \log_2 8 = 3$) states $T(n) = O(n^3)$, giving zero improvement.

Strassen's Trick: Very similarly to Karatsuba, Strassen designed an arbitrary algebra setup calculating intermediate sums $M_1 \dots M_7$ that mathematically eliminates one full matrix multiplication.

• Sub-multiplications reduced from 8 to 7. (Matrix additions take only $O(n^2)$ and increase but remain asymptotically irrelevant).
• Recurrence relation: $T(n) = 7T(n/2) + O(n^2)$.
• By the Master Theorem, $c = \log_2 7 \approx 2.808 > 2$. Thus $T(n) = \mathbf{O(n^{\log_2 7})} \approx \mathbf{O(n^{2.808})}$.

(Note: On the final exam, no professor expects memorization of Strassen's 7 crazy matrix formulas, just the application of its recurrence bounds and understanding of reducing multiplication calls).

Lecture 2: Fast Fourier Transform (FFT)

Problem: The Fast Fourier Transform elegantly multiplies two polynomials in $O(n \log n)$ time, overcoming the brute-force polynomial multiplication (convolution), which takes $O(n^2)$.

1. Representation of Polynomials

A polynomial of degree $n-1$, $p(x) = a_0 + a_1x + a_2x^2 + \dots + a_{n-1}x^{n-1}$, can be represented in two ways:

1. Coefficient Representation: An array of length $n$ containing the coefficients $[a_0, a_1, \dots, a_{n-1}]$.
2. Point-Value Representation: A set of $n$ distinct point-value pairs ${(x_0, y_0), (x_1, y_1), \dots, (x_{n-1}, y_{n-1})}$, where $y_k = p(x_k)$.

Why use Point-Value Representation?
Multiplying two polynomials structured as point-value pairs takes strictly $O(n)$ time! $p(x) \times q(x) = {(x_0, y_0 \times y_0'), \dots, (x_{2n-1}, y_{2n-1} \times y_{2n-1}')}$. We just need enough pairs ($2n-1$) to encapsulate the degree of the new multiplied polynomial. All that remains is efficiently converting coefficients to point-pairs, multiplying in $O(n)$, and converting it back.

2. Forward FFT (Coefficient to Point-Value)

If you blindly evaluate $n$ random $x$ points via Horner's method, that takes $O(n^2)$. FFT picks extremely specific points to make it take $O(n \log n)$.
The selected points are the Complex $n$-th Roots of Unity: $\omega_n^k = e^{i \cdot 2\pi k/n}$, for $k=0, 1, \dots, n-1$.

2.1 How it works (Step-by-step)

Variables: $n$ must be a power of 2. Polynomial array $[a_0, \dots, a_{n-1}]$.

1. Split the coefficients into an even-index polynomial and an odd-index polynomial:
   • $p_{even}(x) = a_0 + a_2x + a_4x^2 + \dots$
   • $p_{odd}(x) = a_1 + a_3x + a_5x^2 + \dots$
   • Notice that $p(x) = p_{even}(x^2) + x \cdot p_{odd}(x^2)$.
2. Calculate the evaluations recursively. The critical mathematical property is that squaring the $n$-th roots of unity yields exactly the $(n/2)$-th roots of unity (Halving Lemma). Thus, evaluating a polynomial of size $n$ at the roots of unity requires evaluating TWO polynomials of size $n/2$ at the roots of unity, perfectly splitting the problem: $T(n) = 2T(n/2) + O(n)$.
3. Recombine solutions via:
   • For $0 \le k < n/2$: $p(\omega_n^k) = p_{even}(\omega_{n/2}^k) + \omega_n^k \cdot p_{odd}(\omega_{n/2}^k)$
   • For $n/2 \le k < n$: $p(\omega_n^k) = p_{even}(\omega_{n/2}^{k - n/2}) - \omega_n^{k-n/2} \cdot p_{odd}(\omega_{n/2}^{k - n/2})$ (Leveraging $\omega_n^{k+n/2} = -\omega_n^k$)

3. Inverse FFT (Point-Value to Coefficient)

Problem: Recovering coefficients means multiplying the $n$-length point-value evaluation vector by the inverse of the Vandermonde matrix.

3.1 Mathematical Proof of Inverse Matrix Correctness

The matrix $V$ has entries $V_{j,k} = \omega_n^{j \cdot k}$. Its inverse $V^{-1}$ has entries $V^{-1}{j,k} = \frac{1}{n} \omega_n^{-j \cdot k}$.
Proof: Let's calculate the product $V \times V^{-1}$ at index $(j,k)$:
$\sum{\ell=0}^{n-1} V_{j,\ell} V^{-1}{\ell, k} = \frac{1}{n} \sum{\ell=0}^{n-1} \omega_n^{j\ell} \omega_n^{-\ell k} = \frac{1}{n} \sum_{\ell=0}^{n-1} \omega_n^{\ell(j-k)}$

• If $j = k$: $\frac{1}{n} \sum_{\ell=0}^{n-1} \omega_n^0 = \frac{1}{n} \sum 1 = 1$.
• If $j \neq k$: This forms a geometric series: $\frac{1}{n} \frac{1 - \omega_n^{n(j-k)}}{1 - \omega_n^{j-k}}$. Because $\omega_n^{n} = 1$, the numerator $1 - 1 = 0$.
  Hence, the product yields the Identity Matrix $I$. $\blacksquare$

Because the inverse matrix entries are simply $\frac{1}{n} \omega_n^{-jk}$, which is identical to the forward FFT structural loop just replacing $\omega_n$ with $\omega_n^{-1}$ and dividing by $n$, Inverse FFT also runs in $O(n \log n)$ using the exact same recursive algorithm.

Lecture 3: Dynamic Programming (Part 1 - Design & Scheduling)

Dynamic Programming (DP) differs from Divide and Conquer: it breaks down problems into overlapping subproblems, solving each subproblem exactly once and storing it (memoization/tabulation) so future queries are $O(1)$.

1. Job Scheduling (Weighted)

Problem: Given $n$ jobs where job $i$ occurs from start $s_i$ to finish $t_i$ and grants value $v_i$, find a subset of non-overlapping jobs that maximizes total value.
(Note: unweighted Job Scheduling just maximizes count, which works flawlessly via a simple Greedy Algorithm: always pick the job that finishes earliest).

1.1 How to use the algorithm (Step-by-step)

Practical Execution:

1. Sort all jobs by their finish time from earliest to latest. Let's call them Job 1, Job 2... Job $n$.
2. Find the last compatible job $p(i)$: For every Job $i$, find the index of the latest job that finishes before Job $i$ starts. If no prior job fits, set it to 0. (Do this quickly with Binary Search).
3. Initialize: Create an array dp of size $n+1$. Set dp[0] = 0.
4. Loop through each job $i$ from 1 to $n$:
   • Option A (Skip it): Copy the best value from the previous jobs, dp[i-1].
   • Option B (Take it): Take this job's value $v_i$, plus the best value of its compatible jobs dp[p(i)].
   • Set dp[i] to the maximum of Option A and Option B.
5. Result: Your max possible value is saved in the final slot dp[n].

Complexity: Overall time limit is $O(n \log n)$.
Why? The bottleneck is strictly computing the preprocessing bounds (sorting by finish times takes $O(n \log n)$ and isolating compatibilities via binary search takes $O(n \log n)$). The dynamic programming loop strictly streams through exactly once ($O(n)$ bounds limit).

2. Matrix-Chain Multiplication

Problem: Multiply a chain of $n$ matrices $A_1 \times A_2 \dots \times A_n$ (where $A_i$ has dimension $d_{i-1} \times d_i$) to minimize the total scalar multiplications. Order matters due to associativity! (e.g. $(AB)C$ vs $A(BC)$).

2.1 How to use the algorithm (Step-by-step)

Practical Execution:

1. Initialize the Table: Create an $n \times n$ table $M$ to store the minimum costs. Set all elements on the main diagonal to 0 ($M[i][i] = 0$).
2. Loop by chain length $s$: Start from $s=1$ up to $n-1$.
3. Loop the starting matrix $i$: Inside the $s$ loop, loop $i$ from $1$ to $n-s$.
4. Define the ending matrix $j$: Set $j = i + s$.
5. Find the best split point $k$: For the current chain block from $A_i$ to $A_j$, try splitting it at every possible matrix $k$ in between ($i \le k < j$).
   • The scalar cost to split at $k$ is: $M[i][k] + M[k+1][j] + (d_{i-1} \times d_k \times d_j)$.
   • Find the single smallest cost across all tested $k$'s, and save it in $M[i][j]$.

Complexity Analysis: Time is $\mathbf{O(n^3)}$, Space is $\mathbf{O(n^2)}$.
Why is it $O(n^3)$? There are naturally $O(n^2)$ table states in the matrix. Resolving the minimum cost strictly enforces checking the split point $k$, requiring up to $O(n)$ steps precisely per cell limit. Multiplying $O(n^2)$ states limit $\times$ $O(n)$ checks bounds precisely strict $\mathbf{O(n^3)}$.

Lecture 3 (approx): The Knapsack Problem & FPTAS

1. 0/1 Knapsack (DP Solution)

Problem: Given $n$ items with weights $w_i > 0$ and values $v_i$, maximize total value inside a capacity $W$. Items cannot be split.

1.1 How to use the algorithm (Step-by-step)

Practical Execution:

1. Initialize a Grid: Create a table dp with $n+1$ rows (for each item 0 to $n$) and $W+1$ columns (for every capacity 0 to $W$). Fill the entire 0-th row with 0s.
2. Iterate row by row: For each item $i$ from 1 to $n$:
   • Iterate capacity: For each limit $j$ from 0 to $W$:
3. Check affordability:
   • If item $i$'s weight is too heavy ($w_i > j$): Just copy the value from the cell directly above it: dp[i, j] = dp[i-1, j].
   • If you can afford it: Compare two options:
     • Option A (Skip): Value from directly above dp[i-1, j].
     • Option B (Take): This item's value $v_i$ PLUS the best value from the remaining capacity dp[i-1, j - w_i].
     • Write the MAX of these two into dp[i, j].
4. Result: Your max value is located at the bottom-right corner dp[n, W]. Backtrack upward to find which items were taken!

Complexity: Space $O(nW)$, Time $\mathbf{O(nW)}$.
Why is it $O(nW)$? The DP grid size is strictly exactly $n \times W$. Calculating each cell's maximum takes purely $O(1)$ constant time (a pure scalar comparison check). Thus, $n \times W \times O(1) = O(nW)$. This is a Pseudo-polynomial runtime since $W$'s size is logarithmically encoded while the runtime natively scales with its pure integer value.

2. Fully Polynomial-Time Approximation Scheme (FPTAS)

Since Knapsack is NP-Complete, we use FPTAS to get a solution $\ge \frac{OPT}{1+\epsilon}$ inside polynomial bounds of $n$ and $1/\epsilon$.
Method: If weights are arbitrarily massive, DP via weights is terrible. We instead DP over values, finding the minimum weight required to reach exactly a value score.

1. To make evaluating large values fast, scale down and chop off the small precision bits of all strictly huge values! Let $v_{max} = \max v_i$.
2. Select parameter $k = \frac{\epsilon v_{max}}{2n}$.
3. Shift all values to $\hat{v}i = \lfloor \frac{v_i}{k} \rfloor$. Now values are extremely crushed bounding the maximum sum parameter array $V = \frac{n \times v{max}}{k} = \frac{2n^2}{\epsilon}$.
4. Run the flipped Knapsack DP to minimize weight aiming for exactly target value $\hat{j}$: Let $dp(i, \hat{j}) = \min(dp(i-1, \hat{j}), dp(i-1, \hat{j} - \hat{v}_i) + w_i)$.
5. Output the subset yielding the max truncated value within capacity $W$.

2.1 Correctness Proof (Approximation Ratio)

Goal: Prove the FPTAS provides value $\ge \frac{OPT}{1+\epsilon}$.

• Let $\hat{S}$ be the output subset using modified values. Let $S_{opt}$ be the theoretic optimal subset for unmodified values.
• Since we round down, $v_i \ge k \hat{v}_i \ge v_i - k$.
• The output of the exact DP on chopped values gives $\hat{S}$. Thus the summation of $\hat{v}$ over $\hat{S}$ MUST mathematically be $\ge$ the summation of $\hat{v}$ over any valid set, including $S_{opt}$.
• Unpacking:
  $\sum_{x \in \hat{S}} v_x \ge k \sum_{x \in \hat{S}} \hat{v}x \ge k \sum{x \in S_{opt}} \hat{v}x \ge k \sum{x \in S_{opt}} (\frac{v_x}{k} - 1)$
• $\sum_{x \in S_{opt}} v_x - k \cdot n$. (Because there are at most $n$ items, losing precision $k$ happens no more than $n$ times).
• Remember $k = \frac{\epsilon \cdot v_{max}}{2n}$. Thus bounded subtraction error is precisely: $OPT - \frac{\epsilon \cdot v_{max}}{2}$.
• Remember $\epsilon < 1$, and $v_{max} \le OPT$. Therefore $\frac{\epsilon}{2} OPT \le \epsilon \cdot OPT$.
• Giving original returned value $\ge OPT (1 - \frac{\epsilon}{2}) \ge \frac{OPT}{1+\epsilon}$. $\blacksquare$

Lecture 4: Shortest Path Dynamic Programming (Bellman-Ford & Floyd-Warshall)

1. Bellman-Ford Algorithm (Single-Source Shortest Path with Negative Edges)

Problem: Find shortest paths from a source node $s$ to all other vertices $v$ in a graph $G=(V, E)$ permitting negative edge weights (provided there remain no negative-weight cycles).
Dijkstra fails here because greedy extraction breaks if future paths offer negative refunds. Bellman-Ford applies DP on the number of edges.

1.1 How to use the algorithm (Step-by-step)

Practical Execution:

1. Initialize: Set the distance to your starting node $s$ as $0$ ($d[s] = 0$). Set the distance to all other nodes to $\infty$ ($d[v] = \infty$).
2. Loop $n-1$ times: (where $n$ is the total number of vertices).
3. Relax Edges: In each loop, go through EVERY edge $(u,v)$ in the graph exactly once.
   • For each edge, check: is $d[u] + \text{weight}(u, v) < d[v]$?
   • If yes, update it: $d[v] = d[u] + \text{weight}(u, v)$.
4. Check for Negative Cycles (Optional 1 extra loop): Run the relaxation on all edges one more time (the $n$-th time). If any distance $d[v]$ STILL gets smaller, your graph has a negative weight cycle and no shortest path exists!

Complexity Analysis:
Why is it $O(n \cdot m)$? It runs $n-1$ outermost loops. Each loop processes all $m$ edges exactly once. Multiplying them gives $O(n \cdot m)$. (When the graph is fully connected completely dense, $m=n^2$, causing $O(n^3)$ limits).

1.2 Detecting Negative Cycles

If the graph contains a negative loop, looping infinitely reduces costs down to $-\infty$.
To computationally capture existence of a negative cycle:

1. Don't trace from just a given $s$ arbitrarily as that sub-graph partition might not access the isolated loop! Introduce a "dummy node" $s_{global}$ holding an initialized distance 0 array binding pointing uniformly to absolutely all vertices!
2. Execute Bellman Ford over this exact $G'$ environment calculating exactly $n$ loops!
3. If after calculating pass $k=n$ versus bounds limit $k=n-1$, you detect strictly a reduction drop $d[v][n] < d[v][n-1]$ somewhere, flag TRUE. A strictly simpler node path bounds out at $n-1$. The loop iteration forces value shedding. Memory resolves $O(n \cdot m)$.

2. Floyd-Warshall Algorithm (All-Pairs Shortest Path)

Problem: Find shortest paths between ALL pairs $(u, v)$ across dense graphs. Simply broadcasting Bellman Ford per nodes costs heavily: $O(n^2 m)$. Floyd-Warshall acts faster on densely populated paths exploiting a localized inner node enumeration bounded DP logic natively targeting $O(n^3)$.

2.1 How to use the algorithm (Step-by-step)

Practical Execution:

1. Initialize the Matrix: Create an $n \times n$ distance matrix $D$.
   • For every diagonal entry, set $D[i][i] = 0$.
   • For every direct edge from $i$ to $j$, set $D[i][j] = \text{weight}(i,j)$.
   • For all other missing edges, set $D[i][j] = \infty$.
2. Three Nested Loops:
   • Outer loop $k$ from $1$ to $n$ (The "stepping stone" node).
   • Middle loop $i$ from $1$ to $n$ (The starting node).
   • Inner loop $j$ from $1$ to $n$ (The ending node).
3. The Core Update: Inside the inner loop, update $D[i][j]$ by checking if going through node $k$ is shorter than the direct path:
   D[i][j] = min(D[i][j], D[i][k] + D[k][j])

Complexity Analysis:
Time limit is $\mathbf{O(n^3)}$. Why? There are exactly 3 nested iterative loops tracing nodes tracing exactly fully $n$ times bounds limit mapping boundaries parameters exactly scaling $n \times n \times n = O(n^3)$ bounds. Dropping matrix scalar $k$ precisely explicitly cleanly simplifies space bounds exactly mapped $O(n^2)$.

Lecture 5 & 5.1: Graph Basics, DFS, BFS & Digraphs

1. Depth-First Search (DFS) & Breadth-First Search (BFS)

Problem: Traverse an undirected (or directed) graph to find connected vertices, identify connected components, output a spanning tree, or detect cycles.

1.1 How to use the algorithms (Step-by-step)

DFS (Depth-First Search): Follow paths as deeply as possible before backtracking.

• Implement using recursion.
• Initialize visited[v] = False for all $v$.
• DFS(u):
  1. visited[u] = True
  2. For each neighbor $w$ of $u$, if visited[w] == False, record $u$ as the parent of $w$ (to trace the Spanning Tree) and recursively call DFS(w).

BFS (Breadth-First Search): Explore layer by layer uniformly.

• Implement using a FIFO Queue.
• Initialize visited array, set visited[root] = True and enqueue the root.
• Loop while Queue is not empty:
  1. Dequeue $v$.
  2. For each neighbor $w$ of $v$, if visited[w] == False, mark it True, enqueue $w$, and record its parent.

Cycle Detection: In DFS, if you are exploring $v$ and encounter a neighbor $w$ that is already visited AND $w \neq \text{parent}[v]$, this is a Backward Edge. A backward edge actively guarantees a cycle exists in the graph.

1.2 Correctness Proof (DFS Connectivity)

Goal: Prove that if $u$ and $v$ are connected in graph $G$, then DFS(u) correctly sets visited[v] = True.
Proof by Contradiction:

1. Suppose $u$ and $v$ are connected by some physical path $P = (v_0, v_1, \dots, v_\ell)$ where $v_0 = u$ and $v_\ell = v$.
2. Assume for the sake of contradiction that visited[v] = False at the end of the algorithm.
3. Since $u$ is the start node, visited[u] = True. Tracing along the path $P$, there must exist some adjacent link $(v_{i-1}, v_i)$ where $v_{i-1}$ was marked True but $v_i$ remained False.
4. However, the definition of DFS ensures that absolutely all neighbors of a visited node are enumerated. Thus, when DFS explored $v_{i-1}$, it necessarily looked at $v_i$. Since $v_i$ was False, DFS would have been forced to explore $v_i$, ensuring visited[v_i] = True.
5. This is a direct contradiction. Thus, all reachable vertices $v$ fundamentally resolve to True. $\blacksquare$

1.3 Complexity Analysis

Time is strictly $\mathbf{O(n+m)}$. Why? Both algorithms process every vertex from the stack/queue exactly once ($O(n)$). Inside the loop, it checks only its direct neighbor edges. Across all nodes, every edge in the graph is checked at most twice ($2m$), yielding $O(m)$ work. Thus: $O(n) + O(m) = O(n+m)$.

2. Topological Sorting (Directed Acyclic Graphs)

Problem: Given a Directed Acyclic Graph (DAG), order the vertices so that all directed edges perfectly point from left to right (from earlier vertices to later vertices).

2.1 How to use the algorithm (Step-by-step)

In-Degree Method ($O(n+m)$):

1. Compute the in-degree (number of incoming edges) for all vertices.
2. Load all vertices with in-degree == 0 (Source vertices) into a queue $Z$.
3. Keep a counter starting at $1$.
4. Loop while $Z$ is not empty:
   • Pop vertex $u$ and assign it the current counter label. Increment the counter.
   • For all outgoing edges $(u, w)$, decrement the local in-degree[w] by $1$.
   • If in-degree[w] drops identically to $0$, enqueue $w$ into $Z$.

Complexity: $\mathbf{O(n+m)}$. Why? Finding the initial in-degrees sweeps $n$ vertices and $m$ edges ($O(n+m)$). Every vertex enters the zero-degree queue exactly once ($O(n)$ ops), and we exactly decrement the in-degree of its outgoing edges exactly once cumulatively spanning the graph run limits ($O(m)$ limits). Total sequence execution is linearly strict $O(n+m)$.

(Note: Running a standard DFS and pushing vertices into a stack exactly when they finish exploration naturally builds a perfectly reversed Topological Sort).

3. Strongly Connected Components (Kosaraju's Algorithm)

Problem: In an arbitrary directed graph, a Strongly Connected Component (SCC) is a maximal subgroup where every node has a directed path to every other node in the subgroup. Identify all SCCs strictly in $O(n+m)$ time.

3.1 Structural Theorems

• The SCCs coalesce identically to represent a "Meta Graph", which is rigorously proven to be a DAG.
• Constructing a reversed graph $G^R$ (flipping all edge arrows) perfectly retains all native SCC groupings.
• Critical Target: A topological Source SCC within $G^R$ inherently maps directly to a topological Sink SCC within the original graph $G$.

3.2 How to use the algorithm (Step-by-step)

1. Construct the reversed graph $G^R$ by flipping all directed edges.
2. Run DFS universally on the entire graph $G^R$, recording the exact finish[v] departure times for all vertices.
3. Order the vertices locally in descending order strictly based on their computed finish[v].
   (Crucial trick: The node with the largest finish time in $G^R$ is mathematically guaranteed to belong to a Source SCC of $G^R$, which seamlessly corresponds exactly to a Sink SCC of $G$.)
4. Run standard DFS exclusively on the original graph $G$, exploring unvisited nodes strictly following the sorted reverse sequence. Every individual DFS tree that spans successfully fully maps out an independent valid SCC cluster.

Complexity Analysis: Time is $\mathbf{O(n+m)}$. Why? The algorithm executes exactly 3 steps: 1) Reversing all edges takes $O(n+m)$. 2) The first total DFS pass takes $O(n+m)$. 3) The second total reverse DFS pass takes $O(n+m)$. Simply adding them together ($3 \times O(n+m)$) mathematically resolves to strictly linear bounds $O(n+m)$.

Lecture 5.2: Shortest Paths with Positive Weights (Dijkstra)

Problem: Find shortest paths from a single source node $s$ to all other vertices. Unlike Bellman-Ford, it does NOT handle negative edge weights.

1. Dijkstra's Algorithm

1.1 How to use the algorithm (Step-by-step)

Practical Execution:

1. Initialize: Set starting node distance $d[s] = 0$, and all others to $d[v] = \infty$. Mark all nodes as "Unvisited".
2. Pick the Closest Node: From the unvisited nodes, pick the node $u$ with the smallest distance $d[u]$. (Initially, this is $s$).
3. Lock It: Mark node $u$ as "Visited" (its shortest distance is now finalized forever).
4. Relax Neighbors: Look at all unvisited neighbors $v$ of node $u$.
   • Check: is $d[u] + \text{weight}(u, v) < d[v]$?
   • If yes, update it: $d[v] = d[u] + \text{weight}(u, v)$.
5. Repeat: Go back to Step 2 and repeat until all nodes are visited (or the remaining unvisited nodes are at $\infty$).

1.2 Correctness Proof

Goal: Prove extracting the smallest estimate $u$ optimally locks the definitive true shortest distance exactly as $d[u] = SD(u)$.
Proof via Induction on Set $|A|$:

• Base Case: $|A|=1$. The set purely contains $s$. The bound is strictly true since $d[s] = 0 = SD(s)$.
• Inductive Hypothesis: Assume for any $|A| = i$, every vertex $x \in A$ inherently holds the true $d[x] = SD(x)$.
• Inductive Step: When the algorithm extracts the smallest queue target $u$, assume contrarily that a shorter logical physical path $P$ routes to $u$.
  • Since $P$ targets $u$ escaping $A$'s border, let $x$ be the last node inside $A$, pointing to $y$ purely outside $A$.
  • By hypothesis, $d[x] = SD(x)$. The relaxing step ensured $d[y] = SD(y)$.
  • Because all graph weights are strictly $\ge 0$, extending the path from $y$ to $u$ guarantees $SD(y) \le SD(u)$.
  • Thus, $d[y] = SD(y) \le SD(u)$.
  • However, the algorithm extracted $u$ before $y$, meaning $d[u] \le d[y]$.
  • These inequalities collide: $d[u] \le d[y] \le SD(u) \le d[u]$. This bounds strictly forces $d[u] = SD(u)$. $\blacksquare$

1.3 Complexity Analysis

Why is it $O((n+m) \log n)$? We push exactly $n$ vertices into the heap and pop them ($O(n \log n)$ time). We check a maximum of $m$ edges for relaxations, causing up to $m$ decrease-key reorganizations ($m \times O(\log n)$). Summing equals $O((n+m) \log n)$.
(Note: Fibonacci Heap cleanly drops decrease-key cost to $O(1)$, yielding precisely $\mathbf{O(n \log n + m)}$).

Lecture 6: Greedy Algorithms (MST, Scheduling, Huffman Codes)

1. Minimum Spanning Tree & The Cut Property

Problem: Find a spanning tree $T \subseteq E$ minimizing the sum of edge weights.
The Cut Property Theorem: For any subset $S \subset V$, if edge $e=(x,y)$ is the lightest edge strictly crossing the cut between $S$ and $V-S$, then every valid MST MUST contain $e$.
Correctness Proof (Exchange Argument):

1. Suppose an optimal MST $T^*$ does not contain $e$.
2. Adding $e$ to $T^*$ creates a cycle. This cycle must contain another edge $e'$ crossing the exact same cut.
3. Since $e$ is the absolute lightest edge crossing the cut, $w(e) \le w(e')$.
4. Swap $e'$ with $e$. The new tree $T$ has weight $W - w(e') + w(e) \le W$. Thus $T$ is an MST containing $e$. $\blacksquare$

2. Prim's Algorithm

Maintains a Min-Heap min_weight[v] of distances from cut $S$ to $V-S$. Extracts the lightest node and relaxes its neighbors into the boundary.
Complexity: $\mathbf{O((n+m) \log n)}$. Why? Finding the lightest nodes requires $n$ extractions from a Min-Heap. Updating neighborhood crossing bounds checks $m$ edges conditionally triggering $m$ decrease-key bound logarithmic boundaries. Summing equates identically exactly mathematical executing strictly mapping boundaries $O((n+m)\log n)$.

2.5 Kruskal's Algorithm & Union-Find

Problem: Find the MST of a graph by selecting edges globally from smallest to largest.

1.1 How to use the algorithm (Step-by-step)

Practical Execution:

1. Pre-sort: Sort all edges $E$ in the graph in ascending order of their weights.
2. Initialize: Create a Disjoint-Set (Union-Find) data structure where every single vertex $v \in V$ is initially in its own isolated component.
3. Iterate: Go through the sorted edges one by one (starting from the lightest). Let the current edge be $e = (u,v)$.
   • Check if $u$ and $v$ are in the same component. (Does Find(u) == Find(v)?)
   • If NO, adding this edge won't create a cycle! Take it: add $e$ to your MST, and merge the components (Union(u, v)).
   • If YES, adding this edge creates a cycle. Skip it and move to the next edge.
4. Stop when your MST has exactly $n-1$ edges.

Complexity: $\mathbf{O(m \log n)}$.
Why? Sorting all exactly $m$ edges dominates the time taking strictly $O(m \log m) = O(m \log n)$. Inside the loop, computing exactly $m$ Find operations and $n$ Union operations executes effectively instantaneously $O(1)$ per request (technically Inverse-Ackermann $\alpha(n)$, which is $\le 4$ operations limit bound map). Therefore the sorting phase precisely dictates identical constraints $O(m \log n)$.

3. Hard Deadline Scheduling (Earliest Deadline First - EDF)

Algorithm (EDF): Pre-emptively schedule the available task with the earliest deadline.
Correctness Proof (Exchange Argument):

1. Let $OPT$ be an optimal schedule meeting all deadlines but occasionally disagreeing with EDF at time $t$.
2. At time $t$, $OPT$ schedules job $J_1$ despite job $J_2$ being available with an earlier deadline ($d_2 < d_1$).
3. $OPT$ eventually processes $J_2$ at some later time $t'$.
4. Swap the execution lengths of $J_1$ and $J_2$ at time $t$ and $t'$.
5. Since $d_2 < d_1$, pushing $J_2$ earlier perfectly guarantees it meets its deadline. Pushing $J_1$ later to the slot previously held by $J_2$ is perfectly safe, because that slot is strictly $\le d_2 < d_1$. Thus the deadline bounds hold safely. $\blacksquare$

4. Huffman Codes (Optimal Prefix Compression)

Algorithm: Iteratively merge the two characters with the lowest frequencies $f(x), f(y)$ into a single subtree node with frequency $x+y$. Result is an optimal prefix-free binary tree mapping.

Lecture 7: Max Flow & Min Cut

Problem: Push max flow from $s$ to $t$ strictly subject to edge capacities $c(u,v) > 0$.

1. Residual Networks & Ford-Fulkerson

Residual Network $G_f$:

1. Forward Edges: Capacity $= c(u,v) - f(u,v)$.
2. Backward Edges: Capacity $= f(u,v)$ (allows "undoing" flow).
   Algorithm: Repeatedly find any path from $s$ to $t$ in $G_f$, then bottleneck augment $rc_P$ flow, until no $s-t$ path exists.
   Complexity: $\mathbf{O(m \cdot C_{max})}$, pseudo-polynomial. Why? The max possible flow is $C_{max}$. Because Ford-Fulkerson works universally with whole integers, each augmented path guarantees the total flow strictly increases by at least 1. Running a basic path search (DFS/BFS) costs exactly $O(m)$ time. At maximum $C_{max}$ loops checking $O(m)$ edges, it yields limits explicitly $O(m \cdot C_{max})$.

2. Edmonds-Karp & Scaling Algorithms

• Scaling FF: Sets threshold $\Delta$, routes bounds $\ge \Delta$, and halves $\Delta$. Limit bounds strictly yield $\mathbf{O(m^2 \log C)}$.
• Edmonds-Karp: Use strictly BFS on $G_f$ (fewest edges). Guarantees $\mathbf{O(m^2 n)}$. Why? Using shortest-path bounds mathematically limits the absolute number of total augmenting paths the algorithm can take to exactly $O(n \cdot m)$. A pure BFS step requires $O(m)$. Thus mapping mathematical execution boundary bounds exactly yields precisely $\mathbf{O(n m^2)}$.

3. Max-Flow Min-Cut Theorem

Theorem: The value of the maximum flow mathematically identically equals the capacity of the Minimum Cut (a partition separating $s$ and $t$ with minimum crossing capacity).

Lecture 8: NP-Completeness & Reductions

4. Maximum Bipartite Matching (Max Flow Application)

Problem: Given a bipartite graph $G=(L \cup R, E)$, find the maximum number of edge pairings such that no vertex shares more than one edge (e.g., assigning applicants $L$ to distinct jobs $R$).

4.1 How to use the algorithm (Step-by-step)

Practical Execution:

1. Create Super-Nodes: Add a dummy Source node $s$ and a dummy Sink node $t$.
2. Build the Flow Network:
   • Connect $s$ to every single node in the left set $L$ with a strictly directed edge of capacity $= 1$.
   • Connect every node symmetrically in the right set $R$ to the Sink $t$ with a directed edge of capacity $= 1$.
   • Direct all original bipartite edges from $L \to R$. Set their capacities strictly to $1$ (or $\infty$, it computationally doesn't matter because the bottleneck is at the endpoints).
3. Run Max Flow: Run Ford-Fulkerson on this directed network.
4. Extract Answer: The Max Flow directly maps identical to the Max Bipartite Match limit. Any intermediate edge $L \to R$ actively carrying flow $f=1$ represents a definitively matched pair.

Complexity: $\mathbf{O(n \cdot m)}$.
Why? Every augmenting path pushes an exact integer limit $+1$ flow. The absolute maximum flow physically cannot exceed the number of vertices $|L|$ (so $C_{max} \le n$). By the scaling rule mapping Ford-Fulkerson identically $O(m \cdot C_{max})$, plugging exactly strictly into tracking limit limits maps bounds exactly bounding $\mathbf{O(n \cdot m)}$.

1. P vs NP Classifications

• P: Problems solvable strictly in polynomial time ($O(n^c)$).
• NP: Decision problems whose candidate solutions can be checked/verified strictly in polynomial time. (Subset-sum, Path lengths, SAT).
• NP-Complete (NPC): The mathematically hardest problems in NP. If ANY NPC problem is solved in $P$, then mathematically $P=NP$.

2. Polynomial-Time Reduction ($B \le_p A$)

Definition: Problem $B$ is polynomially reducible to problem $A$ if an input to $B$ can be transformed in polynomial time into an input to $A$ yielding identically matching Yes/No results.
Core Lemma: If $B \le_p A$ and $B$ is NP-complete, then $A$ MUST be NP-Complete (assuming $A \in NP$).

3. Key Reduction Chains (Exam Tracing)

A massive chain of reductions mathematically maps to specific classic problems:

Formal Proof Structure ($B \le_p A$):
To prove $A$ is NP-Complete, you must:

1. Prove $A \in \text{NP}$ (Given a certificate/solution, verify it in polynomial time).
2. Choose a known NP-Complete problem $B$.
3. Show how to transform any instance of $B$ into an instance of $A$ in polynomial time.
4. Prove that $B$ is a YES-instance $\iff A$ is a YES-instance.

Key Reduction Templates (Exam Tracing):

1. 3SAT $\le_p$ Clique

• Construction: For every single literal in every clause, drop a vertex. If there are $k$ clauses, you'll demand finding a Clique of size exactly $k$.
• Edges (The Rule): Connect every vertex to every other vertex EXCEPT:
  1. Do not connect nodes within the same clause (forces picking exactly 1 literal per clause).
  2. Do not connect direct contradictory opposite variables (e.g., $x_1$ and $\bar{x_1}$).
• Why it works: A $k$-clique physically demands picking $k$ valid unconflicting nodes. Since no edges exist inside clauses, it forcefully spreads the choices across all clauses identically satisfying the 3SAT boolean logic.

2. Clique $\le_p$ Vertex Cover

• Construction: Given graph $G$ and target clique size $k$, generate the Complement Graph $\bar{G}$ (where edges exist only where edges were MISSING in $G$).
• The Rule: Graph $G$ has a Clique of size $k$ $\iff$ Graph $\bar{G}$ has a Vertex Cover of size $n - k$.
• Why it works: A Clique means all chosen nodes securely touch everything internally. The exact remaining external nodes identically form a shield guarding every non-clique edge bounding precisely the Vertex Cover in the complement layout.

3. 3SAT $\le_p$ Directed Hamiltonian Path

• Construction: Build a massive ladder system. Each boolean variable $x_i$ maps to a "diamond-chain" pathway that can be traversed "Left-to-Right" (True) or "Right-to-Left" (False).
• The Rule: Clauses form external jump nodes. If $x_i$ appears in $C_j$, provide an access ramp off the variable chain mapping down to touch the clause node uniquely from the correct boolean traversing direction.
• Why it works: The single pathway physically forces you to commit to exclusively either True or False for each variable chain sequentially to reach the end sink. Touching all extra clause nodes guarantees every clause was satisfied by at least one valid literal ramp.

4. 3SAT $\le_p$ Subset Sum

• Construction: Build a table of huge decimal numbers. Digits map column boundaries: 1 column per variable, 1 column per clause.
• The Rule: Create two numbers per variable (representing mapping True or False). Both hold a '$1$' in that variable's column matrix. If they satisfy a specific target clause, they also put a mapped '$1$' in that specific clause column. Target sum matrix limits variables exactly to '$1$' and clause bounds identically exactly to '$3$'.
• Why it works: Selecting integer sum subsets forces cleanly picking exclusively either the True or False number directly to satisfy the variable column boundary limits '$1$'. The final sum clauses mathematically resolving $1+1+1 = 3$ ensures physical constraint satisfaction.

(End of Cheat Sheet)