Randomness, at scale

Markov: $P(X \ge 16) \le 4/16 = 0.25$. Option A is $(4/16)^2$ — the tempting move of "squaring because Chebyshev has a square", but you have no variance, so Chebyshev is unavailable. D is wrong because Markov needs only non-negativity and the mean, both of which you have.

Convert the absolute threshold into $\sigma$-units first: $k\sigma = 20 \Rightarrow k = 20/5 = 4$. Then $P \le 1/k^2 = 1/16 = 0.0625 \approx \mathbf{0.06}$.

The trap answer is $1/20^2 = 0.0025$, from forgetting to divide by $\sigma$.

A is false: Markov demands $X \ge 0$. (You could apply it to $X + 3$, but not to $X$.)

C is false: Chebyshev is a statement about a single random variable — no independence anywhere. Independence is Hoeffding's requirement.

D is true: $e^{-2nt^2}$ beats $\sigma^2/(nt^2)$ eventually, and "eventually" arrives fast.

Here $X_i \in [0,1]$ so $b-a=1$, and $t = 0.1$. Require $e^{-2n(0.01)} \le 0.05$, i.e. $-0.02n \le \ln 0.05 = -2.9957$, giving $n \ge 149.79$. So $n = \mathbf{150}$.

Note this is the one-sided form. If the question had asked for $P(|\bar X - 0.5| \ge 0.1)$, you would first union-bound the two tails to get $2e^{-2nt^2} \le 0.05$, and $n$ would rise to $185$.

Union bound gives $\le 100 \times 0.001 = 0.1$, and that is all you can say. A and D both assume something extra: D is the answer if the events were independent, which you were never told. This distinction is the entire reason the union bound is the tool of choice in the JL proof — the pairwise events there are dependent, and $1-(1-p)^m$ is not available.

$k \in O(\log n/\epsilon^2)$ has no $d$ in it. Doubling $d$ changes nothing about $k$; it only makes the reduction more worthwhile. What does change is the cost of applying the map, $O(ndk)$, which doubles.

$\dfrac{2n^2}{\delta} = \dfrac{2\times10^6}{0.1} = 2\times 10^7$, so $\ln(2\times10^7) = \ln 2 + 7\ln 10 = 0.693 + 16.118 = 16.811$.

And $\dfrac{8}{\epsilon^2} = \dfrac{8}{0.25} = 32$. So $k \ge 32 \times 16.811 = 537.96$, giving $k = \mathbf{538}$.

Two things to watch: the paper may specify $\log_2$ instead of $\ln$ (which would change the number), and the $2$ inside $\log\frac{2n^2}{\delta}$ is the two-sided factor — drop it and you get $536$ instead.

B is false: $M$ never depends on the data — only on $d$, $n$, $\epsilon$. (Strictly, $n$ enters through $k$, so adding enough points eventually nudges $k$; but no recomputation is triggered by the point's values, which is what the option claims.)

C is false: that is exactly the exact-isometry condition proved impossible for $k < d$.

A is true — unbiasedness is exact, not asymptotic. D is true — probabilistic method, deterministic conclusion.

All $\binom{n}{2}$ events are driven by the same random matrix $M$, so they are heavily dependent — the product formula is simply invalid. The union bound is looser (A is backwards) but it needs no independence, which is the entire point. D is wrong too: the events overlap freely.

$k \propto 1/\epsilon^2$, so halving $\epsilon$ quadruples $k$. Accuracy is expensive: the $\epsilon^{-2}$ dependence, not the $\log n$, is what usually makes $k$ large in practice.

Here $r = 2$ and $cr = 3\times2 = 6$. Distance $5$ satisfies neither $\le 2$ nor $\ge 6$ — it sits in the annulus $(2, 6)$, so… wait: check again. $5 < 6$, so the far condition does not apply.

The correct answer is D. Distance $5$ lies strictly inside the annulus $r < 5 < cr$, where the definition asserts nothing at all. This is exactly the trap: you must compute $cr$ (not compare against $c$) and then check which of the two regimes the distance falls into. Had the distance been $7 \ge 6$, the answer would be B.

$\rho = \dfrac{\log(1/0.9)}{\log(1/0.3)} = \dfrac{0.10536}{1.20397} = \mathbf{0.0875}$.

The base of the logarithm cancels — use whichever you like. Note how a wide $p_1/p_2$ gap gives a tiny $\rho$, hence very few tables: $L = \theta n^{0.0875}$ is almost constant.

AND requires all $k$ coordinates to match, so collisions get strictly harder — both $p_1^k$ and $p_2^k$ shrink. C confuses the two knobs: $k$ is the depth of each table, $L$ is the number of tables. Increasing $k$ does not change $L$.

The mnemonic: AND ↓ both rates (fixes FPR, damages TPR). OR ↑ both rates (fixes TPR, damages FPR). You need both, in that order.

$\log_2(10^6) = 6\log_2 10 = 6 \times 3.3219 = 19.93$, and $\log_2(1/0.5) = 1$. So $k = 19.93 \approx \mathbf{20}$.

Check it does what it is supposed to: $n\,p_2^k = 10^6 \times 2^{-20} = 10^6/1{,}048{,}576 \approx 0.95 \approx 1$. ✓ The choice of $k$ is precisely "make expected false-positive collisions equal to one".

The $n$ cancels exactly — that is the point of choosing $L$ proportional to $n^\rho$. You get a fixed recall guarantee that does not degrade as the dataset grows, and you pay for it in $n^\rho$ tables rather than $n$ distance computations. $\rho$ governs cost and FPR, $\theta$ governs recall.

A, B: the pre-image of a fixed integer is $\{x : jw \le a^\top x + b < (j+1)w\}$ — the region between two parallel hyperplanes with normal $a$. An intersection of two half-spaces, hence convex.

C: the conditional probability $\max(0, 1-|\Delta|/w)$ increases in $w$ for every $\Delta$, so the average does too. Wider buckets, more collisions — for good and bad pairs alike, which is why $w$ must be tuned via $\hat\rho(w)$ rather than simply maximised.

D: $\Delta \sim \mathcal N(0, \|x-y\|^2)$ depends on the pair only through that norm. The collision probability is rotation- and translation-invariant.

Exact: $\mathrm{FPR} = 1 - (1 - 0.4^{10})^{20}$. Since $0.4^{10} = 1.0486\times10^{-4}$, this is $\approx 20 \times 1.0486\times10^{-4} = 2.097\times10^{-3}$. Times $8000$ gives $\mathbf{16.8 \approx 17}$.

The professor's slide quotes $\approx 20$, using the cleaner asymptotic $\theta n^{\rho} = 2 \times 10^{0.2435\times4} \approx 20$, which counts against all $n = 10^4$ points rather than only the $8000$ bad ones. Both are right at this level of precision — but if a paper gives you exact $k$, $L$ and a bad-point count, compute directly from $1-(1-p_2^k)^L$.

In the full SVD, $\Sigma$ has the same shape as $A$: $U$ is $5000\times5000$, $\Sigma$ is $5000\times200$, $V^\top$ is $200\times200$. Only the top $200\times200$ block of $\Sigma$ is non-zero; the bottom $4800$ rows are all zeros. Option A is the shape in the thin/economy SVD — a real distinction, so read which one the question asks for.

C is false — and it is the classic swap. $A^\top A = V\Sigma^2V^\top$ gives the right singular vectors; $AA^\top = U\Sigma^2U^\top$ gives the left ones. Mnemonic: "$A^\top A$ is $d\times d$, lives in feature space, gives $V$."

B is true: both equal $\{\sigma_i^2 : \sigma_i > 0\}$; they differ only in how many extra zeros they carry ($AA^\top$ has $m-d$ more).

Eckart–Young: the error is $\sigma_{k+1}$ with $k = 3$, so $\sigma_4 = \mathbf{3}$.

Traps: $\sigma_3 = 6$ (off-by-one — the error is the first value you discard, not the last you keep) and $\sqrt{3^2+1^2} = \sqrt{10}$ (that would be the Frobenius-norm error, a different theorem that this course does not state).

$\ell = k + p = 25$, so $Q$ is $10^6 \times 25$ and $B = Q^\top A$ is $\mathbf{25} \times 5000$. That is the entire point: you run an exact SVD on a $25\times5000$ matrix rather than a $10^6\times5000$ one.

Note $B$ has $\ell$ rows, not $k$. The truncation to $k$ happens later, at the pull-back step.

A flat spectrum is precisely the failure mode Davis–Kahan predicts: $\|QQ^\top - U_kU_k^\top\| \lesssim \sigma_{k+1}/\sigma_k \approx 0.98$, i.e. no guarantee at all. Power iteration replaces that ratio with $0.98^{2q+1}$ — with $q = 10$, $0.98^{21} = 0.65$. Oversampling (A) helps the probability of a good sketch but does nothing about an intrinsically indistinguishable spectrum.

B is false: $A\Omega$ combines columns — $A\omega = \sum_i \omega_i a_i$ where $a_i$ are columns. (Row combinations would be $\Omega^\top A$.)

D is false: $\epsilon = 6\sqrt{\frac{k+p}{p}\ln\frac2\delta}$ is undefined at $p=0$ — the bound diverges. Oversampling is structurally required, not a tuning nicety.

$(AA^\top)^qA = U\Sigma^{2q+1}V^\top$, so the exponent is $2q+1 = 2(2)+1 = \mathbf{5}$.

Common slips: answering $2q = 4$, or $q = 2$. Remember the odd power comes from the trailing single $A$ — $q$ full "squarings" plus one.

Edges leaving $\{1,2\}$: $\{2,6\}$ and $\{2,4\}$. The edge $\{1,2\}$ is internal and does not count. So the cut is $\mathbf{2}$.

Check with the quadratic form, $f = (1,1,0,0,0,0)$: contributions from $\{2,6\}$ and $\{2,4\}$ are $1$ each, everything else $0$. ✓

C is false, and it follows from B: a zero eigenvalue means $L$ is singular. This is exactly why the sparsification formula needs the pseudo-inverse $L^\dagger$ rather than $L^{-1}$.

D is the reason for B: $L\mathbf 1 = 0$ directly, since $L_{ii} = \sum_j w_{ij}$ and the off-diagonals are $-w_{ij}$.

Without it, the minimiser is $f = \tfrac{1}{\sqrt n}\mathbf 1$ with objective $0$ — "put everything in one cluster". Forcing orthogonality to $\mathbf 1$ deletes that direction and promotes the answer to $f_2$. C is a property of $L$ that holds regardless of any constraint.

A ring is not convex, so it can never be a Voronoi cell — k-means will slice both rings along a diameter regardless of initialisation. In the similarity graph, though, each ring is densely connected internally and weakly connected to the other, so the cheapest cut separates them, and the Fiedler vector finds it. Linear separability (C) is irrelevant: after the spectral embedding, the clusters become separable, which is precisely the point.

$w' = w/p = 0.6/0.2 = \mathbf{3}$ — you divide by $p$, which makes surviving edges heavier, not lighter. B multiplies instead, and is the natural wrong answer.

D is false, and this is the key conceptual point: unbiasedness holds for any $p_{ij} > 0$, since the $p$ and $1/p$ cancel. Effective resistance is chosen to control variance — so the estimate concentrates and the $(1\pm\epsilon)$ guarantee holds w.h.p., with few enough edges.

The bridge has the highest effective resistance — no alternative path exists, so removing it disconnects the graph and destroys the spectrum. It must be kept with probability $\approx 1$. Clique-internal edges are redundant ($p \propto 1/n$). C is a distractor: high weight does not imply high effective resistance — a heavy edge buried in a clique is still replaceable. D is the trap from the previous question.

$|F| = O(n\log n) = 10^6 \times \log(10^6)$. With natural log, $\ln 10^6 \approx 13.8$, giving $\approx 1.4\times10^7$; with $\log_2$, $\approx 20$, giving $2\times10^7$. Either way the exponent is $t = \mathbf{7}$.

That is a reduction of roughly four orders of magnitude — from $5\times10^{11}$ to $\sim10^7$ — which is the difference between "impossible" and "runs on a laptop".

The professor is deliberate about this distinction. NP-hard = no polynomial algorithm known, a complexity-theoretic barrier — that describes the balanced binary cut problem. Computationally expensive = polynomial but slow, which is what dense eigen-decomposition (C, D) is, and what sparsification addresses. The relaxation attacks the first problem; sparsification attacks the second.

Let $Z = \|X\| \ge 0$ with $\mathbb{E}[Z] = 10$. Markov: $P(Z \ge 50) \le 10/50 = 0.2$. Complement: $p = P(Z \le 50) \ge 1 - 0.2 = \mathbf{0.8}$.

Traps: D is the raw Markov number without the complement. B has the complement but keeps the inequality direction — an upper bound on the tail is a lower bound on $p$. C is true but weaker, and the question says "tightest".

$k \in O(\log n/\epsilon^2)$ — no $d$. Same $n$, same $\epsilon$ ⟹ the same $k$ works for both.

Traps: A and B encode "a 1000× bigger space needs a 1000× bigger embedding" — exactly the intuition JL demolishes. The load-bearing phrase is "same number of data-points": that is the only quantity that matters.

"Whenever $X$ occurs, $Y$ occurs" is set containment $X \subseteq Y$: the smaller event sits inside. Hence $P(X) \le P(Y)$ — the subset inequality used throughout the JL proof.

Trap: B is the reversed containment and is the most common error — the arrow in "$X \to Y$" makes it feel like $X$ should be the bigger, outer set. Implication shrinks the event.

The singular values of a Gaussian matrix concentrate in a narrow band — for aspect ratio $\beta = 10^4/10^5 = 0.1$ they lie roughly in $\sqrt N(1\pm\sqrt\beta) \approx [0.68, 1.32]\sqrt N$. Plotted from zero, that band is a spike.

This is the matrix-level restatement of JL: $\sigma_{\min} \approx \sigma_{\max}$ means the map is nearly a scaled isometry — the sphere goes to a nearly spherical ellipsoid. Same fact as the "$\sigma_i \approx \sqrt{d/k}$" line in the Week 2 linear-algebra lecture.

Trap: A is the reflex — "Gaussian entries, so Gaussian singular values". Singular values are a highly non-linear function of the entries.

$\operatorname{Cov}(A\omega) = A\operatorname{Cov}(\omega)A^\top = AA^\top$. Row 1 of $A$ is $(1,4)$: $1+16 = 17$. Row 2 is $(3,1)$: $9+1 = 10$. Cross: $3+4 = 7$.

Trap: B is $A^\top A$ — same trace, same off-diagonal, only the diagonal order differs, so it survives a glance. This is the identity behind randomized SVD ($\operatorname{Cov}(A\omega) = AA^\top$, whose eigenvectors are the left singular vectors); getting it backwards breaks that whole story. C squares each entry.

Level sets of $\lfloor(a^\top x + b)/w\rfloor$ are parallel slabs perpendicular to $a$, of equal width $w$. The direction of $a$ is random (any slope allowed) and $b$ shifts them, so both stripe pictures are realisable.

Traps: B is seductive — "Euclidean LSH, so round buckets" — but rings hash by norm: two antipodal points on the same ring collide despite being maximally far apart. C is half-right: a single linear projection can never carve out a bounded closed region. And since this is an MSQ, ticking only A scores zero.

$P(p) = 1-(1-p^k)^L$ is strictly increasing in $L$ for every $p \in (0,1)$. So it lifts the rate for near pairs ($p \ge p_1$) and for far pairs ($p \le p_2$) at the same time. More tables buy recall and pay in precision, memory, and candidate-filtering time.

Trap: D comes from conflating $L$ with $k$. It is $k$ (the AND) that drives both rates down. Ticking only A also loses the marks — the point of the question is that both move the same way.

Step 1 — diameter upstairs. For $x,y$ on the unit sphere, the triangle inequality through the origin gives $\|x-y\| \le \|x\| + \|y\| = 2$.

Step 2 — apply JL, then square-root. $\|f(x)-f(y)\|^2 \le (1+\epsilon)\|x-y\|^2$, so

Traps: (i) Using diameter $1$ instead of $2$ — the points lie on the unit sphere, so the farthest pair is antipodal. (ii) Multiplying the distance by $(1+\epsilon)$ instead of $\sqrt{1+\epsilon}$, giving $2.0402$. The value $\epsilon = 0.0201$ is engineered so $\sqrt{1+\epsilon} = 1.01$ exactly — that is the examiner telling you to take a square root.

Eckart–Young: $\|A - A_k\|_2 = \sigma_{k+1}$. With $k=4$, that is $\sigma_5 = \mathbf{0.01}$.

Traps: $\sigma_4 = 1$ (off-by-one — the error is the first value discarded). Or the Frobenius answer $\sqrt{0.01^2 + 0.001^2} \approx 0.01005$ — the subscript $2$ means spectral norm, so only the largest discarded value counts. The tiny $\sigma_6 = 0.001$ exists purely to make that mistake feel reasonable.

For a singleton, the cut equals the weighted degree. Degrees: $d_1 = 1+2 = 3$, $d_2 = 1+3 = 4$, $d_3 = 2+3 = 5$, and identically $3, 4, 5$ for vertices $4,5,6$. Minimum is $\mathbf{3}$ at $A = \{1\}$ or $\{4\}$.

Trap: The graph is deliberately disconnected, so the global mincut really is $0$ (take $A = \{1,2,3\}$). The constraint $|A| = 1$ forbids that. Reading past the cardinality constraint is the entire trap. Secondary slip: answering $1$, the smallest single edge weight, instead of summing all edges at the vertex.

Diagonal = weighted degrees $(3,4,5,3,4,5)$; off-diagonal $= -w_{ij}$; zeros across the blocks because the components are disconnected. Since there are two components, $\lambda = 0$ has multiplicity $2$.

Trap: The distractor is $-W$ — right off-diagonals, right sparsity, but a zero diagonal. Kill it with the row-sum test: every row of a Laplacian sums to $0$; in $-W$ every row sums to a negative number. (The source PDF is truncated here, so options C and D are not recoverable.)

For square orthogonal $Q$, $\|Qv\|^2 = v^\top Q^\top Q v = \|v\|^2$ — an exact isometry on $\mathbb{R}^k$. So $\|QMx\| = \|Mx\|$ and $QM$ inherits the identical $\epsilon$. And $Q$ orthogonal ⟹ $Q^\top = Q^{-1}$ is orthogonal too, so the same argument gives B.

Trap: C targets students half-remembering "$Q^\top Q = I$ but $QQ^\top \ne I$". That caveat is for rectangular matrices with orthonormal columns. Here $Q$ is explicitly square, so both products are $I$ and A and B stand or fall together — which makes C self-defeating.

The structural fact: each hash's level set is a slab (convex), so a bucket of $g$ is an intersection of $k$ slabs — also convex. If $x_1, x_2$ share a bucket, the whole segment between them does.

A: $x_3$ is a convex combination, so it's on the segment. ✓

C: pure algebra — $x_3 + (1-\lambda)x_1 + \lambda x_2 = \lambda x_1 + (1-\lambda)x_2 + (1-\lambda)x_1 + \lambda x_2 = x_1 + x_2$. It is literally the same point, so it trivially collides with itself. Expand before you think geometrically.

D: $= \tfrac\lambda2 x_1 + (1-\tfrac\lambda2)x_2$, a convex combination with $\mu = \lambda/2 \in (0,\tfrac12)$. ✓

Trap — B, and it is one word: $\forall \beta \in \mathbb{R}$. Convexity protects $\beta \in [0,1]$ only. Outside that you are on the line's extension, which walks out of the slab. Convex hull, not affine hull.

$Z \ge 0$, and by linearity of expectation (which needs no independence) $\mathbb{E}[Z] = 30$. Markov: $P(Z \ge 60) \le 30/60 = \mathbf{0.5}$.

Trap: "with the available information" is load-bearing. No variance, no independence ⟹ Chebyshev and Hoeffding are unavailable and $0.5$ genuinely is the tightest derivable bound. Splitting into $P(X\ge20) + P(Y\ge40) \le 1$ via the union bound is legal but strictly weaker.

Each row satisfies $r_i^\top u \sim \mathcal N(0, \|u\|^2)$, so $\mathbb{E}[(r_i^\top u)^2] = \|u\|^2 = 100$. Over $k = 25$ rows: $\mathbb{E}\|Ru\|^2 = 25 \times 100 = 2500$. Then $A = R/5$ scales the squared norm by $1/25$:

Note $5 = \sqrt{25} = \sqrt k$ — this is $M = R/\sqrt k$, and the answer coming out as exactly $\|u\|^2$ is the unbiasedness result, not a coincidence.

Traps: forgetting the scaling ($2500$); dividing by $5$ once instead of $25$ ($500$) — the scalar squares inside $\|\cdot\|^2$. The ambient $10000$ is a pure red herring, which is itself the JL punchline.

With $X_{uv} \sim \mathrm{Bernoulli}(p_{uv})$ indicating retention,

so the difference has expectation $\mathbf{0}$, for every fixed $f$.

Trap: grinding out algebra expecting an $f$-dependent mess — the whole design of the $1/p$ reweighting is to make this identically zero. Deeper trap: unbiasedness holds for any $p_{uv} > 0$. Effective resistance buys concentration, not correctness-on-average. Zero expected error is not zero error.

Q85 → C. Euclidean (Datar) LSH buckets are parallel slabs of width $w$ perpendicular to a random direction. Two points in the same slab differ by at most $w$ along that direction; ANDing $k$ of them bounds the separation in $k$ random directions, hence the Euclidean distance w.h.p.

Q86 → B. Cosine similarity depends only on the angle and is scale-invariant, so its buckets must be cones through the origin — exactly what lines through the origin produce (SimHash: $h_a(x) = \mathrm{sign}(a^\top x)$, collision probability $1-\theta/\pi$).

Traps: A and D bucket by norm — antipodal points on the same ring always collide, which is anti-locality-sensitive; and no single linear hash can produce a bounded region. The paired structure is deliberate: answering both with the same partition guarantees losing one. Discriminator: is the similarity scale-invariant? Cosine yes → wedges. Euclidean no → stripes.

Setup. Using the paper's hint $D^\top D = \sum_j i_j v_jv_j^\top$. Since the $v_j$ are orthonormal this is the spectral decomposition: eigenvalues $12, 9, 2, 1, 1$ plus $0$ with multiplicity $d - 5 = 5$.

Q87 → 25. $n = 12+9+2+1+1$. Note $n = 25$, $d = 10$, $\mathrm{rank} = 5$ are three different numbers, each used in a different sub-question.

Q88 → A, B, C ($0$, $1$, $3$). Singular values are square roots: $\sqrt{12}\approx3.46$, $\sqrt9 = 3$, $\sqrt2$, $1$, $1$, and $0$ (five times, since $d > \mathrm{rank}$). $12$ is an eigenvalue of $D^\top D$, not a singular value of $D$ — the multiplicities are handed to you looking like an answer list. Also easy to miss $0$.

Q89 → 0.48. Decode $W$ first: a 0/1 column summing to $1$ is a random standard basis vector, so $D^\top\varepsilon_t$ is the $t$-th row of $D$ — one uniformly sampled data point. This is a sampling sketch, not a Gaussian one. With $\ell=1$, $\mathrm{span}(Z_\ell)$ is a single line, and since the $v_j$ are orthonormal it contains $v_1$ iff the sampled point is $v_1$: $12/25 = \mathbf{0.48}$.

Q90 → 0.93. $\ell = k+p = 4$ draws; $v_1$ is captured iff at least one hits: $1 - 0.52^4 = \mathbf{0.9269}$. Three extra columns take failure from $52\%$ to $7\%$ — the whole argument for oversampling, in one number.

Q91 → 0.93, unchanged. $Z^{(2)} = (D^\top D)Z^{(1)}$ multiplies each sampled column $v_j$ by the positive scalar $i_j$, which does not change the span. Power iteration improves accuracy, never coverage — if no draw was $v_1$, nothing conjures it.

Traps: answering $1$ on Q89 by reading $W$ as Gaussian; answering $0.2$ by sampling uniformly over the 5 directions instead of the 25 points (the multiplicities are the sampling weights — this is why leverage-score sampling exists); $4 \times 0.48 = 1.92 > 1$ on Q90; and expecting Q91 to go up.

Weighted degrees: $d_1 = 3+2+10 = 15$, $d_2 = 3+2 = 5$, $d_3 = 2+1 = 3$, $d_4 = 10+2+1 = 13$.

Q92 → 13. $V\setminus A = \{4\}$, so the cut is just $d_4 = 10+2+1 = \mathbf{13}$. Trap: summing the edges inside $A$ ($3+2+0 = 5$), or missing $w_{34}=1$ (drawn as a long curved arc along the bottom — that layout is deliberate).

Q93 → A, B, D, i.e. $A^* = \{1,2,4\}$. Enumerate: $\mathrm{cut}\{1\} = 15$, $\{2\} = 5$, $\{3\} = 3$, $\{4\} = 13$, $\{1,2\} = 14$, $\{1,3\} = 14$, $\{1,4\} = 8$. The smallest non-zero value is $\mathbf{3}$, achieved by the complementary pair $\{3\}$ and $\{1,2,4\}$; the key commits to the large side. Vertex 3 is the loosely-attached one, so peeling it off is cheapest — exactly what the Fiedler vector would find.

Careful: $\{3\}$ and $\{1,2,4\}$ have identical cut value, so this MSQ is genuinely ambiguous. Reasoning toward the singleton makes you tick only C and score zero. Heuristic: when three of four membership options are true, the large side is intended. Also note "non-zero" — without it, $A = \emptyset$ gives $0$ and the question is degenerate.

Q94 → 17. $L_{11} = d_1 = 15$ and $L_{42} = -w_{42} = -2$, so $15 - (-2) = \mathbf{17}$. The double negative is the whole point of asking for a difference. Secondary traps: using the unweighted degree $3$ for $L_{11}$; and indexing — the paper says "indices start from one" for a reason.

Markov: $P(T \ge 25) \le 4/25 = 0.16$. Complement: $P(T < 25) \ge 1 - 0.16 = \mathbf{0.84}$.

The complement step is the recurring archetype — it appeared in both past papers.

$k \ge \frac{8}{\epsilon^2}\log\frac{2n^2}{\delta}$ involves $n$, $\epsilon$ and $\delta$ — never $d$. $\delta$ counts because it sits inside the log, even though its influence is weak.

If you ticked only A and C you would score zero on an MSQ. Read the full bound, not just the $O(\log n/\epsilon^2)$ headline.

$r = 1$, $cr = 4\times1 = 4$. Distance $3.5$ satisfies neither $\le 1$ nor $\ge 4$ — it lies in the annulus $(1,4)$, where the definition asserts nothing. Always compute $cr$; never compare against $c$ alone.

$\mathrm{rank}(A) = $ number of non-zero singular values $= 3$. And $\|A - A_2\|_2 = \sigma_3 = 2$. Product $= 3 \times 2 = \mathbf 6$.

Trap on the rank: it is not $\min(6,4) = 4$, because $\sigma_4 = 0$.

$\deg(2) = 2$ so $L_{22} = 2$. Vertices $1$ and $3$ are not adjacent, so $w_{13} = 0$ and $L_{13} = -0 = \mathbf{0}$. Sum $= \mathbf{2}$.

For reference, $L = \begin{bmatrix}1&-1&0&0\\-1&2&-1&0\\0&-1&2&-1\\0&0&-1&1\end{bmatrix}$ — check each row sums to zero.

$(b-a)^2 = (6-2)^2 = 16$. So the bound is $e^{-2n(0.25)/16} = e^{-n/32}$.

Traps: B uses $b-a = 2$ (the lower endpoint, not the range); C uses $b^2 = 36$; D silently assumes $[0,1]$. The range matters, not the endpoints individually — the bound is invariant to shifting the interval.

D is false: $\Omega$ is $d \times \ell$, so that $Y = A\Omega$ works dimensionally ($m\times d$ times $d\times\ell$). Getting $\Omega$'s orientation wrong breaks the whole pipeline, and it's the easiest shape to invert mentally.

Shape chain to memorise: $\Omega_{d\times\ell} \to Y_{m\times\ell} \to Q_{m\times\ell} \to B_{\ell\times d} \to \hat U_{m\times k}$.

Base-2 throughout: $\log_2 n = 20$, $\log_2(1/0.25) = \log_2 4 = 2$. So $k = 20/2 = \mathbf{10}$.

Check: $n p_2^k = 2^{20} \times 4^{-10} = 2^{20}/2^{20} = 1$. ✓  Bonus: $\rho = \log(1/0.5)/\log(1/0.25) = 1/2$, so $L = \theta n^{0.5} = \theta \cdot 1024$.

Two details separate B from C: $f_1$ is discarded (it is the constant vector at $\lambda_1 = 0$ and carries no clustering information), and normalisation comes before k-means, not after — the point of projecting the embeddings onto the unit sphere is to make k-means' job easy.

$w' = 8/0.25 = \mathbf{32}$. Expected contribution $= p \cdot w' \cdot (f_u-f_v)^2 = 0.25 \times 32 \times 3 = \mathbf{24}$, which equals $w \cdot (f_u-f_v)^2 = 8 \times 3 = 24$. ✓ Unbiased, as designed.

Note the variance is enormous here: the contribution is $96$ a quarter of the time and $0$ otherwise. That is exactly why the choice of $p$ matters — it controls variance, not the mean.

B is false — the output is an approximation, guaranteed only to be within $(1+\epsilon)\sigma_{k+1}$ with probability $\ge 1-\delta$. Exactness is precisely what you trade away.

C is the real precondition: if the spectrum is flat, $\sigma_{k+1}/\sigma_k \approx 1$ and the subspace bound is vacuous — you then need power iteration.

$\sigma = 3$, so $12 = 4\sigma$ and Chebyshev gives $P(|X| \ge 12) \le 1/16$, hence $P(X \ge 12) \le 1/16$ too.

B is wrong because Markov needs $X \ge 0$, and a mean-zero non-degenerate variable is not non-negative. C is wrong because Hoeffding needs many independent bounded variables — you have one variable of unknown range. This question is really asking: which hypotheses do you actually have?

Singleton cuts are the weighted degrees: $d_1 = 5+1 = 6$, $d_2 = 5+1 = 6$, $d_3 = 1+1 = \mathbf 2$. On three vertices every non-trivial cut is a singleton (or its complement), so the minimum is $\mathbf 2$, at $A = \{3\}$.

Note where the heavy edge ends up: the mincut keeps $1$ and $2$ together precisely because $w_{12} = 5$ is expensive to cross.

Exponentiating first is what turns Markov's weak $1/a$ decay into exponential decay: the free $\lambda$ can then be optimised, giving $\lambda = \epsilon/4$ and the bound $e^{-k\epsilon^2/8}$. Applying Markov to $\|x\|^2$ directly (A) gives only $1/(1+\epsilon)$ — useless.

The MGF of each $x_i^2 \sim \chi^2_1$ is $(1-2\lambda)^{-1/2}$, and independence lets you take the product over the $k$ coordinates.

$\rho = \dfrac{\ln(1/0.8)}{\ln(1/0.2)} = \dfrac{0.2231}{1.6094} = \mathbf{0.1386} \approx 0.14$.

$L = \theta n^\rho = 3 \times (10^6)^{0.1386} = 3 \times 10^{0.8316} = 3 \times 6.78 \approx \mathbf{20}$.

Sanity: $\theta = 3$ ⟹ TPR $= 1 - e^{-3} = 0.95$. Twenty tables gives 95% recall on a million points — that is the headline result of the whole unit.

C is false and is the crux of the relaxation: we abandoned $\{0,1\}^n$ (NP-hard) for $\mathbb{R}^n$. The entries are arbitrary reals, which is exactly why a thresholding or 1-D k-means step is needed afterwards to recover a discrete partition.

A and D restate each other: orthogonality to $\mathbf 1$ deletes the trivial $\lambda_1 = 0$ direction, so the constrained minimum is $\lambda_2$.

Diameter upstairs is $2\times 5 = 10$. JL is on squared distances, so the multiplier on the distance is $\sqrt{1+\epsilon} = \sqrt{1.04} = 1.0198$. Bound $= 10 \times 1.0198 = \mathbf{10.198} \approx 10.2$.

B is $(1+\epsilon)\times10$ — forgetting the square root. C uses the radius instead of the diameter. This is the T2 Q9 archetype with different numbers.

$\dfrac{k+p}{p} = \dfrac{15}{5} = 3$ and $\ln\dfrac{2}{0.01} = \ln 200 = 5.298$. So

and $\|A - QQ^\top A\|_2 \le (1+\epsilon)\sigma_{11} \approx \mathbf{24.9\,\sigma_{11}}$.

The lesson is the constant, not the arithmetic: this theoretical bound is wildly pessimistic — a factor of ~25 rather than the ~2 the professor's illustrative $\epsilon = 1$ suggests. In practice randomized SVD performs far better than this worst-case guarantee. Exam-wise, know the form of $\epsilon$ (how $p$ and $\delta$ enter) rather than trusting a memorised number.

B is false: spectral clustering still needs $k$ — you choose how many eigenvectors to keep, and you still run k-means at the end. It fixes the shape limitation, not the model-selection problem.

All of A, C, D are the same fact in three costumes: Euclidean proximity is the wrong similarity; graph connectivity is the right one.

That is the course in one line, and the same three-beat pattern each time: exact is too expensive → randomize → concentrate. The concentration inequalities of Week 1 are the shared engine; the union bound is what upgrades a per-item guarantee into an all-items-at-once guarantee.

And the loop closes: JL (Week 1) is the tool used to compute effective resistances quickly (Week 6), which is what makes sparsification — and hence spectral clustering at scale — practical.