Algorithms for Data Science · Quiz 2 · Sep 2025

**1. Use orthogonality:** A square orthogonal matrix satisfies \(Q^TQ=QQ^T=I\), so both Q and its transpose preserve Euclidean norms exactly. **2. Apply this after M:** For every pair covered by M’s approximate-isometry guarantee, \(\|QM(x-y)\|=\|M(x-y)\|\). Thus pre-multiplying by Q leaves M’s distortion unchanged. **3. Repeat for the transpose:** Likewise \(\|Q^TM(x-y)\|=\|M(x-y)\|\). Both maps retain the same approximate-isometry guarantee on the same set. **Answer: A, B — Both QM and QᵀM are approximate isometries.** A: **Correct:** Q preserves the norm of each already projected difference, so QM retains the guarantee. B: **Correct:** Qᵀ is also orthogonal and therefore also preserves the projected norms. C: **Incorrect:** Both qualify, rather than exactly one. D: **Incorrect:** Neither additional orthogonal transformation changes the existing distortion, so rejecting both is incorrect.

**1. Describe a Datar-hash bucket:** For \(h(x)=\lfloor(a^Tx+b)/w\rfloor\), one bucket is a slab between two parallel hyperplanes. If two points have the same hash, their connecting line segment remains in that convex slab. A compound bucket is an intersection of such slabs and is also convex. **2. Apply convexity:** Since \(x_3=\lambda x_1+(1-\lambda)x_2\), with \(0<\lambda<1\), x₃ shares the compound bucket with x₁ and x₂. Extrapolating with arbitrary real β can leave the slab. **3. Simplify the third expression:** \(x_3+(1-\lambda)x_1+\lambda x_2=x_1+x_2\). These are identical vectors, so their hashes coincide without needing a geometric assumption. **4. Simplify the fourth expression:** \(x_3-\tfrac\lambda2x_1+\tfrac\lambda2x_2=\tfrac\lambda2x_1+(1-\tfrac\lambda2)x_2\). This is another convex combination of x₁ and x₂, so it remains in their bucket. **Answer: A, C, D — A, C and D — convex bucket membership and an exact vector identity.** A: **Correct:** A convex combination of two points in the same Datar compound bucket stays inside that bucket. B: **Incorrect:** Arbitrary real β allows extrapolation beyond the segment, which can cross a bucket boundary. C: **Correct:** The two displayed vectors simplify to exactly the same x₁+x₂ and must hash identically. D: **Correct:** The expression is a convex combination with coefficient λ/2 between zero and one, so it shares the original bucket.

**1. Check nonnegativity:** X and Y are nonnegative, so \(Z=X+Y\) is nonnegative. Linearity of expectation gives \(\mathbb E[Z]=10+20=30\), without requiring independence. **2. Apply Markov’s inequality:** \[P(Z\ge60)\le\frac{\mathbb E[Z]}{60}=\frac{30}{60}=0.5.\] **3. Check sharpness:** Let \((X,Y)=(20,40)\) with probability one-half and \((0,0)\) otherwise. The specified expectations hold and \(P(Z\ge60)=1/2\). Thus 0.5 is attainable and no smaller universal upper bound follows. **Answer: 0.5.**

**1. Compute one row’s variance:** Each row of R has independent standard-normal entries. Its dot product with fixed u has mean zero and variance \(\|u\|^2=10^2=100\). **2. Include the normalization:** Since \(A=R/5\), each component of Au has variance \(100/25=4\), and therefore squared expectation four. **3. Sum 25 components:** \(\mathbb E\|Au\|^2=25(4)=100\). The normalization \(1/5=1/\sqrt{25}\) preserves squared norm in expectation. **Answer: 100.**

**1. Express one sampled edge contribution:** If edge e has weight \(w_e\) and retention probability \(p_e>0\), its sampled weight is \(I_ew_e/p_e\), where \(I_e\) is a Bernoulli indicator. **2. Take expectation:** \(\mathbb E[I_ew_e/p_e]=p_ew_e/p_e=w_e\). Summing edge Laplacian contributions gives \(\mathbb E[L_H]=L_G\); independence between edges is not needed for this expectation identity. **3. Apply the fixed vector:** \[\mathbb E[f^T(L_H-L_G)f]=f^T(\mathbb E[L_H]-L_G)f=0.\] A sampled graph may have nonzero error; only its expected signed quadratic error is zero. **Answer: 0.** **Convention note:** Positive-weight original edges require positive retention probabilities for the specified inverse-probability reweighting to be defined.

**1. Identify Euclidean locality:** Euclidean distance depends on actual displacement in both coordinate directions. A useful bucket should restrict the spread of points in both directions. **2. Inspect the partitions:** Partition C intersects crossing strips into small bounded cells. By contrast, B groups points by direction, while the nested shells in A and D can contain points far apart around their circumference. **3. Select the best match:** Sharing one of C’s small cells most directly suggests small Euclidean separation. This is the qualitative comparison requested by the diagram rather than a quantified LSH probability theorem. **Answer: C — Partition C.** A: **Incorrect:** Points on opposite sides of one elliptical shell can be far apart in Euclidean distance. B: **Incorrect:** A ray sector can contain points at very different radii and therefore far apart. C: **Correct:** The intersecting strips create spatially localized cells that bound variation in both directions. D: **Incorrect:** A square shell can include distant points on opposite sides of the origin.

**1. Identify angular similarity:** For nonzero vectors, cosine similarity is \(x^Ty/(\|x\|\|y\|)=\cos\theta\). It depends on direction rather than radius. **2. Inspect the radial partition:** Partition B divides the plane into sectors bounded by rays from the origin. Points in a sufficiently narrow sector point in similar directions even when their lengths differ greatly. **3. Compare other cells:** Spatially close cells or equal-radius shells do not directly enforce the same angular grouping. B is the intended directional partition. **Answer: B — Partition B.** **Convention note:** Cosine similarity is undefined for the zero vector. The intended comparison concerns nonzero vectors; actual within-sector similarity depends on the sector’s angular width. A: **Incorrect:** An elliptical shell can include opposite directions, whose cosine similarity is low. B: **Correct:** Angular sectors group vectors by direction, matching cosine similarity. C: **Incorrect:** The grid primarily groups by spatial proximity rather than directly by angle from the origin. D: **Incorrect:** A square shell includes many different directions and does not enforce high cosine similarity.

**1. Count observations rather than unique vectors:** The dataset repeats five orthonormal vectors 12,9,2,1 and 1 times. Each repetition contributes a separate row to the data matrix. **2. Add the multiplicities:** \(n=12+9+2+1+1=25\). **3. State the matrix dimensions:** Since each vector lies in \(\mathbb R^{10}\), D has shape 25×10. Five is its number of distinct row vectors, not its number of rows. **Answer: 25.**

**1. Form the Gram matrix:** Repeating each orthonormal row vector \(v_j^T\) exactly \(i_j\) times gives \(D^TD=\sum_{j=1}^5i_jv_jv_j^T\). Thus each \(v_j\) has eigenvalue \(i_j\). **2. Find all eigenvalues:** The five nonzero eigenvalues are 12,9,2,1,1. The remaining five dimensions in \(\mathbb R^{10}\) are orthogonal to the row span and have eigenvalue zero. **3. Take square roots:** Singular values are \(\sqrt{12},3,\sqrt2,1,1\), together with five zeros. Therefore the offered values 0,1 and 3 occur, while 12 is an eigenvalue of the Gram matrix rather than a singular value of D. **Answer: A, B, C — 0; 1; 3.** A: **Correct:** D has rank five but ten singular-value positions, so zero occurs. B: **Correct:** The Gram eigenvalues one yield singular values one. C: **Correct:** The Gram eigenvalue nine yields singular value three. D: **Incorrect:** Twelve is a squared singular value here; the associated singular value is √12.

**1. Identify the leading direction:** The largest multiplicity is 12, so the top right singular vector of D is \(v_1\), up to sign. With \(k=1,p=0\), only one sample column is used. **2. Interpret the one-hot sampling matrix:** A uniformly selected one-hot column W chooses one of D’s 25 rows. Consequently \(Z_1=D^TW\) is one of the five row directions. **3. Count successful selections:** Because the directions are orthonormal, a single sampled vector spans \(v_1\) exactly only if it is one of its 12 copies. The probability is \(12/25=0.48\). **Answer: 0.48.** **Convention note:** As intended by the sampling construction and scoring key, each one-hot column is selected uniformly from the 25 rows. A one-hot constraint alone, without a distribution on its location, would not determine this probability.

**1. Determine the sample count:** The randomized matrix has \(l=k+p=1+3=4\) one-hot columns. Each uniformly samples one of 25 observations, independently with replacement. **2. Characterize success:** The sampled span contains \(v_1\) exactly if at least one column selects one of its 12 copies. Other orthonormal row directions cannot combine to produce \(v_1\) without such a sample. **3. Use the complementary event:** Each draw misses \(v_1\) with probability \(13/25\). All four miss with probability \((13/25)^4\), so success has probability \(1-(13/25)^4=0.92688384\). **4. Round:** Correct to two decimal places, the result is 0.93. **Answer: 0.93.** **Convention note:** This uses the intended independent uniform one-hot-column sampling with replacement. Sampling without replacement would produce a different probability.

**1. Write the additional iteration:** The initial sampled matrix is \(Z_l^{(1)}=D^TW\). The second is \(Z_l^{(2)}=D^TDZ_l^{(1)}\), because \(W_l^{(2)}=DZ_l^{(1)}\). **2. Apply it to each sampled direction:** A column initially equal to \(v_j\) becomes \(D^TDv_j=i_jv_j\). Since all five multiplicities are positive, this rescales existing directions but adds none and removes none. **3. Preserve the success event:** The leading direction is present after the extra iteration if and only if it was sampled initially. With four independent draws, that probability remains \(1-(13/25)^4=0.92688384\). **4. Round and interpret:** The answer is 0.93. Power iteration can emphasize strong components, but in this exact orthonormal-row sampling example it cannot recover a direction never sampled. **Answer: 0.93.** **Convention note:** This zero-mark academic question is still solved. The calculation uses the same independent uniform sampling convention as the preceding questions.

**1. Identify the cut sides:** \(A=\{1,2,3\}\), so \(V\setminus A=\{4\}\). Only edges with exactly one endpoint at vertex four cross the cut. **2. Read the crossing weights:** The edges to vertex four have weights \(w_{14}=10\), \(w_{24}=2\), and \(w_{34}=1\). The edges 1–2 and 1–3 lie entirely within A. **3. Add each undirected edge once:** \(\operatorname{cut}(A,V\setminus A)=10+2+1=13\). Counting both matrix entries of each undirected edge would incorrectly double the cut. **Answer: 13.**