Advanced Algorithms and Complexity
CS G526 | Aug-Dec 2026
This course explores advanced paradigms in algorithm design and analysis beyond the core curriculum, coupled with a serious study of complexity theory. It covers randomized algorithms, approximation algorithms, online algorithms, and a focused introduction to two-player matrix games (von Neumann’s minimax theorem and the multiplicative weights update), alongside parallel & distributed algorithms. Complexity theory is treated in depth — NP-completeness and reductions, the polynomial hierarchy, counting (#P), and interactive & zero-knowledge proofs — showing both what is computationally hard and what can still be achieved for hard problems.
Design and Analysis of Algorithms (CS F364) or equivalent.
Instructor: Tulasimohan Molli (TA: Hans Krupakar) Venue: I114 (lectures), I015 (lab) Venue: I114 (lectures), I015 (lab) Lectures: Monday 2:00–3:00 PM (I114) · Tuesday 12:00–1:00 PM (I114) · Thursday 12:00–1:00 PM (I114) Lab: Thursday 9:00–11:00 AM (I015) Lab: Thursday 9:00–11:00 AM (I015) Midsem: 06/10 Endsem: 04/12
Chamber Consultation: Monday 3:00–4:00 PM @ H-134
| Component | Weight |
|---|---|
| Midterm | 25% |
| Comprehensive Exam | 35% |
| Term Project (10-min Video + Report/Code + 3-min In-Class Q&A) | 20% |
| Lab Interaction | 10% |
| Class Interaction | 10% |
| # | Date | Topic | Slides |
|---|---|---|---|
| Lecture 1 | 2026-08-03 | Course Overview |  |
| Lecture 2 | 2026-08-04 | Probability Review I: Foundations & Expectation | |
| Lecture 3 | 2026-08-06 | Probability Review II: Tail Bounds | |
| Lecture 4 | 2026-08-10 | Applications of Tail Bounds | |
| Lecture 5 | 2026-08-11 | Applications of Tail Bounds II | |
| Lecture 6 | 2026-08-13 | Randomized Algorithms: Foundations | |
| Lecture 7 | 2026-08-18 | Las Vegas to Monte Carlo and Back | |
| Lecture 8 | 2026-08-20 | Randomized Complexity Classes | |
| Lecture 9 | 2026-08-24 | Graphs and Algebraic Matchings | |
| Lecture 10 | 2026-08-27 | Randomized Global Min-Cut (Karger’s Algorithm) | |
| Lecture 11 | 2026-08-31 | Randomized Data Structures: Skip Lists | |
| Lecture 12 & 13 | 2026-09-01 | Hash Tables, Universal Hashing & Perfect Hashing (FKS) | |
| Lecture 14 | 2026-09-07 | Shortest Paths & Matrix Powers | |
| Lecture 15 | 2026-09-17 | Seidel’s APSP Algorithm & The Isolation Lemma | |
| Lectures 16–18 | 2026-09-21 | Game Theory: Strategic Foundations, Minimax Duality & Yao’s Principle | |
| Lectures 19–20 | 2026-09-24 | Number Theory & Randomized Primality Testing | |
| Lecture 21 | 2026-09-28 | Online Algorithms I: Competitive Analysis & Ski Rental | |
| Lecture 22 | 2026-09-29 | Online Algorithms II: Paging & Caching | |
| Lectures 23–24 | 2026-10-12 | Complexity: Introduction to Turing Machines & Diagonalisation | |
| Lecture 25 | 2026-10-15 | Complexity: P, NP & Reductions | |
| Lecture 26 | 2026-10-19 | Complexity: NP-Hardness Reductions I — Graph Problems | |
| # | Topic | Materials |
|---|---|---|
| Practice Sheet 1 | Basics, Arrays & Linked Lists | HTML · PDF |
| Practice Sheet 2 | Linked Lists, Searching & Sequences | HTML · PDF |
| Practice Sheet 3 | Stacks | HTML · PDF |
| Practice Sheet 4 | Queues & Deques | HTML · PDF |
| Practice Sheet 5 | BFS & DFS Graph Algorithms | HTML · PDF |
Curated practice questions simulating exam-level expectations with rigorous, complete mathematical proofs. Click any row to expand the statement and view the model solution.
| Topic & Question Title | Module | Tags |
|---|---|---|
Las Vegas to Monte Carlo Conversion via Execution Timeout
|
Probability & Tail Bounds | Las VegasMonte CarloMarkov InequalityRuntime |
Las Vegas to Monte Carlo Conversion via Execution Timeout
Module: Probability & Tail Bounds
Problem Statement
Let $\mathcal{A}_{LV}$ be a **Las Vegas algorithm** that always computes the correct answer for a computational problem $\Pi$. The execution time of $\mathcal{A}_{LV}$ on an input $x$ of size $n$ is given by a non-negative random variable $X \ge 0$ with expected running time $\mathbb{E}[X] = T(n)$.
Subparts
Part (A): Describe a concrete construction of a Monte Carlo algorithm $\mathcal{A}_{MC}$ for $\Pi$ using $\mathcal{A}_{LV}$ as a subroutine such that: (1) $\mathcal{A}_{MC}$ has a strictly deterministic worst-case running time $O(T(n))$; (2) $\mathcal{A}_{MC}$ errs (or outputs a failure token) with probability at most $\frac{1}{3}$.
Part (B): Prove that the error probability of your constructed algorithm $\mathcal{A}_{MC}$ is at most $\frac{1}{3}$. Explicitly state any probabilistic inequality used and formally verify that all required hypotheses are satisfied.
Part (C): Formally show that the worst-case running time of $\mathcal{A}_{MC}$ is $O(T(n))$. Explain why this bound holds deterministically across all random choices.
Model Solution (Examination Reference)
Part (a) Algorithm Construction:
• Run algorithm $\mathcal{A}_{LV}$ for at most $3 T(n)$ execution steps.
• If $\mathcal{A}_{LV}$ terminates within $3 T(n)$ steps, return its computed output.
• If $\mathcal{A}_{LV}$ has not finished after $3 T(n)$ steps, abort the execution immediately and output $\text{"FAIL"}$ (or an arbitrary default answer).
Part (b) Error Probability Analysis:
• The constructed algorithm $\mathcal{A}_{MC}$ outputs an incorrect answer or failure token if and only if $\mathcal{A}_{LV}$ does not finish within $3 T(n)$ steps.
• Thus, the error event is equivalent to $\{X \ge 3 T(n)\}$.
• Since the running time $X$ is a non-negative random variable ($X \ge 0$) and the threshold $3 T(n) > 0$ is strictly positive, Markov's Inequality directly applies:
$$\Pr(\text{Error}) = \Pr(X \ge 3 T(n)) \le \frac{\mathbb{E}[X]}{3 T(n)} = \frac{T(n)}{3 T(n)} = \frac{1}{3}$$
• Verification of hypotheses: $X \ge 0$ holds because execution time is non-negative, and $3 T(n) > 0$ holds since the expected running time is strictly positive.
Part (c) Worst-Case Deterministic Running Time:
• The algorithm runs for at most $3 T(n)$ steps before terminating or being aborted.
• Checking the step budget adds at most $O(1)$ overhead per operation.
• Therefore, the worst-case running time is strictly bounded by $O(T(n))$ deterministically across all possible sequences of random coin flips.
|
||
Markov's Inequality Tightness and Non-Negativity Failure
|
Probability & Tail Bounds | Markov InequalityTightnessCounterexampleExpectation |
Markov's Inequality Tightness and Non-Negativity Failure
Module: Probability & Tail Bounds
Problem Statement
Recall Markov's Inequality: For any non-negative random variable $X \ge 0$ and any constant $a > 0$, $\Pr(X \ge a) \le \frac{\mathbb{E}[X]}{a}$.
Subparts
Part (A): Construct a discrete random variable $X$ taking values in $\{0, a\}$ such that Markov's Inequality holds with exact equality for a given $a > 0$. Specify its PMF and verify that $\Pr(X \ge a) = \frac{\mathbb{E}[X]}{a}$.
Part (B): Provide a concrete counterexample demonstrating that Markov's Inequality can fail if the non-negativity condition ($X \ge 0$) is omitted. Explicitly state the distribution of $X$, choose a threshold $a > 0$, and show that $\Pr(X \ge a) > \frac{\mathbb{E}[X]}{a}$.
Model Solution (Examination Reference)
Part (a) Tightness Construction:
• Let $X$ take values in $\{0, a\}$ with probability distribution:
$$\Pr(X = a) = p, \quad \Pr(X = 0) = 1 - p \quad (0 < p \le 1)$$
• Compute the expectation:
$$\mathbb{E}[X] = a \cdot p + 0 \cdot (1 - p) = a p$$
• Evaluate Markov's ratio:
$$\frac{\mathbb{E}[X]}{a} = \frac{a p}{a} = p = \Pr(X \ge a)$$ Hence, $\Pr(X \ge a) = \frac{\mathbb{E}[X]}{a}$ holds with exact equality.
Part (b) Negative Counterexample:
• Define a discrete variable $X$ taking negative values:
$$\Pr(X = -100) = 0.5, \quad \Pr(X = 10) = 0.5$$
• Compute expectation:
$$\mathbb{E}[X] = 0.5(-100) + 0.5(10) = -50 + 5 = -45$$
• Choose threshold $a = 10 > 0$. Then:
$$\Pr(X \ge 10) = \Pr(X = 10) = 0.5$$
• However, the Markov bound formula yields:
$$\frac{\mathbb{E}[X]}{a} = \frac{-45}{10} = -4.5$$
• Since $0.5 > -4.5$, we have $\Pr(X \ge a) > \frac{\mathbb{E}[X]}{a}$, completely violating the bound.
|
||
State and Prove Markov's Inequality (Discrete Setting)
|
Probability & Tail Bounds | Markov InequalityDiscrete ProbabilityExpectationProof |
State and Prove Markov's Inequality (Discrete Setting)
Module: Probability & Tail Bounds
Problem Statement
Markov's inequality is the fundamental first-moment tail bound upon which many advanced concentration inequalities are built.
Subparts
Part (A): State Markov's Inequality formally for a non-negative random variable $X \ge 0$ and a strictly positive threshold $a > 0$.
Part (B): Prove Markov's Inequality in the discrete setting: Let $X$ take values in a countable set $\mathcal{S} \subset [0, \infty)$ with probability mass function $p(x) = \Pr(X = x)$. Prove that $\Pr(X \ge a) \le \frac{\mathbb{E}[X]}{a}$ using discrete summations by partitioning the expectation sum into values strictly less than $a$ and values at least $a$.
Part (C): Identify precisely where the non-negativity hypothesis ($X \ge 0$) is used in your summation proof. Explain why the proof breaks down if $X$ can take negative values.
Model Solution (Examination Reference)
Part (a) Formal Statement of Markov's Inequality:
• For any non-negative random variable $X \ge 0$ and any constant threshold $a > 0$:
$$\Pr(X \ge a) \le \frac{\mathbb{E}[X]}{a}$$
Part (b) Proof in Discrete Setting (using Summations):
• By the definition of expectation for a discrete random variable taking values in $\mathcal{S}$:
$$\mathbb{E}[X] = \sum_{x \in \mathcal{S}} x \cdot p(x)$$
• Partition this summation into two disjoint subsets of values:
$$\mathbb{E}[X] = \sum_{x \in \mathcal{S}, x < a} x \cdot p(x) + \sum_{x \in \mathcal{S}, x \ge a} x \cdot p(x)$$
• Since $X \ge 0$, every value $x \ge 0$, and every probability $p(x) \ge 0$. Therefore, every term in the first sum is non-negative ($x \cdot p(x) \ge 0$). Dropping this non-negative sum yields the inequality:
$$\mathbb{E}[X] \ge \sum_{x \in \mathcal{S}, x \ge a} x \cdot p(x)$$
• For all terms in the remaining sum, $x \ge a$. Replacing $x$ with the constant lower bound $a$:
$$\mathbb{E}[X] \ge \sum_{x \in \mathcal{S}, x \ge a} a \cdot p(x) = a \sum_{x \in \mathcal{S}, x \ge a} p(x) = a \cdot \Pr(X \ge a)$$
• Dividing both sides by $a > 0$ yields:
$$\Pr(X \ge a) \le \frac{\mathbb{E}[X]}{a}$$
Part (c) Critical Role of Non-Negativity:
• The non-negativity hypothesis ($X \ge 0$) is strictly required when dropping the lower summation $\sum_{x < a} x \cdot p(x) \ge 0$.
• If $X$ can take negative values, this lower sum can be negative. Dropping a negative quantity would reverse or invalidate the inequality $\mathbb{E}[X] \ge \sum_{x \ge a} x \cdot p(x)$.
|
||
State and Prove Chebyshev's Inequality using Markov's Inequality
|
Probability & Tail Bounds | Chebyshev InequalityMarkov InequalityVarianceStandard Deviation |
State and Prove Chebyshev's Inequality using Markov's Inequality
Module: Probability & Tail Bounds
Problem Statement
Chebyshev's inequality provides a two-sided tail bound on the probability that a random variable deviates from its mean, parameterized by its variance.
Subparts
Part (A): State Chebyshev's Inequality formally for an arbitrary random variable $Y$ with mean $\mu = \mathbb{E}[Y]$ and finite variance $\sigma^2 = \mathrm{Var}(Y) < \infty$.
Part (B): Prove Chebyshev's Inequality using Markov's Inequality: Consider the event $|Y - \mu| \ge k$ for $k > 0$. By squaring both sides, express this in terms of the non-negative random variable $Z = (Y - \mu)^2$ and apply Markov's Inequality to prove $\Pr(|Y - \mu| \ge k) \le \frac{\sigma^2}{k^2}$.
Part (C): Using Chebyshev's Inequality, what is the probability of a random variable being at least $t$ standard deviations away from the mean, i.e., find an upper bound for $\Pr(|Y - \mu| \ge t\sigma)$ for $t > 0$?
Model Solution (Examination Reference)
Part (a) Formal Statement of Chebyshev's Inequality:
• Let $Y$ be any random variable with expected value $\mu = \mathbb{E}[Y]$ and finite variance $\sigma^2 = \mathrm{Var}(Y) < \infty$. For any threshold $k > 0$:
$$\Pr(|Y - \mu| \ge k) \le \frac{\sigma^2}{k^2}$$
Part (b) Proof of Chebyshev's Inequality from Markov:
• Consider the event $|Y - \mu| \ge k$. Since both sides are non-negative, squaring both sides yields an equivalent event:
$$|Y - \mu| \ge k \iff (Y - \mu)^2 \ge k^2$$
• Define the random variable $Z = (Y - \mu)^2$.
• $Z \ge 0$ is strictly non-negative because it is a square.
• The expected value of $Z$ is the variance of $Y$:
$$\mathbb{E}[Z] = \mathbb{E}[(Y - \mu)^2] = \mathrm{Var}(Y) = \sigma^2$$
• Applying Markov's Inequality to $Z$ with threshold $a = k^2 > 0$:
$$\Pr(|Y - \mu| \ge k) = \Pr(Z \ge k^2) \le \frac{\mathbb{E}[Z]}{k^2} = \frac{\sigma^2}{k^2}$$
Part (c) Deviation of $t$ Standard Deviations:
• Substituting $k = t\sigma$ into Chebyshev's Inequality:
$$\Pr(|Y - \mu| \ge t\sigma) \le \frac{\sigma^2}{(t\sigma)^2} = \frac{\sigma^2}{t^2 \sigma^2} = \frac{1}{t^2}$$
• Thus, the probability of any random variable deviating from its mean by at least $t$ standard deviations is bounded above by $\frac{1}{t^2}$.
|
||
Step-by-Step Derivation of the Chernoff Bound (MGF Method)
|
Probability & Tail Bounds | Chernoff BoundMoment Generating FunctionMarkov InequalityIndependence |
Step-by-Step Derivation of the Chernoff Bound (MGF Method)
Module: Probability & Tail Bounds
Problem Statement
Let $X = X_1 + \dots + X_n$ be a sum of i.i.d. random variables.
Subparts
Part (A): Explain why the event $X \ge t$ is identical to the event $e^X \ge e^t$. Apply Markov\'s inequality to the non-negative random variable $e^X$ to prove that $\Pr(X \ge t) \le e^{-t} \mathbb{E}[e^X]$.
Part (B): Since $X = \sum_{i=1}^n X_i$ is the sum of mutually independent random variables $X_1, \dots, X_n$, prove that $\mathbb{E}[e^X] = \prod_{i=1}^n \mathbb{E}[e^{X_i}]$. Using Part (a), deduce that $\Pr(X \ge t) \le e^{-t} \prod_{i=1}^n \mathbb{E}[e^{X_i}]$.
Part (C): Assuming $X_1, \dots, X_n$ are i.i.d. $\mathrm{Bernoulli}(1/2)$ random variables (taking values $0$ and $1$ with probability $1/2$ each), compute $\mathbb{E}[e^{X_i}]$ in closed form, and write out the explicit upper bound for $\Pr(X \ge t)$ as a function of $n$ and $t$.
Model Solution (Examination Reference)
Part (a) Exponential Transformation and Markov's Inequality:
• The exponential function $g(u) = e^u$ is strictly monotonically increasing on $\mathbb{R}$.
• Therefore, the event $X \ge t$ occurs if and only if $e^X \ge e^t$.
• The transformed random variable $Y = e^X$ is strictly positive ($Y > 0$), and $e^t > 0$.
• Applying Markov's Inequality to $Y$ with threshold $a = e^t$:
$$\Pr(X \ge t) = \Pr(e^X \ge e^t) \le \frac{\mathbb{E}[e^X]}{e^t} = e^{-t} \mathbb{E}[e^X]$$
Part (b) Independence and Product of Exponentials:
• Substitute $X = \sum_{i=1}^n X_i$ into the expectation:
$$\mathbb{E}[e^X] = \mathbb{E}\left[\exp\left(\sum_{i=1}^n X_i\right)\right] = \mathbb{E}\left[\prod_{i=1}^n e^{X_i}\right]$$
• Since $X_1, \dots, X_n$ are mutually independent, the transformed random variables $e^{X_1}, \dots, e^{X_n}$ are also mutually independent.
• For independent random variables, the expectation of a product equals the product of their expectations:
$$\mathbb{E}\left[\prod_{i=1}^n e^{X_i}\right] = \prod_{i=1}^n \mathbb{E}[e^{X_i}]$$
• Substituting this into Part (a) yields:
$$\Pr(X \ge t) \le e^{-t} \prod_{i=1}^n \mathbb{E}[e^{X_i}]$$
Part (c) Explicit Upper Bound for i.i.d. $\mathrm{Bernoulli}(1/2)$:
• For each $\mathrm{Bernoulli}(1/2)$ random variable $X_i \in \{0, 1\}$:
$$\mathbb{E}[e^{X_i}] = e^0 \cdot \Pr(X_i = 0) + e^1 \cdot \Pr(X_i = 1) = 1 \cdot \frac{1}{2} + e \cdot \frac{1}{2} = \frac{1 + e}{2}$$
• Since $X_1, \dots, X_n$ are i.i.d.:
$$\prod_{i=1}^n \mathbb{E}[e^{X_i}] = \left( \frac{1 + e}{2} \right)^n$$
• Substituting this back into the bound from Part (b), the explicit upper bound is:
$$\Pr(X \ge t) \le e^{-t} \left( \frac{1 + e}{2} \right)^n$$ |
||
RP One-Sided Error Probability Amplification
|
Complexity & Derandomization | RPError AmplificationOne-Sided ErrorComplexity |
RP One-Sided Error Probability Amplification
Module: Complexity & Derandomization
Problem Statement
The randomized complexity class $\text{RP}$ (Randomized Polynomial Time) features one-sided error: if $x \notin L$, the decider never accepts; if $x \in L$, it accepts with non-trivial probability.
Subparts
Part (A): Let $L \in \text{RP}$ be decided by a randomized algorithm $\mathcal{A}$ running in polynomial time with one-sided error: $\Pr[\mathcal{A}(x) = 1 \mid x \notin L] = 0$ and $\Pr[\mathcal{A}(x) = 1 \mid x \in L] \ge \epsilon$ for some constant $0 < \epsilon < 1$. Describe an amplified algorithm $\mathcal{A}_k$ running $\mathcal{A}(x)$ independently $k$ times. Specify its decision rule.
Part (B): Prove that if $x \notin L$, $\Pr[\mathcal{A}_k(x) = 1] = 0$, and if $x \in L$, the false negative probability satisfies $\Pr[\mathcal{A}_k(x) = 0] \le (1 - \epsilon)^k \le e^{-\epsilon k}$.
Part (C): For an arbitrary target error bound $\delta > 0$, determine the minimum number of repetitions $k$ required in terms of $\epsilon$ and $\delta$ to guarantee $\Pr[\text{Error}] \le \delta$.
Model Solution (Examination Reference)
Part (a) Decision Rule:
• Run $\mathcal{A}(x)$ independently $k$ times using fresh, independent random bits in each trial.
• Decision Rule: Output $1$ (Accept) if at least one trial outputs $1$; otherwise output $0$ (Reject).
Part (b) Error Probability Analysis:
• Case 1 ($x \notin L$): Every trial outputs $0$ with probability $1$. Hence no trial can ever output $1$:
$$\Pr[\mathcal{A}_k(x) = 1 \mid x \notin L] = 0$$ The false positive error remains strictly zero.
• Case 2 ($x \in L$): In each independent trial $i$, $\Pr[\mathcal{A}(x) = 0 \mid x \in L] \le 1 - \epsilon$.
• The amplified algorithm errs only if *all* $k$ independent trials simultaneously output $0$:
$$\Pr[\mathcal{A}_k(x) = 0 \mid x \in L] = \prod_{i=1}^k \Pr[\mathcal{A}(x) = 0 \mid x \in L] \le (1 - \epsilon)^k$$
• Using the fundamental inequality $1 - x \le e^{-x}$ for all $x \in \mathbb{R}$:
$$(1 - \epsilon)^k \le e^{-\epsilon k}$$
Part (c) Repetition Bound for Target Error $\delta$:
• To achieve $\Pr[\text{Error}] \le \delta$, we set:
$$e^{-\epsilon k} \le \delta \implies -\epsilon k \le \ln \delta = -\ln(1/\delta) \implies k \ge \frac{1}{\epsilon} \ln(1/\delta)$$
• Therefore, running $k = \left\lceil \frac{1}{\epsilon} \ln(1/\delta) \right\rceil$ independent repetitions suffices to drive the error down to at most $\delta$.
|
||
Amplifying BPP via Majority Voting and Hoeffding's Bound
|
Complexity & Derandomization | BPPMajority VotingError AmplificationHoeffding Bound |
Amplifying BPP via Majority Voting and Hoeffding's Bound
Module: Complexity & Derandomization
Problem Statement
Let $L \in \text{BPP}$. A randomized polynomial-time algorithm $\mathcal{A}$ decides $L$ with two-sided error probability at most $1/3$, meaning $\Pr[\mathcal{A}(x) = L(x)] \ge 2/3$. To reduce the error probability to an arbitrarily small target $\delta > 0$, we run $\mathcal{A}$ independently $k$ times on input $x$ and output the majority answer.
Subparts
Part (A): Define indicator random variables $Y_i \in \{0, 1\}$ for $i = 1, \dots, k$, where $Y_i = 1$ if trial $i$ outputs the correct answer $L(x)$, and $Y_i = 0$ otherwise. Let $S = \sum_{i=1}^k Y_i$ denote the total number of correct trials. State the condition on $S$ under which the majority voting procedure outputs an incorrect answer.
Part (B): Using $\mathbb{E}[Y_i] \ge 2/3$ (so $\mathbb{E}[S] \ge 2k/3$), express the error event $S \le k/2$ as a deviation from the mean, $S - \mathbb{E}[S] \le -k/6$. Apply Hoeffding's inequality, $\Pr(S - \mathbb{E}[S] \le -t) \le \exp(-2t^2/k)$, to prove that the majority voting error probability is bounded by $\exp(-k/18)$.
Part (C): For any target error probability $\delta > 0$, determine the number of repetitions $k$ sufficient to guarantee that the majority voting algorithm errs with probability at most $\delta$. Why does this show that the error can be made exponentially small while keeping the running time polynomial?
Model Solution (Examination Reference)
Part (a) Majority Decision & Error Condition:
• Let $Y_i = 1$ if trial $i$ outputs the correct answer $L(x)$, and $Y_i = 0$ if it errs.
• The majority voting algorithm outputs the correct answer whenever strictly more than half the trials are correct ($S > k/2$).
• Therefore, the majority vote errs if and only if at most half of the trials succeed:
$$S = \sum_{i=1}^k Y_i \le \frac{k}{2}$$
Part (b) Proof of Exponential Error Decay via Hoeffding's Bound:
• Expectation of $S$: Since each trial succeeds with probability $p = \Pr(Y_i = 1) \ge 2/3$, by linearity of expectation:
$$\mathbb{E}[S] = \sum_{i=1}^k \mathbb{E}[Y_i] = k p \ge \frac{2}{3}k$$
• Deviation from the mean:
$$S \le \frac{k}{2} \implies S - \mathbb{E}[S] \le \frac{k}{2} - \frac{2}{3}k = -\frac{k}{6}$$
• Applying Hoeffding's Inequality: For independent random variables $Y_i \in [0, 1]$, Hoeffding's inequality states:
$$\Pr(S - \mathbb{E}[S] \le -t) \le \exp\left(-\frac{2t^2}{k}\right)$$
• Setting $t = k/6$:
$$\Pr\left(S \le \frac{k}{2}\right) \le \Pr\left(S - \mathbb{E}[S] \le -\frac{k}{6}\right) \le \exp\left(-\frac{2(k/6)^2}{k}\right) = \exp\left(-\frac{2 \cdot k^2 / 36}{k}\right) = \exp\left(-\frac{k}{18}\right)$$
• Thus, the error probability decays exponentially: $\Pr(\text{Error}) \le e^{-k/18}$.
Part (c) Repetition Count for Target Error $\delta$:
• To achieve error at most $\delta$, set:
$$\exp\left(-\frac{k}{18}\right) \le \delta \implies -\frac{k}{18} \le \ln \delta = -\ln(1/\delta) \implies k \ge 18 \ln(1/\delta)$$
• Taking $k = \lceil 18 \ln(1/\delta) \rceil = O(\ln(1/\delta))$ independent repetitions is sufficient.
• Polynomial Complexity: If $\mathcal{A}$ runs in polynomial time $T(n) = O(n^d)$, the amplified algorithm runs $k$ trials in total time $O(k \cdot T(n)) = O(\ln(1/\delta) \cdot n^d)$. Even for exponentially small error $\delta = 2^{-n}$, $k = O(n)$ repetitions suffice, which remains strictly polynomial ($O(n^{d+1})$).
|
||
The Mod-2 Random Dot Product Lemma
|
Algebraic Algorithms | Mod-2 LemmaRandomized FingerprintingLinear AlgebraDiscrete Probability |
The Mod-2 Random Dot Product Lemma
Module: Algebraic Algorithms
Problem Statement
Let $d = (d_1, \dots, d_n) \in \{0, 1\}^n$ be a fixed non-zero boolean vector ($d \ne 0$), and let $r = (r_1, \dots, r_n) \in \{0, 1\}^n$ be a uniformly random boolean vector with each coordinate chosen independently with $\Pr(r_i = 0) = \Pr(r_i = 1) = 1/2$. State and prove the **Mod-2 Lemma**: $\Pr(d^T r \equiv 0 \pmod 2) = 1/2$.
Model Solution (Examination Reference)
Statement: For any fixed non-zero $d \in \{0, 1\}^n$, if $r \in \{0, 1\}^n$ is chosen uniformly at random, then $\Pr(d^T r \equiv 0 \pmod 2) = \frac{1}{2}$. Proof (Principle of Deferred Decisions):
• Since $d \ne 0$, there exists at least one index $k \in \{1, \dots, n\}$ with $d_k = 1$.
• Partition the inner product:
$$d^T r = d_k r_k + \sum_{i \ne k} d_i r_i = r_k + \sum_{i \ne k} d_i r_i$$
• Fix any outcome for the $n-1$ bits $\{r_i \mid i \ne k\}$, and let $S = \sum_{i \ne k} d_i r_i \bmod 2 \in \{0, 1\}$.
• The sum $d^T r \equiv 0 \pmod 2$ iff $r_k \equiv S \pmod 2$.
• Since $r_k$ is chosen uniformly from $\{0, 1\}$ independently of all other bits, $\Pr(r_k \equiv S) = 1/2$ for every fixed $S$.
• By the Law of Total Probability this holds unconditionally:
$$\Pr(d^T r \equiv 0 \pmod 2) = \frac{1}{2}$$ Corollary (over any field): Over any field $\mathbb{F}$, $d^T r = 0$ requires $r_k = -S / d_k$. Since $d_k \ne 0$, at most one value in $\{0, 1\}$ satisfies this, so $\Pr(d^T r = 0) \le 1/2$. |
||
Freivalds' $O(n^2)$ Matrix Product Verification Algorithm
|
Algebraic Algorithms | Freivalds AlgorithmMatrix MultiplicationMonte CarloRandomized Fingerprinting |
Freivalds' $O(n^2)$ Matrix Product Verification Algorithm
Module: Algebraic Algorithms
Problem Statement
Given three $n \times n$ matrices $A, B, C$ over a field $\mathbb{F}$, Freivalds' algorithm verifies whether $A B = C$ in $O(n^2)$ time by sampling a random vector $r \in \{0, 1\}^n$ and checking whether $A(B r) = C r$.
Subparts
Part (A): Prove that if $A B \ne C$, then $\Pr(A(B r) = C r) \le 1/2$. Explain how computing $A(B r)$ and $C r$ avoids explicitly calculating the matrix product $A B$, yielding an $O(n^2)$ running time.
Part (B): Describe the one-sided error nature of Freivalds' algorithm (which case is always correct, and which case has error). If the verification test is repeated independently $k$ times with fresh random vectors $r^{(1)}, \dots, r^{(k)}$, show that the probability of falsely declaring $A B = C$ when $A B \ne C$ is at most $2^{-k}$.
Model Solution (Examination Reference)
Part (a) Verification Error & $O(n^2)$ Complexity:
• Define error matrix $D = A B - C$. If $A B \ne C$, then $D$ is a non-zero matrix ($D \ne 0$).
• Therefore, there exists at least one row index $j$ such that the $j$-th row vector $d_j = (D_{j1}, D_{j2}, \dots, D_{jn})$ is non-zero ($d_j \ne 0$).
• Notice that $(A(B r) - C r)_j = ((A B - C)r)_j = (D r)_j = d_j^T r$.
• For $A(B r) = C r$ to hold, the entire vector $D r$ must be zero, which requires that every coordinate is zero, in particular $d_j^T r = 0$.
• By the Mod-2 Lemma, since $d_j \ne 0$, $\Pr(d_j^T r = 0) \le 1/2$. Consequently:
$$\Pr(A(B r) = C r) \le \Pr(d_j^T r = 0) \le \frac{1}{2}$$
• Running Time: By matrix associativity, $A(B r)$ is evaluated by first computing $v = B r$ ($n \times n$ matrix times $n \times 1$ vector in $O(n^2)$ operations), and then computing $A v$ (another matrix-vector product in $O(n^2)$ operations). Computing $C r$ also takes $O(n^2)$ time. Comparing the two $n \times 1$ vectors takes $O(n)$ time. The total running time is $O(n^2)$, completely avoiding the $O(n^3)$ or $O(n^{2.372})$ cost of matrix multiplication.
Part (b) One-Sided Error & Independent Amplification:
• One-Sided Error:
• If $A B = C$, then $D = 0$, so $(A B - C)r = 0 \cdot r = 0$ identically for every vector $r$. The algorithm accepts with probability 1 (zero false negatives).
• If $A B \ne C$, the algorithm incorrectly outputs that $A B = C$ with probability at most $1/2$ (false positive error $\le 1/2$).
• Independent Amplification:
• Run the test with $k$ independent random vectors $r^{(1)}, r^{(2)}, \dots, r^{(k)}$.
• An error occurs only if $D r^{(i)} = 0$ for *all* $i = 1, \dots, k$.
• Because random vectors are mutually independent:
$$\Pr(\text{False Positive}) = \prod_{i=1}^k \Pr(D r^{(i)} = 0) \le \left(\frac{1}{2}\right)^k = 2^{-k}$$
• Running $k$ trials takes $O(k n^2)$ time and drives the error down exponentially with $k$.
|
||
Resolvent Matrix Identity and Algebraic Graph Reachability
|
Algebraic Algorithms | Resolvent IdentityNeumann SeriesMatrix InversionGraph ReachabilityIn-Class Quiz 4 |
Resolvent Matrix Identity and Algebraic Graph Reachability
Module: Algebraic Algorithms
Problem Statement
Let $G = (V, E)$ be a directed graph on $n$ vertices with adjacency matrix $A \in \{0, 1\}^{n \times n}$. Let $\varepsilon > 0$ be a sufficiently small real scalar such that the series converges.
Subparts
Part (A): Prove the Neumann series matrix identity: $(I - \varepsilon A)^{-1} = \sum_{k=0}^{\infty} \varepsilon^k A^k = I + \varepsilon A + \varepsilon^2 A^2 + \varepsilon^3 A^3 + \cdots$.
Part (B): Using this identity: (1) Explain why the entry $\left((I - \varepsilon A)^{-1}\right)_{uv} > 0$ if and only if vertex $v$ is reachable from vertex $u$ in $G$. (2) How does this algebraic test avoid explicitly computing individual powers $A, A^2, \dots, A^{n-1}$?
Model Solution (Examination Reference)
Part (a) Proof of the Resolvent Identity:
• Let partial sum $S_N = \sum_{k=0}^N (\varepsilon A)^k = I + \varepsilon A + \varepsilon^2 A^2 + \dots + \varepsilon^N A^N$.
• Multiply $S_N$ by $(I - \varepsilon A)$:
$$(I - \varepsilon A) S_N = \sum_{k=0}^N (\varepsilon A)^k - \sum_{k=1}^{N+1} (\varepsilon A)^k = I - (\varepsilon A)^{N+1}$$
• For sufficiently small $\varepsilon > 0$, the spectral radius $\rho(\varepsilon A) < 1$, so $\lim_{N \to \infty} (\varepsilon A)^{N+1} = 0$.
• Taking limits as $N \to \infty$:
$$(I - \varepsilon A) \left(\sum_{k=0}^\infty \varepsilon^k A^k\right) = I \implies (I - \varepsilon A)^{-1} = \sum_{k=0}^\infty \varepsilon^k A^k$$
Part (b) Reachability Characterization & Complexity:
• Entry-wise expansion: $\left((I - \varepsilon A)^{-1}\right)_{uv} = \sum_{k=0}^\infty \varepsilon^k (A^k)_{uv}$.
• The matrix power entry $(A^k)_{uv}$ counts the exact number of directed walks of length $k$ from $u$ to $v$.
• Since $A$ is an adjacency matrix with non-negative entries ($A_{ij} \ge 0$) and $\varepsilon^k > 0$, every term in the sum is non-negative: $\varepsilon^k (A^k)_{uv} \ge 0$.
• Therefore, the sum is strictly positive ($> 0$) if and only if there exists at least one $k \ge 0$ such that $(A^k)_{uv} > 0$, which is the precise definition of reachability from $u$ to $v$.
• Avoiding individual powers: Rather than computing individual matrix powers $A, A^2, \dots, A^{n-1}$ (which requires repeated multiplications taking $O(n \cdot n^\omega)$ or $O(n^\omega \log n)$ time), a single matrix inversion of $(I - \varepsilon A)$ runs in $O(n^\omega)$ time, resolving all-pairs reachability simultaneously.
|
||
The Handshaking Lemma and Degrees in Multigraphs
|
Randomized Graph Algorithms | Handshaking LemmaGraph TheoryDegreesSum of DegreesAverage Degree |
The Handshaking Lemma and Degrees in Multigraphs
Module: Randomized Graph Algorithms
Problem Statement
The Handshaking Lemma (Euler, 1736) is one of the most fundamental structural identities in graph theory, frequently utilized to establish lower bounds on edge counts in min-cut and matching algorithms.
Subparts
Part (A): State the Handshaking Lemma formally for an undirected multigraph $G = (V, E)$ (possibly containing parallel edges, but no self-loops). Prove the lemma by double-counting the set of vertex-edge incidence pairs $S = \{(v, e) \in V \times E \mid v \text{ is an endpoint of } e\}$.
Part (B): Using the Handshaking Lemma, prove that in any undirected multigraph, the number of vertices with odd degree must be even.
Part (C): Let $G = (V, E)$ be a connected multigraph with $n = |V|$ vertices. If every vertex $v \in V$ has degree $\deg(v) \ge k$ for some positive integer $k$, prove that the total number of edges satisfies $|E| \ge \frac{n k}{2}$, and the average vertex degree is at least $k$. Briefly explain how this exact inequality is utilized in the analysis of Karger's min-cut contraction algorithm.
Model Solution (Examination Reference)
Part (a) Statement & Double Counting Proof:
• Statement: In any undirected multigraph $G = (V, E)$ without self-loops:
$$\sum_{v \in V} \deg(v) = 2 |E|$$
• Proof by Double Counting:
Consider the set of incidence pairs $S = \{(v, e) \in V \times E \mid v \in e\}$. We count the cardinality $|S|$ in two ways:
• Counting by vertices: For each fixed vertex $v \in V$, the number of incident edges is by definition $\deg(v)$. Summing across all vertices:
$$|S| = \sum_{v \in V} \deg(v)$$
• Counting by edges: Each undirected edge $e = \{u, v\} \in E$ has exactly 2 distinct endpoints ($u$ and $v$). Thus, each edge $e$ belongs to exactly 2 incidence pairs: $(u, e)$ and $(v, e)$. Summing across all edges:
$$|S| = \sum_{e \in E} 2 = 2 |E|$$ Equating both expressions yields $\sum_{v \in V} \deg(v) = 2 |E|$.
Part (b) Parity of Odd-Degree Vertices:
• Partition the vertex set $V$ into two disjoint subsets: vertices with even degree ($V_{\text{even}}$) and vertices with odd degree ($V_{\text{odd}}$):
$$\sum_{v \in V} \deg(v) = \sum_{v \in V_{\text{even}}} \deg(v) + \sum_{v \in V_{\text{odd}}} \deg(v) = 2 |E|$$
• The total sum $2 |E|$ is an even integer.
• For every $v \in V_{\text{even}}$, $\deg(v)$ is even, so the sum $\sum_{v \in V_{\text{even}}} \deg(v)$ is even.
• Rearranging:
$$\sum_{v \in V_{\text{odd}}} \deg(v) = 2 |E| - \sum_{v \in V_{\text{even}}} \deg(v) = \text{even} - \text{even} = \text{even}$$
• Because the sum of an odd number of odd integers is odd, a sum of odd integers can be even if and only if the number of terms is even.
• Therefore, $|V_{\text{odd}}|$, the number of vertices with odd degree, must be even.
Part (c) Minimum Degree, Edge Bound, and Karger's Application:
• Edge Bound: If $\deg(v) \ge k$ for all $v \in V$, then summing across all $n$ vertices gives:
$$2 |E| = \sum_{v \in V} \deg(v) \ge \sum_{v \in V} k = n k \implies |E| \ge \frac{n k}{2}$$
• Average Degree: The average degree is $\bar{d} = \frac{1}{n} \sum_{v \in V} \deg(v) = \frac{2 |E|}{n} \ge \frac{n k}{n} = k$.
• Application in Karger's Min-Cut: If $C$ is a global min-cut of size $k = |C|$, then the degree of every vertex must satisfy $\deg(v) \ge k$ (otherwise the trivial cut $(\{v\}, V \setminus \{v\})$ would have size $\deg(v) < k$, contradicting minimality). The Handshaking Lemma then guarantees $|E| \ge n k / 2$. Consequently, when picking an edge uniformly at random from $E$, the probability of contracting an edge belonging to $C$ is at most $\frac{|C|}{|E|} \le \frac{k}{n k / 2} = \frac{2}{n}$.
|
||
Karger's Min-Cut Edge Contraction Survival Analysis
|
Randomized Graph Algorithms | Karger Min-CutEdge ContractionGraph TheoryConditional Probability |
Karger's Min-Cut Edge Contraction Survival Analysis
Module: Randomized Graph Algorithms
Problem Statement
Let $G = (V, E)$ be a connected, undirected multigraph with $n = |V|$ vertices. In Karger's randomized algorithm, a uniformly random edge is contracted in each step until exactly 2 multi-vertices remain.
Subparts
Part (A): Let $C \subset E$ be a fixed minimum cut of size $k = |C|$. Prove that the degree of every vertex in $G$ is at least $k$, and show that the total number of edges satisfies $|E| \ge \frac{n k}{2}$. Conclude that the probability a uniformly random edge belongs to $C$ is at most $\frac{2}{n}$.
Part (B): Let $\mathcal{E}_i$ be the event that no edge of $C$ is contracted in step $i$. Prove by conditional probability that the probability $C$ survives all $n-2$ successive contractions is at least $\frac{2}{n(n-1)} = \frac{1}{\binom{n}{2}}$.
Model Solution (Examination Reference)
Part (a) Single-Step Survival:
• If any vertex $v$ had degree $< k$, the cut $(\{v\}, V \setminus \{v\})$ would have size $< k$, contradicting that $C$ is a min-cut of size $k$. Thus $\deg(v) \ge k$ for all $v$.
• By the Handshaking Lemma: $2 |E| = \sum_{v \in V} \deg(v) \ge n k \implies |E| \ge \frac{n k}{2}$.
• A uniformly random edge belongs to $C$ with probability:
$$\Pr(e \in C) = \frac{|C|}{|E|} \le \frac{k}{\frac{n k}{2}} = \frac{2}{n}$$
Part (b) Multi-Step Telescoping Product:
• At step $i$ (when $n - i + 1$ vertices remain), the probability of contracting an edge of $C$ given that no edge of $C$ was contracted previously is at most $\frac{2}{n - i + 1}$.
• The conditional survival probability is at least $1 - \frac{2}{n - i + 1} = \frac{n - i - 1}{n - i + 1}$.
• Telescoping across all $n-2$ contraction steps:
$$\Pr(C \text{ survives}) = \prod_{i=1}^{n-2} \frac{n - i - 1}{n - i + 1} = \left(\frac{n-2}{n}\right) \left(\frac{n-3}{n-1}\right) \left(\frac{n-4}{n-2}\right) \cdots \left(\frac{2}{4}\right) \left(\frac{1}{3}\right)$$
• All intermediate numerator terms cancel with the denominator two steps ahead:
$$\Pr(C \text{ survives}) = \frac{2 \times 1}{n(n-1)} = \frac{2}{n(n-1)} = \frac{1}{\binom{n}{2}}$$ |
||
Upper Bound on the Number of Distinct Minimum Cuts
|
Randomized Graph Algorithms | Min-Cut BoundKarger AlgorithmCombinatoricsDisjoint Events |
Upper Bound on the Number of Distinct Minimum Cuts
Module: Randomized Graph Algorithms
Problem Statement
A fundamental consequence of Karger's min-cut contraction analysis is a tight combinatorial upper bound on the maximum number of distinct minimum cuts that any connected, undirected multigraph can possess.
Subparts
Part (A): Recall that in a single run of Karger's contraction algorithm on an undirected multigraph with $n$ vertices, any fixed minimum cut $C$ survives all contractions with probability at least $\frac{1}{\binom{n}{2}} = \frac{2}{n(n-1)}$. When the algorithm terminates with 2 multi-vertices, explain why the events $A_j = \{C_j \text{ is output}\}$ for distinct minimum cuts $C_1, C_2, \dots, C_m$ are mutually disjoint.
Part (B): Using the mutual disjointness of the output events and the survival lower bound $\Pr(A_j) \ge \frac{1}{\binom{n}{2}}$, prove that any undirected multigraph on $n$ vertices can possess at most $\binom{n}{2} = \frac{n(n-1)}{2}$ distinct minimum cuts. Provide an example of a graph family that achieves this bound with exact equality.
Model Solution (Examination Reference)
Part (a) Mutual Disjointness of Output Events:
• When Karger's algorithm terminates, exactly 2 multi-vertices remain, which uniquely partitions the original vertex set $V$ into two non-empty subsets $(S, V \setminus S)$.
• This final 2-vertex configuration corresponds to exactly one single cut in the graph.
• Therefore, the algorithm outputs at most one specific cut in any single execution.
• If $C_1, C_2, \dots, C_m$ are distinct minimum cuts ($C_i \ne C_j$ for $i \ne j$), the algorithm cannot output both $C_i$ and $C_j$ simultaneously in the same run.
• Hence, the output events $A_j = \{C_j \text{ is output}\}$ are mutually disjoint.
Part (b) Combinatorial Min-Cut Bound & Tight Example:
• By the axiom of countable additivity for mutually disjoint events:
$$\Pr\left(\bigcup_{j=1}^m A_j\right) = \sum_{j=1}^m \Pr(A_j)$$
• Since the total probability of any union of events cannot exceed $1$:
$$1 \ge \sum_{j=1}^m \Pr(A_j)$$
• Because every fixed minimum cut $C_j$ survives all contractions and is output with probability $\Pr(A_j) \ge \frac{1}{\binom{n}{2}}$:
$$1 \ge \sum_{j=1}^m \frac{1}{\binom{n}{2}} = m \cdot \frac{1}{\binom{n}{2}} \implies m \le \binom{n}{2} = \frac{n(n-1)}{2}$$
• Thus, an undirected multigraph on $n$ vertices has at most $\binom{n}{2}$ distinct minimum cuts.
• Tight Example: The cycle graph $C_n$ on $n$ vertices. Every pair of edges in $C_n$ forms a 2-edge minimum cut, and there are exactly $\binom{n}{2}$ such pairs of edges. Thus $C_n$ achieves this bound with exact equality.
|
||
Skip Lists: Backward Search Path Analysis & Height Bounds
|
Randomized Data Structures | Skip ListsBackward AnalysisGeometric DistributionSearch Time |
Skip Lists: Backward Search Path Analysis & Height Bounds
Module: Randomized Data Structures
Problem Statement
In a Skip List with coin-flip probability $p = 1/2$, search for a key proceeds from the top-left header node moving forward (right) as far as possible, and dropping down one level whenever moving right would overshoot.
Subparts
Part (A): Explain how backward analysis is used to analyze the search path starting from the target key at level 0 back to the header node. What event determines whether the backward trajectory moves UP versus LEFT?
Part (B): Model the number of leftward steps taken at any level before climbing up as a Geometric random variable. Show that the expected number of steps per level is $\frac{1}{p} = 2$.
Part (C): Given that the maximum height of a Skip List with $n$ elements is bounded by $3 \log_2 n$ with high probability ($1 - 1/n^2$), prove that the total expected search time is $O(\log n)$.
Model Solution (Examination Reference)
Part (a) Backward Analysis Mechanism:
• Tracing forward search requires knowing future key comparisons. Tracing backward from the found key at level 0:
• At node $x$ on level $i$, if $x$ was promoted to level $i+1$, the forward search dropped from level $i+1$ to $x$; hence the backward path moves UP.
• If $x$ was not promoted to level $i+1$, the forward search moved right from node $y$ to $x$; hence the backward path moves LEFT.
• The decision depends solely on the independent coin flip used when node $x$ was inserted: it moves UP with probability $p = 1/2$, and LEFT with probability $1 - p = 1/2$.
Part (b) Steps per Level as Geometric Distribution:
• At each node, the path moves UP with probability $p$. The number of consecutive LEFT moves before encountering the first UP move follows a Geometric distribution (counting trials until first success).
• Expected number of total steps (left moves + up move) per level:
$$\mathbb{E}[\text{Steps per level}] = \frac{1}{p} = \frac{1}{1/2} = 2$$
Part (c) Total Expected Search Time:
• Let $H$ be the maximum height of the Skip List. With high probability $1 - 1/n^2$, $H \le 3 \log_2 n$.
• Conditioned on $H \le c \log n$, the total backward path length $L$ is the sum of $H$ independent Geometric variables:
$$\mathbb{E}[L \mid H \le 3 \log_2 n] \le 3 \log_2 n \cdot \mathbb{E}[\text{Steps per level}] = 3 \log_2 n \cdot 2 = 6 \log_2 n$$
• The failure branch $H > 3 \log_2 n$ occurs with probability $\le 1/n^2$, contributing at most $O(n / n^2) = O(1/n)$ to expectation. Total expected search time is $O(\log n)$.
|
||
Proof of Fermat's Little Theorem via Mathematical Induction
|
Number Theory & Primality | Fermat's Little TheoremMathematical InductionBinomial TheoremPrime Modulo |
Proof of Fermat's Little Theorem via Mathematical Induction
Module: Number Theory & Primality
Problem Statement
Fermat's Little Theorem states that if $p$ is a prime number, then for any integer $a \ge 1$, $a^p \equiv a \pmod p$. Prove this identity using the Binomial Theorem and mathematical induction.
Subparts
Part (A): Using the Binomial Theorem $(a + 1)^p = \sum_{k=0}^p \binom{p}{k} a^k$, prove that for every integer $k$ strictly between $1$ and $p - 1$ ($1 \le k \le p - 1$), the binomial coefficient $\binom{p}{k}$ is divisible by $p$. Conclude that $(a + 1)^p \equiv a^p + 1 \pmod p$.
Part (B): Using the algebraic identity from Part (a), prove by mathematical induction on $a$ that $a^p \equiv a \pmod p$ holds for all positive integers $a \ge 1$.
Model Solution (Examination Reference)
Part (a) Binomial Coefficient Lemma:
• By definition: $\binom{p}{k} = \frac{p!}{k!(p-k)!} \implies k! (p - k)! \binom{p}{k} = p \cdot (p - 1)!$.
• The prime $p$ divides the right-hand side $p \cdot (p - 1)!$.
• For $1 \le k \le p - 1$, all prime factors of $k!$ and $(p - k)!$ are strictly less than $p$. Since $p$ is prime, $\gcd(k!(p-k)!, p) = 1$. By Euclid's Lemma, $p$ must divide $\binom{p}{k}$, so $\binom{p}{k} \equiv 0 \pmod p$.
• Expanding:
$$(a + 1)^p = a^p + \sum_{k=1}^{p-1} \binom{p}{k} a^k + 1 \equiv a^p + 0 + 1 = a^p + 1 \pmod p$$
Part (b) Proof by Induction on $a$:
• Base Case ($a = 1$): $1^p = 1 \equiv 1 \pmod p$. The statement holds.
• Inductive Hypothesis: Assume the statement holds for some integer $a \ge 1$, so $a^p \equiv a \pmod p$.
• Inductive Step: Consider $(a + 1)^p$:
By Part (a): $(a + 1)^p \equiv a^p + 1 \pmod p$. By Inductive Hypothesis: $a^p \equiv a \pmod p$. Substituting gives: $$(a + 1)^p \equiv a + 1 \pmod p$$
• By the Principle of Mathematical Induction, $a^p \equiv a \pmod p$ holds for all integers $a \ge 1$.
|
||
Online Paging: Sleator–Tarjan Adversarial Lower Bound
|
Online Algorithms | Online PagingSleator-TarjanLower BoundAdversaryCompetitive Analysis |
Online Paging: Sleator–Tarjan Adversarial Lower Bound
Module: Online Algorithms
Problem Statement
Consider an online two-level memory hierarchy where a fast cache holds $k$ pages, backed by a slow memory of $N$ pages ($k < N$). The **Sleator–Tarjan Lower Bound Theorem** states that for any deterministic online paging algorithm $\mathcal{A}$ with cache capacity $k$, its competitive ratio against an offline optimal algorithm $\text{OPT}$ is at least $k$, i.e., $\frac{\text{cost}(\mathcal{A})}{\text{cost}(\text{OPT})} \ge k$. We prove this theorem below.
Subparts
Part (A): Construct an adversarial request sequence on a restricted universe of $k+1$ pages. Show that an adaptive adversary can force any deterministic online algorithm $\mathcal{A}$ to fault on every single request, while the offline optimal algorithm OPT incurs at most 1 fault every $k$ requests.
Part (B): Conclude from the adversarial construction that the competitive ratio of any deterministic online paging algorithm is at least $k$, i.e., $\frac{\text{cost}(\mathcal{A})}{\text{cost}(\text{OPT})} \ge k$.
Model Solution (Examination Reference)
Part (a) Adversarial Construction on $k+1$ Pages:
• Restrict the universe of pages to $k+1$ pages: $U = \{p_1, p_2, \dots, p_{k+1}\}$.
• At each step $t$, the adversary inspects the deterministic algorithm's cache (which contains $k$ pages) and requests the unique page $p^* \in U$ that is not in the cache.
• Because $p^*$ is not in cache, algorithm $\mathcal{A}$ incurs a page fault on every single request, totaling $m$ faults for an $m$-length sequence.
• Meanwhile, the offline optimal algorithm (Belady's MIN) knows future requests and always evicts the page that is requested furthest in the future.
• Since only $k+1$ distinct pages exist, the evicted page cannot be requested for at least $k$ steps. Hence, OPT incurs at most 1 fault every $k$ requests: $\text{cost}(\text{OPT}) \le \lceil m/k \rceil$.
Part (b) Competitive Ratio Deduction:
• Taking the ratio of costs as sequence length $m \to \infty$:
$$\frac{\text{cost}(\mathcal{A})}{\text{cost}(\text{OPT})} \ge \frac{m}{\lceil m/k \rceil} \ge \frac{m}{m/k + 1} \xrightarrow{m \to \infty} k$$
• Thus, no deterministic online paging algorithm can achieve a competitive ratio strictly less than $k$.
|
||
Online Paging: LRU Phase Partitioning and $k$-Competitiveness
|
Online Algorithms | Online PagingLRUPhase PartitioningCompetitive AnalysisRandomized Marking |
Online Paging: LRU Phase Partitioning and $k$-Competitiveness
Module: Online Algorithms
Problem Statement
The Least Recently Used (LRU) paging algorithm evicts the page whose last access was furthest in the past. We analyze its competitive ratio using the method of phase partitioning.
Subparts
Part (A): Partition an arbitrary page request sequence $\sigma$ into phases $P_1, P_2, \dots, P_m$ such that each phase contains requests to exactly $k$ distinct pages. Prove that LRU incurs at most $k$ page faults during any individual phase $P_j$.
Part (B): Prove that the offline optimal algorithm OPT must incur at least 1 page fault across any phase transition (or between consecutive phases). Conclude that LRU is strictly $k$-competitive: $\text{cost}(\text{LRU}) \le k \cdot \text{cost}(\text{OPT}) + k$.
Model Solution (Examination Reference)
Part (a) LRU Cost within a Phase:
• Partition $\sigma = P_1, P_2, \dots, P_m$ into phases where Phase 0 is initial cache loading, and each subsequent phase $P_j$ contains requests to exactly $k$ distinct pages.
• Within Phase $j$, once a page is brought into the cache on its first request in Phase $j$, it is marked as recently accessed.
• Because Phase $j$ contains at most $k$ distinct pages in total, at most $k-1$ *other* distinct pages can be requested after it in this phase.
• Since LRU only evicts a page if $k$ distinct other pages are requested after it, no page requested in Phase $j$ is ever evicted during Phase $j$.
• Thus, each distinct page can cause at most one fault for LRU in Phase $j$:
$$\text{cost}_{P_j}(\text{LRU}) \le k$$
Part (b) OPT Cost and $k$-Competitiveness:
• Consider the set of pages requested in Phase $j-1$ and Phase $j$.
• Phase $j-1$ contains $k$ distinct pages, and the first request of Phase $j$ is to a page distinct from all $k$ pages of Phase $j-1$ (by definition of phase boundary).
• Thus, across Phase $j-1$ and the start of Phase $j$, there are $k+1$ distinct page requests.
• Because OPT's cache holds only $k$ pages, OPT must incur at least 1 fault in servicing this transition.
• Summing across all $m$ phases:
$$\text{cost}(\text{LRU}) \le k \cdot m \le k \cdot \text{cost}(\text{OPT}) + O(k)$$
• This proves that LRU is strictly $k$-competitive, matching the theoretical Sleator–Tarjan lower bound.
|
||
Work in groups of 1 to 3. Choose an idea from the pool below or propose your own topic (subject to instructor approval). Deliverables include a 10-min recorded video, a comprehensive report and implementation, and a ~3-minute in-class Q&A defense per group at the end of the semester. Click any row to expand details.
| ID | Topic Title | Category | Type | Tags |
|---|---|---|---|---|
| P01 |
B-Trees & B+ Trees
|
Advanced Data Structures | Implementation + Study | Advanced Data Structures Data Structures Trees |
[P01] B-Trees & B+ Trees — Details & ScopeProject Idea: Explore why modern database storage engines and file systems rely on multi-way B/B+ trees rather than standard binary search trees.
Suggested References: CLRS Ch. 18; Ramakrishnan & Gehrke, Database Management Systems.
|
||||
| P02 |
Red–Black Trees vs. AVL Trees
|
Advanced Data Structures | Implementation + Study | Advanced Data Structures Data Structures Trees |
[P02] Red–Black Trees vs. AVL Trees — Details & ScopeProject Idea: Compare the practical engineering trade-offs between strictly balanced AVL trees and color-balanced Red-Black trees.
Suggested References: CLRS Ch. 12–13.
|
||||
| P03 |
Splay Trees & Self-Adjusting Trees
|
Advanced Data Structures | Implementation + Study | Advanced Data Structures Data Structures Trees |
[P03] Splay Trees & Self-Adjusting Trees — Details & ScopeProject Idea: Investigate self-adjusting binary search trees that maintain logarithmic amortized efficiency without storing any balance metadata.
Suggested References: Sleator & Tarjan 1985; CLRS Ch. 17.
|
||||
| P04 |
Treaps (Randomized Search Trees)
|
Advanced Data Structures | Implementation + Study | Advanced Data Structures Data Structures Trees |
[P04] Treaps (Randomized Search Trees) — Details & ScopeProject Idea: Study how assigning independent random priorities to BST keys yields expected logarithmic height without complex deterministic rotation rules.
Suggested References: Seidel & Aragon 1996; Motwani & Raghavan Ch. 8.
|
||||
| P05 |
Fibonacci Heaps vs. Binary & d-ary Heaps
|
Advanced Data Structures | Implementation + Study | Advanced Data Structures Data Structures Heaps |
[P05] Fibonacci Heaps vs. Binary & d-ary Heaps — Details & ScopeProject Idea: Evaluate whether the theoretical asymptotic superiority of Fibonacci heaps ($O(1)$ amortized decrease-key) translates to real-world performance.
Suggested References: Fredman & Tarjan 1987; CLRS Ch. 19.
|
||||
| P06 |
Pairing Heaps: Practical Self-Adjusting Heaps
|
Advanced Data Structures | Implementation + Study | Advanced Data Structures Data Structures Heaps |
[P06] Pairing Heaps: Practical Self-Adjusting Heaps — Details & ScopeProject Idea: Examine pairing heaps as a simpler, pointer-lean alternative to Fibonacci heaps designed for practical systems.
Suggested References: Fredman et al. 1986; Iacono 2000.
|
||||
| P07 |
Disjoint Set Union (Union–Find) & Offline LCA
|
Advanced Data Structures | Implementation + Study | Advanced Data Structures Data Structures |
[P07] Disjoint Set Union (Union–Find) & Offline LCA — Details & ScopeProject Idea: Explore the near-linear efficiency of union-find and its application to solving static tree queries offline.
Suggested References: Tarjan 1975; CLRS Ch. 21.
|
||||
| P08 |
Segment Trees with Lazy Propagation
|
Advanced Data Structures | Implementation + Study | Advanced Data Structures Data Structures Trees |
[P08] Segment Trees with Lazy Propagation — Details & ScopeProject Idea: Build a versatile range-query engine capable of handling dynamic interval updates in logarithmic time.
Suggested References: de Berg et al., Computational Geometry.
|
||||
| P09 |
Fenwick Trees (Binary Indexed Trees)
|
Advanced Data Structures | Implementation + Study | Advanced Data Structures Data Structures Trees |
[P09] Fenwick Trees (Binary Indexed Trees) — Details & ScopeProject Idea: Analyze bit-manipulation techniques that enable dynamic prefix sums over an array with zero pointer overhead.
Suggested References: Fenwick 1994.
|
||||
| P10 |
Persistent Search Trees
|
Advanced Data Structures | Implementation + Study | Advanced Data Structures Data Structures Trees |
[P10] Persistent Search Trees — Details & ScopeProject Idea: Study how path-copying enables functional, persistent search trees that allow querying historical versions without copying the entire structure.
Suggested References: Driscoll, Sarnak, Sleator, & Tarjan 1989.
|
||||
| P11 |
Tries & Compressed Radix Trees (Patricia Tries)
|
Advanced Data Structures | Implementation + Study | Advanced Data Structures Data Structures Trees |
[P11] Tries & Compressed Radix Trees (Patricia Tries) — Details & ScopeProject Idea: Investigate memory-compact prefix search structures for strings and network IP lookups.
Suggested References: CLRS Ch. 32; Morrison 1968.
|
||||
| P12 |
Suffix Trees & Ukkonen's Algorithm
|
Advanced Data Structures | Implementation + Study | Advanced Data Structures Data Structures Trees Strings |
[P12] Suffix Trees & Ukkonen's Algorithm — Details & ScopeProject Idea: Master the linear-time online construction of suffix trees for all-substring indexing.
Suggested References: Ukkonen 1995; Gusfield, Algorithms on Strings, Trees and Sequences.
|
||||
| P13 |
Suffix Arrays & LCP Arrays
|
Advanced Data Structures | Implementation + Study | Advanced Data Structures Data Structures Strings |
[P13] Suffix Arrays & LCP Arrays — Details & ScopeProject Idea: Explore suffix arrays as a lightweight, array-only alternative to suffix trees for text indexation.
Suggested References: Manber & Myers 1993; Kasai et al. 2001.
|
||||
| P14 |
Aho–Corasick Multi-Pattern Automaton
|
Advanced Data Structures | Implementation + Study | Advanced Data Structures Data Structures |
[P14] Aho–Corasick Multi-Pattern Automaton — Details & ScopeProject Idea: Construct an exact multi-string pattern matching automaton that searches for thousands of keywords in a single linear pass.
Suggested References: Aho & Corasick 1975.
|
||||
| P15 |
$k$-d Trees for Spatial Range & Nearest-Neighbor Search
|
Advanced Data Structures | Implementation + Study | Advanced Data Structures Data Structures Trees Spatial/Geometry |
[P15] $k$-d Trees for Spatial Range & Nearest-Neighbor Search — Details & ScopeProject Idea: Apply multidimensional space-partitioning trees to spatial search and nearest-neighbor problems.
Suggested References: Bentley 1975; de Berg et al., Computational Geometry.
|
||||
| P16 |
Interval Trees & Range Trees
|
Advanced Data Structures | Implementation + Study | Advanced Data Structures Data Structures Trees Spatial/Geometry |
[P16] Interval Trees & Range Trees — Details & ScopeProject Idea: Study geometric search trees designed for interval stabbing queries and multi-dimensional orthogonal queries.
Suggested References: CLRS Ch. 14; Edelsbrunner 1980.
|
||||
| P17 |
R-Trees for Spatial & GIS Indexing
|
Advanced Data Structures | Implementation + Study | Advanced Data Structures Data Structures Trees Spatial/Geometry |
[P17] R-Trees for Spatial & GIS Indexing — Details & ScopeProject Idea: Explore hierarchical bounding-box trees used by GIS engines and spatial databases.
Suggested References: Guttman 1984; Beckmann et al. (R-tree) 1990.
|
||||
| P18 |
Van Emde Boas Trees
|
Advanced Data Structures | Implementation + Study | Advanced Data Structures Data Structures Trees |
[P18] Van Emde Boas Trees — Details & ScopeProject Idea: Investigate double-logarithmic time integer priority queues over bounded universes.
Suggested References: van Emde Boas 1977; CLRS Ch. 20.
|
||||
| P19 |
Bloom Filters & Counting Bloom Filters
|
Probabilistic & Streaming Structures | Implementation + Study | Probabilistic & Streaming Structures Streaming |
[P19] Bloom Filters & Counting Bloom Filters — Details & ScopeProject Idea: Explore space-efficient probabilistic set-membership filters and their role in minimizing disk and network queries.
Suggested References: Bloom 1970; Broder & Mitzenmacher 2004.
|
||||
| P20 |
HyperLogLog: Cardinality Estimation at Scale
|
Probabilistic & Streaming Structures | Implementation + Study | Probabilistic & Streaming Structures Streaming |
[P20] HyperLogLog: Cardinality Estimation at Scale — Details & ScopeProject Idea: Analyze how modern analytics engines estimate distinct element counts over massive data streams using minimal memory.
Suggested References: Flajolet et al. 2007; Heule et al. 2013.
|
||||
| P21 |
Count-Min Sketch for Heavy Hitters
|
Probabilistic & Streaming Structures | Implementation + Study | Probabilistic & Streaming Structures Streaming |
[P21] Count-Min Sketch for Heavy Hitters — Details & ScopeProject Idea: Study sublinear-memory frequency estimation for tracking high-frequency items in streaming data.
Suggested References: Cormode & Muthukrishnan 2005.
|
||||
| P22 |
Locality-Sensitive Hashing (LSH) for Nearest Neighbors
|
Probabilistic & Streaming Structures | Implementation + Study | Probabilistic & Streaming Structures Streaming |
[P22] Locality-Sensitive Hashing (LSH) for Nearest Neighbors — Details & ScopeProject Idea: Investigate randomized hashing schemes that map similar high-dimensional vectors to identical buckets with high probability.
Suggested References: Indyk & Motwani 1998; Gionis et al. 1999.
|
||||
| P23 |
Dijkstra's Algorithm on Real-World Road Networks
|
Graph, Network & Practical Algorithms | Implementation + Study | Graph, Network & Practical Algorithms Graphs & Networks Graphs |
[P23] Dijkstra's Algorithm on Real-World Road Networks — Details & ScopeProject Idea: Benchmark single-source shortest path algorithms on realistic road networks and study speedup heuristics.
Suggested References: CLRS Ch. 24; Goldberg & Harrelson 2005.
|
||||
| P24 |
Maximum Flow on Complex Graphs: Edmonds–Karp & Dinic
|
Graph, Network & Practical Algorithms | Implementation + Study | Graph, Network & Practical Algorithms Graphs & Networks Graphs |
[P24] Maximum Flow on Complex Graphs: Edmonds–Karp & Dinic — Details & ScopeProject Idea: Compare augmenting-path and blocking-flow algorithms for network flow and their reductions to real-world matching problems.
Suggested References: CLRS Ch. 26; Dinic 1970.
|
||||
| P25 |
Minimum Spanning Trees on Massive Graphs: Kruskal, Prim & Borůvka
|
Graph, Network & Practical Algorithms | Implementation + Study | Graph, Network & Practical Algorithms Graphs & Networks Trees Graphs |
[P25] Minimum Spanning Trees on Massive Graphs: Kruskal, Prim & Borůvka — Details & ScopeProject Idea: Examine the algorithmic differences and performance trade-offs among the three classic MST algorithms.
Suggested References: CLRS Ch. 23.
|
||||
| P26 |
String Matching Showdown: KMP vs. Rabin–Karp
|
Graph, Network & Practical Algorithms | Implementation + Study | Graph, Network & Practical Algorithms Graphs & Networks Strings |
[P26] String Matching Showdown: KMP vs. Rabin–Karp — Details & ScopeProject Idea: Contrast deterministic finite-state string matching against randomized rolling-hash matching.
Suggested References: CLRS Ch. 32.
|
||||
| P27 |
Online Paging & Caching Algorithms on Real Memory Traces
|
Optimization, Online & System-Level Paradigms | Implementation + Study | Optimization, Online & System-Level Paradigms Optimization |
[P27] Online Paging & Caching Algorithms on Real Memory Traces — Details & ScopeProject Idea: Bridge the gap between competitive ratio analysis and real-world cache performance.
Suggested References: Sleator & Tarjan 1985; Borodin & El-Yaniv.
|
||||
| P28 |
Metric TSP: Christofides' 1.5-Approximation & Local Search
|
Optimization, Online & System-Level Paradigms | Implementation + Study | Optimization, Online & System-Level Paradigms Optimization Graphs |
[P28] Metric TSP: Christofides' 1.5-Approximation & Local Search — Details & ScopeProject Idea: Explore polynomial-time approximation algorithms for NP-hard routing problems.
Suggested References: Christofides 1976; Williamson & Shmoys Ch. 2.
|
||||
| P29 |
Modern SAT Solver Reductions for Scheduling & Puzzles
|
Optimization, Online & System-Level Paradigms | Implementation + Study | Optimization, Online & System-Level Paradigms Optimization |
[P29] Modern SAT Solver Reductions for Scheduling & Puzzles — Details & ScopeProject Idea: Formulate complex discrete scheduling or constraint satisfaction problems as Boolean CNF-SAT instances.
Suggested References: Biere et al., Handbook of Satisfiability; Arora & Barak Ch. 2.
|
||||
| P30 |
Primality Testing: Miller–Rabin vs. Deterministic AKS
|
Optimization, Online & System-Level Paradigms | Implementation + Study | Optimization, Online & System-Level Paradigms Optimization |
[P30] Primality Testing: Miller–Rabin vs. Deterministic AKS — Details & ScopeProject Idea: Investigate the practical and theoretical contrasts between randomized Monte Carlo primality testing and deterministic polynomial-time testing.
Suggested References: Rabin 1980; Agrawal, Kayal & Saxena 2004.
|
||||
| Week | Module | Learning Objectives | Topics | Reference |
|---|---|---|---|---|
| 1 | M1 | Course scope and landscape; probability & complexity refresher | Introduction — Advanced Algorithms & Complexity; Review of Probability & Complexity Classes | T1 Ch1 |
| 2 | M1 | Classify randomized algorithms; verify matrix products, identities, min-cuts | Las Vegas & Monte Carlo, Freivalds, Min-Cut; PIT, Schwartz–Zippel | T1 Ch1 |
| 3 | M2 | Bound deviations via tail inequalities | Tail Inequalities, Chebyshev, Chernoff Bounds & Applications | T1 Ch3–4 |
| 4 | M3 | Expected-time data structures | Skip Lists, Hash Tables, Cuckoo Hashing | T1 Ch8 |
| 5 | M3 | Randomize classic graph algorithms | Randomized Graph Algorithms: MST, Shortest Paths, Matching | T1 Ch10 |
| 6 | M4 | Two-player matrix games: minimax and multiplicative weights | Two-Player Matrix Games; von Neumann’s Minimax Theorem; Multiplicative Weights Update | T1 Ch4 |
| 7 | M5 | Online decision-making under uncertainty | Competitive Ratio, Ski Rental, Paging, Secretary Problem | T1 Ch13 |
| 8 | M6 | Number-theoretic algorithms | Euclid, Euler’s φ, Primality Testing | T1 Ch14 |
| 9 | M7 | Parallel and distributed algorithms | PRAM, Prefix, MIS; Byzantine Agreement, Consensus | T1 Ch12 |
| 10 | M8 | NP-completeness framework and the polynomial hierarchy | NP-Completeness & Reductions: Decision Problems, Cook–Levin, Polynomial Hierarchy | T3 Ch2–4 |
| 11 | M9 | Approximation by greedy, LP rounding, primal-dual, local search | Greedy, LP Rounding, Primal-Dual, Local Search; Set Cover, TSP | R1, R3 |
| 12 | M9/M10 | Approximation schemes and limits of approximability; interactive proofs | PTAS, APX; Inapproximability, Gap Technique; Interactive Proofs | R4, T3 Ch8, 11 |
| 13 | M10 | Advanced complexity: interactive & zero-knowledge proofs, counting, algebraic methods | Interactive & Zero-Knowledge Proofs; #P & Counting; Algebraic Counting Methods | T3 Ch8–9, T1 Ch1 |
| 14 | M11 | Student project proposal presentations | Student Project Proposal Presentations | — |