da5003_2026T2_Q2_NA.pdf

Algorithms for Data Science · Quiz 2 · May 2026

Questions and published explanations below are available without starting a test. Some questions may not have a published solution yet.

Question 2 MCQ · 2.0 marks

Consider an LSH setup with [[IMAGE:f9837cbe66574f15_2_2]] tables and [[IMAGE:f9837cbe66574f15_2_3]] hash functions per table with the usual definition of collision. [[IMAGE:f9837cbe66574f15_2_4]] Consider four points [[IMAGE:f9837cbe66574f15_2_5]] . The following is observed: [[IMAGE:f9837cbe66574f15_2_6]] Which of the following is true given the above information?

The only collision is between [[IMAGE:f9837cbe66574f15_2_7]] and [[IMAGE:f9837cbe66574f15_2_8]]
The only collision is between [[IMAGE:f9837cbe66574f15_2_9]] and [[IMAGE:f9837cbe66574f15_2_10]] .
There are at least two collisions, one between [[IMAGE:f9837cbe66574f15_2_11]] and [[IMAGE:f9837cbe66574f15_2_12]] and the other between [[IMAGE:f9837cbe66574f15_2_13]] and [[IMAGE:f9837cbe66574f15_2_14]] .
There are no collisions.

A published solution is not available for this question yet.

Question 3 MCQ · 3.0 marks

[[IMAGE:f9837cbe66574f15_3_15]] Let . Consider a random vector [[IMAGE:f9837cbe66574f15_3_16]] . Find the covariance matrix of [[IMAGE:f9837cbe66574f15_3_17]] .

[[IMAGE:f9837cbe66574f15_3_18]]
[[IMAGE:f9837cbe66574f15_3_19]]
[[IMAGE:f9837cbe66574f15_3_20]]
[[IMAGE:f9837cbe66574f15_3_21]]

A published solution is not available for this question yet.

Question 4 MCQ · 3.0 marks

When computing an [[IMAGE:f9837cbe66574f15_3_22]] -spectral sparsification of a graph [[IMAGE:f9837cbe66574f15_3_23]] , the edge [[IMAGE:f9837cbe66574f15_3_24]] is retained with probability [[IMAGE:f9837cbe66574f15_3_25]] . [[IMAGE:f9837cbe66574f15_3_26]] denotes the vector with one at index [[IMAGE:f9837cbe66574f15_3_27]] and zero everywhere else. [[IMAGE:f9837cbe66574f15_3_28]] is the Laplacian of the graph and [[IMAGE:f9837cbe66574f15_3_29]] is its pseudoinverse. Which of the following is true?

[[IMAGE:f9837cbe66574f15_3_30]]
[[IMAGE:f9837cbe66574f15_3_31]]
[[IMAGE:f9837cbe66574f15_4_32]]
[[IMAGE:f9837cbe66574f15_4_33]]

A published solution is not available for this question yet.

Question 5 MCQ · 3.0 marks

You are given a subset of the singular values of a large matrix [[IMAGE:f9837cbe66574f15_4_34]] : [[IMAGE:f9837cbe66574f15_4_35]] . You don't know the dimensions of the matrix. If the best rank- [[IMAGE:f9837cbe66574f15_4_36]] approximation of the matrix is [[IMAGE:f9837cbe66574f15_4_37]] , which of the following is true? [[IMAGE:f9837cbe66574f15_4_38]] is the spectral norm.

[[IMAGE:f9837cbe66574f15_4_39]]
[[IMAGE:f9837cbe66574f15_4_40]]
[[IMAGE:f9837cbe66574f15_4_41]]
[[IMAGE:f9837cbe66574f15_4_42]]

A published solution is not available for this question yet.

Question 6 MSQ · 3.0 marks

In the context of LSH, consider a setup with [[IMAGE:f9837cbe66574f15_4_43]] tables and [[IMAGE:f9837cbe66574f15_4_44]] functions per table. If you want to make the collisions between points harder, that is, make it harder for two points to collide, which of these steps would you take? One or more options could be correct.

Increase the value of [[IMAGE:f9837cbe66574f15_4_45]] while keeping [[IMAGE:f9837cbe66574f15_4_46]] fixed
Decrease the value of [[IMAGE:f9837cbe66574f15_4_47]] while keeping [[IMAGE:f9837cbe66574f15_4_48]] fixed
Increase the value of [[IMAGE:f9837cbe66574f15_5_49]] while keeping [[IMAGE:f9837cbe66574f15_5_50]] fixed
Decrease the value of [[IMAGE:f9837cbe66574f15_5_51]] while keeping [[IMAGE:f9837cbe66574f15_5_52]] fixed

A published solution is not available for this question yet.

Question 7 MSQ · 3.0 marks

Consider an [[IMAGE:f9837cbe66574f15_5_53]] matrix [[IMAGE:f9837cbe66574f15_5_54]] . Let [[IMAGE:f9837cbe66574f15_5_55]] be a [[IMAGE:f9837cbe66574f15_5_56]] matrix whose [[IMAGE:f9837cbe66574f15_5_57]] columns are the top- [[IMAGE:f9837cbe66574f15_5_58]] left singular vectors. Let [[IMAGE:f9837cbe66574f15_5_59]] be a random matrix of shape [[IMAGE:f9837cbe66574f15_5_60]] , where each entry is sampled from [[IMAGE:f9837cbe66574f15_5_61]] . Let [[IMAGE:f9837cbe66574f15_5_62]] be the [[IMAGE:f9837cbe66574f15_5_63]] matrix whose columns form an orthonormal basis for the columns of [[IMAGE:f9837cbe66574f15_5_64]] . Which of the following is/are true? Assume that the singular values of [[IMAGE:f9837cbe66574f15_5_65]] decay rapidly.

[[IMAGE:f9837cbe66574f15_5_66]] is the best rank- [[IMAGE:f9837cbe66574f15_5_67]] approximation of [[IMAGE:f9837cbe66574f15_5_68]]
[[IMAGE:f9837cbe66574f15_5_69]]
[[IMAGE:f9837cbe66574f15_5_70]] is the best rank- [[IMAGE:f9837cbe66574f15_5_71]] approximation of [[IMAGE:f9837cbe66574f15_5_72]]
[[IMAGE:f9837cbe66574f15_5_73]] with a high probability.

A published solution is not available for this question yet.

Question 8 NAT · 3.0 marks

Consider a continuous random variable [[IMAGE:f9837cbe66574f15_5_74]] with [[IMAGE:f9837cbe66574f15_5_75]] . Find the tightest lower bound for [[IMAGE:f9837cbe66574f15_5_76]] with the given information using Markov's inequality. Enter your answer correct to one decimal place.

A published solution is not available for this question yet.

Question 9 MCQ · 2.0 marks

Let [[IMAGE:f9837cbe66574f15_6_77]] be a [[IMAGE:f9837cbe66574f15_6_78]] random matrix whose entries are i.i.d standard normal random variables. Let [[IMAGE:f9837cbe66574f15_6_79]] be a fixed vector with [[IMAGE:f9837cbe66574f15_6_80]] . Based on the above data, answer the given subquestions.

Which of the following is a scalar random variable?

[[IMAGE:f9837cbe66574f15_6_81]]
[[IMAGE:f9837cbe66574f15_6_82]]
[[IMAGE:f9837cbe66574f15_6_83]]

A published solution is not available for this question yet.

Question 10 NAT · 3.0 marks

What is [[IMAGE:f9837cbe66574f15_6_84]] ?

A published solution is not available for this question yet.

Question 11 NAT · 3.0 marks

The **diameter** of a dataset [[IMAGE:f9837cbe66574f15_7_85]] with a finite number of points, denoted as [[IMAGE:f9837cbe66574f15_7_86]] , is defined as the Euclidean distance of that pair of points with the maximum separation between them. Formally: [[IMAGE:f9837cbe66574f15_7_87]] Next, consider a dataset [[IMAGE:f9837cbe66574f15_7_88]] of [[IMAGE:f9837cbe66574f15_7_89]] data-points in [[IMAGE:f9837cbe66574f15_7_90]] . Let [[IMAGE:f9837cbe66574f15_7_91]] be a linear [[IMAGE:f9837cbe66574f15_7_92]] -isometry as guaranteed by the JL-lemma for [[IMAGE:f9837cbe66574f15_7_93]] and [[IMAGE:f9837cbe66574f15_7_94]] . Define [[IMAGE:f9837cbe66574f15_7_95]] . Based on the above data, answer the given subquestions.

If [[IMAGE:f9837cbe66574f15_7_96]] , find the tightest upper bound for [[IMAGE:f9837cbe66574f15_7_97]] with the available information. Enter your answer correct to one decimal place. Use the version of JL-Lemma that involves squared distances.

A published solution is not available for this question yet.

Question 12 MCQ · 2.0 marks

Call the upper bound found in the previous subquestion [[IMAGE:f9837cbe66574f15_7_98]] . Let [[IMAGE:f9837cbe66574f15_7_99]] be two points, not necessarily in the dataset, such that [[IMAGE:f9837cbe66574f15_7_100]] . Is the inequality given below true or false? [[IMAGE:f9837cbe66574f15_8_101]]

True
False

A published solution is not available for this question yet.

Question 13 NAT · 3.0 marks

The contours of a hash function [[IMAGE:f9837cbe66574f15_8_102]] sampled from the Datar-hash family [[IMAGE:f9837cbe66574f15_8_103]] with [[IMAGE:f9837cbe66574f15_8_104]] , where [[IMAGE:f9837cbe66574f15_8_105]] and [[IMAGE:f9837cbe66574f15_8_106]] , are shown in the plot below. The red numbers denote the value the function takes on the dotted line immediately to their right. In other words, [[IMAGE:f9837cbe66574f15_8_107]] on the dotted line passing through [[IMAGE:f9837cbe66574f15_8_108]] and [[IMAGE:f9837cbe66574f15_8_109]] on the dotted line passing through [[IMAGE:f9837cbe66574f15_8_110]] . Note that [[IMAGE:f9837cbe66574f15_8_111]] and [[IMAGE:f9837cbe66574f15_8_112]] are realizations of random variables. [[IMAGE:f9837cbe66574f15_8_113]] Based on the above data, answer the given subquestions.

Find [[IMAGE:f9837cbe66574f15_8_114]] .

A published solution is not available for this question yet.

Question 14 NAT · 2.0 marks

Let [[IMAGE:f9837cbe66574f15_9_115]] be the set of all points inside the rectangle with corners [[IMAGE:f9837cbe66574f15_9_116]] , [[IMAGE:f9837cbe66574f15_9_117]] , [[IMAGE:f9837cbe66574f15_9_118]] , [[IMAGE:f9837cbe66574f15_9_119]] that are hashed to the value [[IMAGE:f9837cbe66574f15_9_120]] . Find the area of the region corresponding to [[IMAGE:f9837cbe66574f15_9_121]] correct to one decimal place.

A published solution is not available for this question yet.

Question 15 NAT · 3.0 marks

Consider a dataset with three data-points that are located on the vertices of an equilateral triangle with side length [[IMAGE:f9837cbe66574f15_9_122]] . Instantiate a weighted graph on this dataset with the weighting function [[IMAGE:f9837cbe66574f15_9_123]] with [[IMAGE:f9837cbe66574f15_9_124]] . Do not include an edge from a data-point to itself. **Useful hints** 1. All sides of an equilateral triangle have the same length. [[IMAGE:f9837cbe66574f15_9_126]] 2. [[IMAGE:f9837cbe66574f15_9_125]] is an eigenvalue of the matrix and it repeats twice. Based on the above data, answer the given subquestions.

Compute the Laplacian [[IMAGE:f9837cbe66574f15_10_127]] . If the [[IMAGE:f9837cbe66574f15_10_128]] denotes the entry in [[IMAGE:f9837cbe66574f15_10_129]] row and [[IMAGE:f9837cbe66574f15_10_130]] column, with [[IMAGE:f9837cbe66574f15_10_131]] , enter the value of [[IMAGE:f9837cbe66574f15_10_132]] . Enter your answer correct to one decimal place.