Algorithms for Data Science · Quiz 2 · May 2026

**1. Apply the two levels of collision:** Within each table, both hash functions must agree for a pair to share the compound bucket. Across the two tables, agreement in at least one table is enough to count as an LSH collision. **2. Check the first specified pair:** The pair \((x_1,y_1)\) agrees on both functions in table 1, so it collides. Its disagreement in table 2 does not undo that table-1 collision. **3. Check the second specified pair:** The pair \((x_2,y_2)\) agrees on both hash functions in both tables, so it also collides. These are at least two distinct colliding pairs; the information does not exclude additional cross-pair collisions. **Answer: C — At least two colliding pairs: (x₁,y₁) and (x₂,y₂).** A: **Incorrect:** The second specified pair also collides, so the first pair cannot be the only collision. B: **Incorrect:** The first specified pair already collides in table 1, so the second pair is not the only collision. C: **Correct:** Both named pairs collide in at least one complete table; other pairs are not ruled out. D: **Incorrect:** The supplied equalities establish at least two colliding pairs.

**1. Transform the covariance:** For a fixed matrix A, \(\operatorname{Cov}(A\omega)=A\operatorname{Cov}(\omega)A^T\). Since \(\omega\sim\mathcal N(0,I_3)\), this reduces to \(AA^T\). **2. Calculate diagonal entries:** The rows of A are \((1,1,2),(1,0,1),(0,1,1)\). Their squared lengths are \(1+1+4=6\), \(1+0+1=2\), and \(0+1+1=2\). **3. Calculate off-diagonal entries:** Row dot products give \(1+0+2=3\), \(0+1+2=3\), and \(0+0+1=1\). Covariance is symmetric. **4. Assemble the result:** \[\operatorname{Cov}(A\omega)=\begin{bmatrix}6&3&3\\3&2&1\\3&1&2\end{bmatrix}.\] **Answer: B — Covariance matrix with rows (6,3,3), (3,2,1), (3,1,2).** A: **Incorrect:** This is AᵀA, formed from column dot products, rather than AAᵀ required for the covariance of Aω. B: **Correct:** It matches the row-wise dot products in AAᵀ, including variances 6,2,2. C: **Incorrect:** Its diagonal and cross-covariance values do not match AAᵀ. D: **Incorrect:** The identity is the covariance of ω; multiplication by this non-orthogonal A changes it.

**1. Use the best-rank approximation theorem:** In spectral norm, the error of a best rank-at-most-three approximation is the fourth largest singular value: \(\|M-B\|_2=\sigma_4(M)\). **2. Sort the known subset:** The given singular values in decreasing order are 1000,10,8,5,3,0. Even if there are unknown singular values, at least four singular values are at least five. **3. Derive the guaranteed bound:** Therefore the fourth largest singular value among all values satisfies \(\sigma_4(M)\ge5\). Unknown values could push it above five, so the exact error cannot be fixed from the subset. **Answer: B — The best rank-3 spectral-norm error is at least 5.** A: **Incorrect:** Equality would follow if these were all relevant singular values, but unreported larger ones can make the error exceed five. B: **Correct:** At least four singular values are at least five, guaranteeing that the fourth largest and the optimal error are at least five. C: **Incorrect:** Unknown singular values can make the fourth largest exceed five, so this upper bound is not guaranteed. D: **Incorrect:** Eight is not forced; if the displayed list were complete, the fourth largest would be five.

**1. Write the amplification probability:** If one basic hash function has pair-collision probability p, then k independent functions agree in a table with probability \(p^k\). With L independent tables, the probability of at least one table collision is \(1-(1-p^k)^L\). **2. Change the table count:** With k fixed and \(0<p<1\), increasing L gives more opportunities to collide and raises the probability. Decreasing L makes a collision harder. **3. Change the functions per table:** With L fixed, increasing k lowers \(p^k\), because more simultaneous agreements are required. Decreasing k makes the within-table condition easier. **Answer: B, C — Decrease L or increase k.** **Convention note:** The probability formula assumes the usual independent hash construction. At degenerate basic collision probabilities zero or one, a change may leave the probability unchanged rather than strictly reducing it. A: **Incorrect:** More tables provide more chances for a collision and therefore make collisions easier. B: **Correct:** Fewer tables reduce the opportunities for at least one compound-hash match. C: **Correct:** More hash functions in a table require more simultaneous matches, reducing collision probability. D: **Incorrect:** Fewer functions relax the within-table condition and make collisions easier.

**1. Identify the exact SVD projection:** If \(A=U\Sigma V^T\), projecting onto its top-k left singular vectors gives \(U_kU_k^TA=U_k\Sigma_kV_k^T\). This is the truncated SVD and is a best rank-at-most-k approximation. **2. Explain the randomized range finder:** Multiplying by a Gaussian matrix \(\Omega\) forms random combinations of A’s columns. Large singular-value directions contribute more strongly to \(A\Omega\); with rapid decay and adequate separation, its orthonormal basis Q is likely to approximate the dominant subspace. **3. Distinguish approximation from equality:** The projector \(QQ^T\) generally differs from \(U_kU_k^T\) when a nonzero singular-value tail remains. Thus \(QQ^TA\) is a randomized approximation rather than automatically the exact optimum. **4. Interpret the probabilistic statement:** Under the course’s rapid-decay interpretation, D is the intended approximate relation. Its quality depends on the decay, the gap at k and the random sample; an exact equality or an unspecified universal accuracy guarantee does not follow. **Answer: A, D — A and D under the stated rapid-decay approximation.** **Convention note:** The symbol ≈ has no specified tolerance here, and “rapidly” supplies no numerical gap or failure probability. A rigorous high-probability bound needs quantitative conditions; oversampling or power iterations are standard ways to strengthen it. If rank(A)=k and the Gaussian sample spans its range, equality does hold with probability one. A: **Correct:** Projection onto the true top-k left singular subspace produces the optimal truncated-SVD approximation. B: **Incorrect:** A random sampled range need not equal the exact dominant subspace, so projector equality is not generally true. C: **Incorrect:** The randomized projection is generally approximate; only the exact top-k SVD projection is guaranteed to be optimal. D: **Correct:** Rapidly decaying singular values make a good approximation to the dominant subspace plausible, which is the intended probabilistic statement.

**1. Choose a nonnegative variable:** Markov’s inequality applies to \(Y=X^2\ge0\), with \(\mathbb E[Y]=0.3\). It does not require the mean of X to be zero. **2. Bound the outside event:** \(P(|X|>1)=P(X^2>1)\le\mathbb E[X^2]/1=0.3\). Continuity means the boundary points ±1 have probability zero. **3. Take the complement:** \[P(-1\le X\le1)=1-P(|X|>1)\ge1-0.3=0.7.\] **4. Explain tightness:** Distributions can concentrate nearly 0.7 of their mass near zero and nearly 0.3 just outside the interval while maintaining second moment 0.3. Thus no strictly larger uniform lower bound follows from the given moment alone; 0.7 is the sharp infimum. **Answer: 0.7.**

**1. Determine the product’s dimension:** The matrix P has shape 25×10,000 and u is a fixed 10,000-dimensional vector. Therefore Pu is a random vector with 25 components. **2. Apply the squared norm:** \(\|Pu\|^2\) sums the squares of those 25 components into one random real number. It is therefore a scalar random variable. **3. Check expectation:** \(\mathbb E[Pu]\) is a deterministic 25-dimensional zero vector, because every entry of P has zero mean. It is not the scalar random quantity being requested. **Answer: B — The squared norm ‖Pu‖².** A: **Incorrect:** Pu has 25 components, making it a random vector rather than a scalar. B: **Correct:** The squared Euclidean norm sums all components to a single random nonnegative value. C: **Incorrect:** E[Pu] is a deterministic zero vector with 25 components.

**1. Analyze one row:** Let \(Z_i=\sum_{j=1}^{10000}P_{ij}u_j\). Since u is fixed and P’s entries are independent standard normal variables, \(\mathbb E[Z_i]=0\) and \(\operatorname{Var}(Z_i)=\sum_j u_j^2=\|u\|^2=1\). **2. Obtain its squared expectation:** \(\mathbb E[Z_i^2]=\operatorname{Var}(Z_i)+(\mathbb E[Z_i])^2=1\). **3. Sum all rows:** \(\|Pu\|^2=\sum_{i=1}^{25}Z_i^2\), so \(\mathbb E\|Pu\|^2=25\). Equivalently this norm squared has a chi-square distribution with 25 degrees of freedom. **4. Check scaling:** P has unscaled standard-normal entries. If it had instead been divided by \(\sqrt{25}\), the expected squared norm would be one, but that normalization is not given. **Answer: 25.**

**1. Apply the squared-distance JL inequality:** For any two points in the given dataset, \(\|f(x)-f(y)\|^2\le(1+\epsilon)\|x-y\|^2\), with \(\epsilon=0.2\). **2. Bound every projected pair:** The original diameter is 4.2, so each original pair has squared distance at most \(4.2^2=17.64\). Every projected squared distance is therefore at most \(1.2(17.64)=21.168\). **3. Take the maximum and square root:** The same bound holds for the largest projected pair: \(D_2\le\sqrt{21.168}=4.2\sqrt{1.2}=4.60086948\ldots\). **4. Round in the requested format:** To one decimal place, the bound is 4.6. The unrounded upper bound is about 4.60087; the rounded reporting value should not be mistaken for a strictly smaller exact bound. **Answer: 4.6.**

**1. Identify the scope of JL:** The promised distortion bound holds for pairs from the specified finite dataset. The new points p and q are not required to belong to it. **2. Explain why linearity is insufficient:** A linear map can preserve distances along directions represented by the dataset while expanding an untested direction by a large factor. The finite-set guarantee does not bound its operator norm on every direction. **3. Construct a counterexample pattern:** Put all dataset points on the x-axis in three dimensions, with diameter 4.2, and take \(f(x,y,z)=(x,My)\). Dataset distances are preserved exactly. Two external points separated by at most 4.2 along the y-direction have images separated by M times their original distance, which exceeds the earlier bound when M is large. **4. Conclude:** The stated inequality is not guaranteed for arbitrary external points. A uniform bound would require an additional global norm or subspace guarantee. **Answer: B — False.** A: **Incorrect:** The finite dataset guarantee cannot be extended to every external pair solely from linearity. B: **Correct:** A map can preserve the dataset yet expand another direction, so the claimed universal inequality is false.

**1. Write the hash form:** Datar hashing uses \(h_{a,b}(x)=\lfloor(a_1x_1+a_2x_2+b)/w\rfloor\), with \(w=2\). The plotted parallel bucket boundaries have slope −1, so their normal has equal components: \(a_1=a_2=c\). **2. Use adjacent boundary labels:** The boundary through \((-3,0)\) starts bucket −1 and the next boundary through \((-1,0)\) starts bucket 0. Hence \(-3c+b=-2\) and \(-c+b=0\). Subtracting gives \(2c=2\), so \(c=1\) and \(b=1\). **3. Compute the requested quantity:** \(a=(1,1)\), so \(\|a\|^2=1^2+1^2=2\). Adding \(|b|=1\) gives \(\|a\|^2+|b|=3\). **4. Check the figure:** The inferred hash is \(\lfloor(x_1+x_2+1)/2\rfloor\). On the two marked boundaries it gives \(\lfloor-2/2\rfloor=-1\) and \(\lfloor0/2\rfloor=0\), consistent with the labels. **Answer: 3.** **Convention note:** This uses the standard intended reading of the plotted contour lines as successive bucket boundaries. Isolated samples merely known to have floor values −1 and 0, without boundary information, would not uniquely determine a and b.

**1. Reconstruct the hash:** The plotted boundaries with width two give \(a=(1,1)\), \(b=1\), hence \(h(x_1,x_2)=\lfloor(x_1+x_2+1)/2\rfloor\). **2. Translate bucket 1 into inequalities:** A floor value of one requires \(1\le(x_1+x_2+1)/2<2\), equivalently \(1\le x_1+x_2<3\). **3. Intersect with the rectangle:** Inside \(0\le x_1\le2\), \(0\le x_2\le1\), the maximum coordinate sum is three, attained only at the upper-right corner. The excluded lower region \(x_1+x_2<1\) is a right triangle with legs one and one. **4. Subtract areas:** The rectangle area is \(2(1)=2\); the lower triangle area is \(\tfrac12(1)(1)=0.5\). The requested area is \(2-0.5=1.5\). Including or excluding a boundary line or corner does not change area. **Answer: 1.5.**

**1. Evaluate a single edge weight:** All three distances equal \(\sqrt{\ln2}\), and \(\sigma=1/\sqrt2\), so \(2\sigma^2=1\). Each off-diagonal weight is \(e^{-(\ln2)/1}=1/2\). Self-edges are excluded. **2. Compute degrees:** Every vertex connects to two others with weight one-half, giving degree \(1/2+1/2=1\). Thus the degree matrix is the identity. **3. Form the unnormalized Laplacian:** With \(L=D-W\), \[L=\begin{bmatrix}1&-1/2&-1/2\\-1/2&1&-1/2\\-1/2&-1/2&1\end{bmatrix}.\] **4. Extract the requested entries:** \(L_{11}=1\) and \(L_{23}=-1/2\), so \(L_{11}-L_{23}=1-(-1/2)=1.5\). **Answer: 1.5.**

**1. Reconstruct the Laplacian:** The equilateral triangle has edge weight \(e^{-\ln2}=1/2\), since \(2\sigma^2=1\). Each degree is one, giving diagonal entries one and off-diagonal entries −1/2. **2. Write a useful matrix form:** If J is the 3×3 all-ones matrix, then \(L=\tfrac32I-\tfrac12J\). The vector \((1,1,1)\) is an eigenvector of J with eigenvalue three, so its Laplacian eigenvalue is \(3/2-(1/2)3=0\). **3. Evaluate the remaining subspace:** Any vector with coordinate sum zero satisfies \(Jv=0\), hence \(Lv=\tfrac32v\). This subspace is two-dimensional, so the other two eigenvalues are both 1.5. **4. Select the smallest nonzero value:** The spectrum is \(0,1.5,1.5\). Therefore the requested eigenvalue is 1.5. **Answer: 1.5.**