Divide & Conquer + Master Theorem
Break the problem in half, solve each half recursively, merge the results. This paradigm gives us $O(n\log n)$ sorting, $O(n\log n)$ convex hull, $O(n)$ median finding, and $O(n^{2.81})$ matrix multiplication. The Master Theorem tells us the runtime without drawing the recursion tree.
The Divide and Conquer Paradigm
Every divide-and-conquer algorithm follows the same skeleton: given a problem of size $n$, divide it into $a$ subproblems each of size $n/b$, solve each recursively, then merge the results in $f(n)$ time. The total runtime satisfies:
$$T(n) = aT\!\left(\frac{n}{b}\right) + f(n)$$
The art is in choosing the right division and designing an efficient merge. The merge step is usually what differentiates a clever algorithm from a naive one — compare $O(n^2)$ merge (naive convex hull) with $O(n)$ merge (divide-and-conquer convex hull).
Three steps, always:
Divide — split the input into subproblems. Usually in half: $n/2$ or two halves by sorted order.
Conquer — solve each subproblem recursively. The base case handles small inputs directly.
Combine — merge the subproblem solutions into the final answer. This is where the work happens.
Divide — split the input into subproblems. Usually in half: $n/2$ or two halves by sorted order.
Conquer — solve each subproblem recursively. The base case handles small inputs directly.
Combine — merge the subproblem solutions into the final answer. This is where the work happens.
Problem 1 — Interval Scheduling and Weighted Interval Scheduling
Before reaching divide and conquer, L1 grounds the course in two scheduling problems that illustrate a key theme: very similar problems can have very different complexity.
Interval Scheduling: given $n$ requests with start times $s(i)$ and finish times $f(i)$, select the maximum number of non-overlapping requests. The greedy algorithm — always pick the request with earliest finish time — solves this in $O(n\log n)$.
Greedy correctness proof (exchange argument). Let greedy produce $S = [i_1, i_2, \ldots, i_k]$ and let $S^* = [j_1, j_2, \ldots, j_{k^*}]$ be optimal. We show $k = k^*$ by induction. Key step: since greedy picks earliest finish time, $f(i_1) \leq f(j_1)$. Replace $j_1$ with $i_1$ in $S^*$ to get $S^{**}$, which is still feasible and still has $k^*$ intervals. Now $S^{**}[2\ldots k^*]$ is optimal for the sub-instance of intervals starting after $f(i_1)$. By induction, greedy picks $k^*-1$ more. Total: $k = k^*$. $\square$
Weighted Interval Scheduling: add weight $w(i)$ to each request; maximise total weight of non-overlapping subset. Greedy fails — a short, low-weight interval can block a heavy one. This requires dynamic programming:
Sort by finish time: $f(1) \leq f(2) \leq \cdots \leq f(n)$. Define $p(j)$ = largest index $i < j$ with $f(i) \leq s(j)$ (the last compatible interval before $j$). Define $M[j]$ = maximum weight using only requests $1\ldots j$.
$$M[j] = \max\bigl(w(j) + M[p(j)],\;\; M[j-1]\bigr)$$
Base case: $M[0] = 0$. Compute in order $j = 1, \ldots, n$. Time: $O(n\log n)$ (sorting + binary search for each $p(j)$).
The jump from greedy (unweighted) to DP (weighted) illustrates that small problem changes can require fundamentally different algorithmic approaches.
Problem 2 — Convex Hull
Given $n$ points in the plane, find the smallest convex polygon containing all of them. Represented as the boundary vertices in clockwise order.
Brute force: test every line segment — $O(n^2)$ segments, $O(n)$ tests each = $O(n^3)$. Can we do better?
Divide and conquer: sort points by $x$-coordinate once ($O(n\log n)$). Split into left half $A$ and right half $B$. Compute $CH(A)$ and $CH(B)$ recursively. Merge by finding the upper and lower tangent lines between the two hulls.
Finding the upper tangent in $O(n)$: start at the rightmost point of $A$ (index $i=1$) and leftmost of $B$ (index $j=1$). Define $y(i,j)$ = $y$-coordinate where the vertical separator $L$ meets segment $(a_i, b_j)$. The upper tangent maximises $y(i,j)$.
Move fingers: if $y(i, j+1) > y(i,j)$, advance $j$ clockwise; if $y(i-1, j) > y(i,j)$, advance $i$ anticlockwise; else $(a_i, b_j)$ is the upper tangent. Each step strictly increases $y$, so terminates in $O(n)$ steps.
Recurrence: $T(n) = 2T(n/2) + \Theta(n) = \Theta(n\log n)$.
Move fingers: if $y(i, j+1) > y(i,j)$, advance $j$ clockwise; if $y(i-1, j) > y(i,j)$, advance $i$ anticlockwise; else $(a_i, b_j)$ is the upper tangent. Each step strictly increases $y$, so terminates in $O(n)$ steps.
Recurrence: $T(n) = 2T(n/2) + \Theta(n) = \Theta(n\log n)$.
Problem 3 — Median Finding in Linear Time
Find the element of rank $\lfloor(n+1)/2\rfloor$ in an unsorted array. Sorting works in $\Theta(n\log n)$. Can we do it in $\Theta(n)$?
Yes — but only if we pick the pivot cleverly. The naive Select (random pivot) achieves $O(n)$ expected time. The Median of Medians algorithm achieves $O(n)$ worst-case:
Median of Medians (deterministic $O(n)$ select):
1. Arrange $S$ into groups of 5. Sort each group. ($O(n)$ total.)
2. Find the median of the $\lceil n/5 \rceil$ group medians recursively: $T(\lceil n/5 \rceil)$.
3. Use this median $x$ as pivot. Partition into $B = \{y < x\}$ and $C = \{y > x\}$.
4. Recurse on the appropriate side.
Key guarantee: at least $3(\lceil n/10 \rceil - 2)$ elements are $> x$ and $< x$, so both $|B|$ and $|C|$ are at most $\frac{7n}{10} + 6$.
Recurrence: $T(n) = T(\lceil n/5 \rceil) + T(7n/10 + 6) + \Theta(n)$
Solution: $T(n) = \Theta(n)$ (proved by substitution: assume $T(n) \leq cn$, show it holds).
1. Arrange $S$ into groups of 5. Sort each group. ($O(n)$ total.)
2. Find the median of the $\lceil n/5 \rceil$ group medians recursively: $T(\lceil n/5 \rceil)$.
3. Use this median $x$ as pivot. Partition into $B = \{y < x\}$ and $C = \{y > x\}$.
4. Recurse on the appropriate side.
Key guarantee: at least $3(\lceil n/10 \rceil - 2)$ elements are $> x$ and $< x$, so both $|B|$ and $|C|$ are at most $\frac{7n}{10} + 6$.
Recurrence: $T(n) = T(\lceil n/5 \rceil) + T(7n/10 + 6) + \Theta(n)$
Solution: $T(n) = \Theta(n)$ (proved by substitution: assume $T(n) \leq cn$, show it holds).
import bisect
# ── WEIGHTED INTERVAL SCHEDULING ── O(n log n) ──────────────────────
def weighted_interval_scheduling(intervals):
"""
intervals: list of (start, finish, weight)
Returns maximum total weight of non-overlapping intervals.
"""
intervals.sort(key=lambda x: x[1]) # sort by finish time
n = len(intervals)
finish_times = [iv[1] for iv in intervals]
def p(j):
"""Largest i < j with finish[i] <= start[j]."""
return bisect.bisect_right(finish_times, intervals[j][0], 0, j) - 1
M = [0] * (n + 1) # M[0] = 0 (base case)
for j in range(n):
pj = p(j)
M[j + 1] = max(intervals[j][2] + M[pj + 1], M[j])
return M[n]
# ── MEDIAN OF MEDIANS ── O(n) worst case ────────────────────────────
def median_of_medians(S, i):
"""
Returns the i-th smallest element (1-indexed) of S.
O(n) deterministic — no randomness needed.
"""
if len(S) <= 5:
return sorted(S)[i - 1]
# Step 1: split into groups of 5, find each group's median
chunks = [S[j:j+5] for j in range(0, len(S), 5)]
medians = [sorted(c)[len(c) // 2] for c in chunks]
# Step 2: find median of medians recursively
pivot = median_of_medians(medians, len(medians) // 2 + 1)
# Step 3: partition around pivot
low = [x for x in S if x < pivot]
high = [x for x in S if x > pivot]
k = len(low) + 1 # rank of pivot in S
# Step 4: recurse on correct side
if i == k: return pivot
elif i < k: return median_of_medians(low, i)
else: return median_of_medians(high, i - k)#include <vector>
#include <algorithm>
using namespace std;
// Weighted Interval Scheduling — O(n log n)
struct Interval { int s, f, w; };
int weighted_interval(vector<Interval>& ivs) {
sort(ivs.begin(), ivs.end(), [](auto& a, auto& b){ return a.f < b.f; });
int n = ivs.size();
vector<int> M(n + 1, 0);
for (int j = 0; j < n; ++j) {
// binary search for p(j)
int lo = 0, hi = j;
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
if (ivs[mid-1].f <= ivs[j].s) lo = mid;
else hi = mid - 1;
}
M[j+1] = max(ivs[j].w + M[lo], M[j]);
}
return M[n];
}
// Median of Medians — O(n) deterministic
int mom(vector<int> S, int i) {
if ((int)S.size() <= 5) {
sort(S.begin(), S.end());
return S[i - 1];
}
vector<int> medians;
for (int j = 0; j < (int)S.size(); j += 5) {
auto chunk = vector<int>(S.begin()+j,
S.begin()+min(j+5,(int)S.size()));
sort(chunk.begin(), chunk.end());
medians.push_back(chunk[chunk.size()/2]);
}
int pivot = mom(medians, medians.size()/2 + 1);
vector<int> lo, hi;
for (int x : S) { if (x < pivot) lo.push_back(x);
else if (x > pivot) hi.push_back(x); }
int k = lo.size() + 1;
if (i == k) return pivot;
if (i < k) return mom(lo, i);
return mom(hi, i - k);
}Problem 4 — Strassen’s Matrix Multiplication
Naive matrix multiplication of two $n \times n$ matrices costs $\Theta(n^3)$ — $n^2$ entries in $C$, each requiring $n$ multiplications. Strassen’s key insight: you can compute the four $n/2 \times n/2$ submatrix products using only 7 multiplications (not 8) at the cost of 18 additions.
Strassen’s seven products (for $2\times2$ block decomposition $A = \begin{pmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\end{pmatrix}$, same for $B$):
$$M_1 = (A_{11}+A_{22})(B_{11}+B_{22}) \quad M_2 = (A_{21}+A_{22})B_{11}$$
$$M_3 = A_{11}(B_{12}-B_{22}) \quad M_4 = A_{22}(B_{21}-B_{11})$$
$$M_5 = (A_{11}+A_{12})B_{22} \quad M_6 = (A_{21}-A_{11})(B_{11}+B_{12})$$
$$M_7 = (A_{12}-A_{22})(B_{21}+B_{22})$$
Then: $C_{11} = M_1+M_4-M_5+M_7$, $C_{12}=M_3+M_5$, $C_{21}=M_2+M_4$, $C_{22}=M_1-M_2+M_3+M_6$.
Recurrence: $T(n) = 7T(n/2) + \Theta(n^2)$. By Master Theorem: $T(n) = \Theta(n^{\log_2 7}) \approx \Theta(n^{2.807})$.
Recurrence: $T(n) = 7T(n/2) + \Theta(n^2)$. By Master Theorem: $T(n) = \Theta(n^{\log_2 7}) \approx \Theta(n^{2.807})$.
import numpy as np
def strassen(A, B):
"""
Strassen matrix multiplication. A, B must be n x n with n a power of 2.
Returns C = A @ B in O(n^2.807) recursive multiplications.
For small n, falls back to naive to avoid overhead.
"""
n = len(A)
if n <= 64: # base case: numpy is fastest here
return A @ B
half = n // 2
# Partition into 2x2 blocks of submatrices
A11, A12 = A[:half, :half], A[:half, half:]
A21, A22 = A[half:, :half], A[half:, half:]
B11, B12 = B[:half, :half], B[:half, half:]
B21, B22 = B[half:, :half], B[half:, half:]
# 7 recursive multiplications (not 8)
M1 = strassen(A11 + A22, B11 + B22)
M2 = strassen(A21 + A22, B11)
M3 = strassen(A11, B12 - B22)
M4 = strassen(A22, B21 - B11)
M5 = strassen(A11 + A12, B22)
M6 = strassen(A21 - A11, B11 + B12)
M7 = strassen(A12 - A22, B21 + B22)
# 18 additions to assemble C
C11 = M1 + M4 - M5 + M7
C12 = M3 + M5
C21 = M2 + M4
C22 = M1 - M2 + M3 + M6
C = np.zeros((n, n))
C[:half, :half], C[:half, half:] = C11, C12
C[half:, :half], C[half:, half:] = C21, C22
return C// Strassen matrix multiplication — O(n^log2(7)) ≈ O(n^2.807)
// Matrices stored as vector<vector<double>>
#include <vector>
using namespace std;
using Mat = vector<vector<double>>;
Mat add(const Mat& A, const Mat& B, int sign=1) {
int n = A.size();
Mat C(n, vector<double>(n));
for (int i=0;i<n;i++) for (int j=0;j<n;j++)
C[i][j] = A[i][j] + sign*B[i][j];
return C;
}
Mat strassen(const Mat& A, const Mat& B) {
int n = A.size();
if (n <= 64) { // base: naive for small n
Mat C(n, vector<double>(n, 0));
for(int i=0;i<n;i++) for(int k=0;k<n;k++) for(int j=0;j<n;j++)
C[i][j] += A[i][k]*B[k][j];
return C;
}
int h = n/2;
// Extract submatrices
auto sub = [&](const Mat& M, int r0, int c0) {
Mat S(h, vector<double>(h));
for(int i=0;i<h;i++) for(int j=0;j<h;j++) S[i][j]=M[r0+i][c0+j];
return S;
};
auto A11=sub(A,0,0), A12=sub(A,0,h), A21=sub(A,h,0), A22=sub(A,h,h);
auto B11=sub(B,0,0), B12=sub(B,0,h), B21=sub(B,h,0), B22=sub(B,h,h);
auto M1=strassen(add(A11,A22), add(B11,B22));
auto M2=strassen(add(A21,A22), B11);
auto M3=strassen(A11, add(B12,B22,-1));
auto M4=strassen(A22, add(B21,B11,-1));
auto M5=strassen(add(A11,A12), B22);
auto M6=strassen(add(A21,A11,-1),add(B11,B12));
auto M7=strassen(add(A12,A22,-1),add(B21,B22));
// Assemble C from 7 products
Mat C(n, vector<double>(n));
for(int i=0;i<h;i++) for(int j=0;j<h;j++) {
C[i][j] = M1[i][j]+M4[i][j]-M5[i][j]+M7[i][j];
C[i][j+h] = M3[i][j]+M5[i][j];
C[i+h][j] = M2[i][j]+M4[i][j];
C[i+h][j+h] = M1[i][j]-M2[i][j]+M3[i][j]+M6[i][j];
}
return C;
}The Master Theorem
The Master Theorem solves recurrences of the form $T(n) = aT(n/b) + f(n)$ where $a \geq 1$, $b > 1$. Compare $f(n)$ with $n^{\log_b a}$ (the “critical exponent”):
Master Theorem — three cases:
Case 1: $f(n) = O(n^{\log_b a - \varepsilon})$ for some $\varepsilon > 0$ (leaves dominate) → $T(n) = \Theta(n^{\log_b a})$
Case 2: $f(n) = \Theta(n^{\log_b a} \log^k n)$ for $k \geq 0$ (tied) → $T(n) = \Theta(n^{\log_b a} \log^{k+1} n)$
Case 3: $f(n) = \Omega(n^{\log_b a + \varepsilon})$ and $af(n/b) \leq cf(n)$ for $c<1$ (root dominates) → $T(n) = \Theta(f(n))$
If $n^{\log_b a}$ is greater than $f(n)$ but not polynomially greater, the Master Theorem does not apply (e.g., $T(n) = 2T(n/2) + \Theta(n/\log n)$).
Case 1: $f(n) = O(n^{\log_b a - \varepsilon})$ for some $\varepsilon > 0$ (leaves dominate) → $T(n) = \Theta(n^{\log_b a})$
Case 2: $f(n) = \Theta(n^{\log_b a} \log^k n)$ for $k \geq 0$ (tied) → $T(n) = \Theta(n^{\log_b a} \log^{k+1} n)$
Case 3: $f(n) = \Omega(n^{\log_b a + \varepsilon})$ and $af(n/b) \leq cf(n)$ for $c<1$ (root dominates) → $T(n) = \Theta(f(n))$
If $n^{\log_b a}$ is greater than $f(n)$ but not polynomially greater, the Master Theorem does not apply (e.g., $T(n) = 2T(n/2) + \Theta(n/\log n)$).
| Recurrence | $a$, $b$, $f(n)$ | Case | Solution |
|---|---|---|---|
| $T = 2T(n/2)+\Theta(n)$ | 2, 2, $n$ | Case 2 ($k=0$) | $\Theta(n\log n)$ |
| $T = 7T(n/2)+\Theta(n^2)$ | 7, 2, $n^2$ | Case 1 ($n^{\log_27}\approx n^{2.807}$) | $\Theta(n^{\log_2 7})$ |
| $T = 4T(n/2)+\Theta(n^2)$ | 4, 2, $n^2$ | Case 2 ($k=0$) | $\Theta(n^2\log n)$ |
| $T = 4T(n/2)+\Theta(n^3)$ | 4, 2, $n^3$ | Case 3 ($n^3 \gg n^2$) | $\Theta(n^3)$ |
| $T = T(n/5)+T(7n/10)+\Theta(n)$ | — | Doesn’t apply; use substitution | $\Theta(n)$ |
def convex_hull_dc(points):
"""
Divide-and-conquer convex hull. O(n log n).
points: list of (x, y). Returns upper hull vertices left-to-right.
(Full hull = upper hull + lower hull, both in O(n log n).)
"""
pts = sorted(set(points)) # sort by x, deduplicate
n = len(pts)
if n <= 3:
return pts # base case
mid = n // 2
left_hull = convex_hull_dc(pts[:mid])
right_hull = convex_hull_dc(pts[mid:])
return merge_hulls(left_hull, right_hull)
def cross(O, A, B):
"""Cross product of OA and OB. Positive = left turn."""
return (A[0]-O[0])*(B[1]-O[1]) - (A[1]-O[1])*(B[0]-O[0])
def merge_hulls(left, right):
"""
Merge two convex hulls by finding upper and lower tangents. O(n).
Returns the merged upper hull (simplified for clarity).
"""
# Find upper tangent: rightmost of left, leftmost of right
i = left.index(max(left)) # rightmost point of left hull
j = 0 # leftmost point of right hull
while True:
changed = False
# Move right finger clockwise until it can't improve
while cross(left[i], right[j], right[(j+1) % len(right)]) > 0:
j = (j + 1) % len(right)
changed = True
# Move left finger anticlockwise until it can't improve
while cross(right[j], left[i], left[(i-1) % len(left)]) < 0:
i = (i - 1) % len(left)
changed = True
if not changed:
break
return left[:i+1] + right[j:] # merge along tangent#include <vector>
#include <algorithm>
using namespace std;
struct P { long long x, y; };
long long cross(P O, P A, P B) {
return (A.x-O.x)*(B.y-O.y)-(A.y-O.y)*(B.x-O.x);
}
// Upper hull in O(n) via Graham scan merge
vector<P> upper_hull(vector<P> pts) {
sort(pts.begin(), pts.end(), [](P a, P b){
return a.x < b.x || (a.x==b.x && a.y < b.y);
});
vector<P> h;
for (auto& p : pts) {
while (h.size() >= 2 &&
cross(h[h.size()-2], h.back(), p) >= 0)
h.pop_back();
h.push_back(p);
}
return h;
}
// Full convex hull (upper + lower) — O(n log n) with sort
vector<P> convex_hull(vector<P> pts) {
sort(pts.begin(), pts.end(), [](P a, P b){
return a.x < b.x || (a.x==b.x && a.y < b.y);
});
int n = pts.size(); if (n < 2) return pts;
vector<P> h;
// Upper hull
for (auto& p : pts) {
while (h.size()>=2 && cross(h[h.size()-2],h.back(),p)>=0) h.pop_back();
h.push_back(p);
}
// Lower hull
int upper_size = h.size();
for (int i=n-2; i>=0; --i) {
while ((int)h.size()>upper_size &&
cross(h[h.size()-2],h.back(),pts[i])>=0) h.pop_back();
h.push_back(pts[i]);
}
h.pop_back();
return h;
}
Worked Example · Options Strategy Scheduling
🇮🇳 TTT Strategy
TTT runs multiple option strategies. Each strategy occupies a margin block during $[s_i, f_i]$ and generates expected PnL $w_i$. Only one strategy can hold margin at a time. Maximise total expected PnL.
Model as Weighted Interval Scheduling
Strategies = intervals $[s_i, f_i]$ with weight $w_i$ (expected PnL). Non-overlap constraint = margin constraint. Apply the $O(n\log n)$ DP.
strategies = [
(9, 17, 4200), # NIFTY straddle, 9am-5pm, ₹4200 expected PnL
(9, 11, 1800), # BankNifty scalp, 9am-11am
(11, 17, 2900), # NIFTY spread, 11am-5pm
(9, 13, 3100), # NIFTY butterfly, 9am-1pm
(13, 17, 1600), # Afternoon hedge, 1pm-5pm
]
# As (start, finish, weight) tuples
result = weighted_interval_scheduling(strategies)
print(result) # 4700 = BankNifty (1800) + NIFTY spread (2900)
Optimal: BankNifty scalp [9,11] + NIFTY spread [11,17] = ₹4,700. The full-day straddle (₹4,200) is suboptimal — the greedy rule (pick highest weight) fails; DP finds the globally optimal non-overlapping subset.
Weighted Interval Scheduling directly models multi-strategy capital allocation: strategies compete for the same margin capital during overlapping time windows. The $O(n\log n)$ DP gives the globally optimal subset. For TTT’s expiry-day strategies, where STRATEGY_01, STRATEGY_06, STRATEGY_08, and VOLT_OTM all contend for NIFTY margin during morning volatility, this framework picks which strategies to run. Strassen matters less in quant finance directly — but the divide-and-conquer thinking (reduce 8 operations to 7 by clever combination) appears in options Greeks calculation and covariance matrix inversion shortcuts.
Practice Problems
4 questions · Chapter 01
prog / daa / ch01 / q01
★ Master Theorem
What is the solution to $T(n) = 4T(n/2) + \Theta(n^2)$?
Answer: B — $\Theta(n^2 \log n)$.
$a=4$, $b=2$, so $n^{\log_b a} = n^{\log_2 4} = n^2$. Since $f(n) = \Theta(n^2) = \Theta(n^{\log_b a} \cdot \log^0 n)$, this is Case 2 with $k=0$: $T(n) = \Theta(n^2 \log^{0+1} n) = \Theta(n^2 \log n)$.
This recurrence appears when merge sort is applied to a 2D problem where the merge step costs $O(n^2)$ per level. There are $\log n$ levels, each doing $O(n^2)$ total work — hence the $\log$ factor.
$a=4$, $b=2$, so $n^{\log_b a} = n^{\log_2 4} = n^2$. Since $f(n) = \Theta(n^2) = \Theta(n^{\log_b a} \cdot \log^0 n)$, this is Case 2 with $k=0$: $T(n) = \Theta(n^2 \log^{0+1} n) = \Theta(n^2 \log n)$.
This recurrence appears when merge sort is applied to a 2D problem where the merge step costs $O(n^2)$ per level. There are $\log n$ levels, each doing $O(n^2)$ total work — hence the $\log$ factor.
prog / daa / ch01 / q02
★★ Strassen
Strassen uses 7 multiplications instead of 8 per recursion. Why is this the key insight, and what would happen if someone found a way to use only 6?
Answer: B.
The recurrence is $T(n) = mT(n/2) + \Theta(n^2)$ where $m$ is the number of multiplications. By Case 1 of the Master Theorem (as long as $m > 4 = n^{\log_2 4}$), the solution is $\Theta(n^{\log_2 m})$. So $m=8 \Rightarrow n^3$, $m=7 \Rightarrow n^{2.807}$, $m=6 \Rightarrow n^{2.585}$. Each multiplication saved shaves the exponent. The current world record is approximately $n^{2.371}$ (Vassilevska Williams et al., 2024). Whether the true lower bound is $\omega = 2$ is one of the biggest open problems in theoretical computer science.
The recurrence is $T(n) = mT(n/2) + \Theta(n^2)$ where $m$ is the number of multiplications. By Case 1 of the Master Theorem (as long as $m > 4 = n^{\log_2 4}$), the solution is $\Theta(n^{\log_2 m})$. So $m=8 \Rightarrow n^3$, $m=7 \Rightarrow n^{2.807}$, $m=6 \Rightarrow n^{2.585}$. Each multiplication saved shaves the exponent. The current world record is approximately $n^{2.371}$ (Vassilevska Williams et al., 2024). Whether the true lower bound is $\omega = 2$ is one of the biggest open problems in theoretical computer science.
prog / daa / ch01 / q03
★★ Greedy vs DP
Greedy (earliest finish time) solves unweighted interval scheduling optimally. Why does it fail for weighted interval scheduling?
Answer: C.
Concrete counterexample: three intervals $[1,3]$ weight 1, $[2,5]$ weight 10, $[4,6]$ weight 10. Earliest finish picks $[1,3]$ first (finish=3), then $[4,6]$ (finish=6) for total weight 11. But $[2,5]$ and $[4,6]$ overlap — we can’t take both. Optimal is $[1,3]+[4,6]=11$ or $[2,5]=10$, so greedy gets 11 here. Better example: $[1,4]$ weight 3, $[2,3]$ weight 1, $[3,5]$ weight 3. Greedy takes $[2,3]$ first (earliest finish), then $[3,5]$, total 4. Optimal is $[1,4]=3$... Actually greedy gets 4 here too. The canonical counterexample: $[1,6]$ weight 10 vs $[1,3]$ weight 3 and $[4,6]$ weight 3. Greedy takes $[1,3]$ then $[4,6]$ = 6. Optimal is just $[1,6]$ = 10. Greedy fails.
Concrete counterexample: three intervals $[1,3]$ weight 1, $[2,5]$ weight 10, $[4,6]$ weight 10. Earliest finish picks $[1,3]$ first (finish=3), then $[4,6]$ (finish=6) for total weight 11. But $[2,5]$ and $[4,6]$ overlap — we can’t take both. Optimal is $[1,3]+[4,6]=11$ or $[2,5]=10$, so greedy gets 11 here. Better example: $[1,4]$ weight 3, $[2,3]$ weight 1, $[3,5]$ weight 3. Greedy takes $[2,3]$ first (earliest finish), then $[3,5]$, total 4. Optimal is $[1,4]=3$... Actually greedy gets 4 here too. The canonical counterexample: $[1,6]$ weight 10 vs $[1,3]$ weight 3 and $[4,6]$ weight 3. Greedy takes $[1,3]$ then $[4,6]$ = 6. Optimal is just $[1,6]$ = 10. Greedy fails.
prog / daa / ch01 / q04
★★★ Median of Medians
Median of Medians uses groups of 5. Why 5, and not 3 or 7?
Answer: C.
With groups of size $g$, the pivot eliminates at least a $\frac{g-1}{2g}$ fraction of elements. For $g=3$: fraction $\frac{1}{3}$, so recurrence is $T(n) = T(n/3) + T(2n/3) + \Theta(n)$. The $T(n/3)+T(2n/3)$ part sums to $T(n)$ times $1/3+2/3=1$, giving $T(n) = \Omega(n\log n)$. Not linear!
For $g=5$: fraction $3/10$, recurrence $T(n/5)+T(7n/10)+\Theta(n)$. Now $1/5+7/10=9/10 < 1$, giving $T(n)=O(n)$ by substitution. For $g=7$: even better fraction, but sorting groups of 7 costs more. The constant in $O(n)$ grows. $g=5$ is the smallest group size that makes the algorithm linear — the sweet spot.
With groups of size $g$, the pivot eliminates at least a $\frac{g-1}{2g}$ fraction of elements. For $g=3$: fraction $\frac{1}{3}$, so recurrence is $T(n) = T(n/3) + T(2n/3) + \Theta(n)$. The $T(n/3)+T(2n/3)$ part sums to $T(n)$ times $1/3+2/3=1$, giving $T(n) = \Omega(n\log n)$. Not linear!
For $g=5$: fraction $3/10$, recurrence $T(n/5)+T(7n/10)+\Theta(n)$. Now $1/5+7/10=9/10 < 1$, giving $T(n)=O(n)$ by substitution. For $g=7$: even better fraction, but sorting groups of 7 costs more. The constant in $O(n)$ grows. $g=5$ is the smallest group size that makes the algorithm linear — the sweet spot.
Terminal Questions — Chapter 01
10 problems · No answers given
Work through independently. Q1–3 direct application. Q4–7 synthesis. Q8–10 careful argument.
1
Apply the Master Theorem to each: (a) $T=3T(n/3)+\Theta(n)$, (b) $T=2T(n/4)+\Theta(1)$, (c) $T=8T(n/2)+\Theta(n^2)$, (d) $T=4T(n/2)+\Theta(n^2\log n)$. State which case applies and give the solution. Easy
2
Run the Weighted Interval Scheduling DP on intervals $\{[1,4,3],[2,6,5],[3,5,4],[5,9,6],[6,10,2]\}$ (start, finish, weight). Fill the $M$ array, find $p(j)$ for each $j$, and trace back the optimal set. Easy
3
Verify Strassen's seven products by expanding $M_1+M_4-M_5+M_7$ algebraically to show it equals $A_{11}B_{11}+A_{12}B_{21}$. Then verify $C_{22} = M_1-M_2+M_3+M_6 = A_{21}B_{12}+A_{22}B_{22}$. Easy
4
Implement Randomised Quickselect (pivot chosen uniformly at random) and compare its expected running time to Median of Medians empirically on arrays of size $n = 10^3, 10^4, 10^5$. Which is faster in practice? Why might the $O(n)$ worst-case algorithm be slower in practice? Medium
5
The recurrence $T(n) = T(n/5) + T(7n/10+6) + \Theta(n)$ does not satisfy the Master Theorem. Prove $T(n) = \Theta(n)$ using the substitution method: assume $T(n) \leq cn$ for some $c$, substitute, and find the required lower bound on $c$. Medium
6
Design a divide-and-conquer algorithm for the closest pair of points problem: given $n$ points in the plane, find the pair with minimum Euclidean distance. Prove your recurrence and show the merge step runs in $O(n)$, giving $T(n) = 2T(n/2) + O(n) = O(n\log n)$. Medium
7
Non-identical machines: you have $n$ jobs and $m$ machine types. Job $i$ can run on machine types $Q(i) \subseteq \{T_1,\ldots,T_m\}$. Each machine can handle one job at a time. Argue why greedy (earliest finish) fails, and explain why the decision version (can $k$ jobs be scheduled?) is NP-complete by reduction from bipartite matching extended to multiple constraints. Medium
8
Prove the correctness of the divide-and-conquer convex hull merge: if $(a_i, b_j)$ is the pair that maximises $y(i,j)$ (the $y$-coordinate of the tangent line at the separator), then $(a_i, b_j)$ is the upper tangent. Hint: show that if it isn’t, some point lies above the line. Hard
9
The Akra-Bazzi theorem generalises the Master Theorem to recurrences of the form $T(n) = \sum_{i=1}^{k} a_i T(n/b_i) + f(n)$. Apply it to the Median of Medians recurrence $T(n) = T(n/5) + T(7n/10) + \Theta(n)$. Find the characteristic exponent $p$ where $\sum a_i/b_i^p = 1$, and state the solution. Hard
10
Strassen uses 7 multiplications for $2\times2$ block decomposition. Prove that any algorithm computing $2\times2$ matrix products using the standard bilinear algorithm framework requires at least 7 multiplications (the Winograd-Pan lower bound argument). What does this say about $\omega$, the exponent of matrix multiplication? Hard