Algorithms for Data Science Quiz 2: 3 August 2025 (May 2025 term)

Consider a dataset for an unsupervised learning problem consisting of $n$ points in $\mathbb{R}^d$, where all the points lie on the unit hypersphere. Using the JL lemma, let $f$ be a linear map from $\mathbb{R}^d \to \mathbb{R}^k$ for $\epsilon = 0.0201$ and a suitable choice of $k$ as mandated by the lemma. Find an upper bound for the distance between any two points of the dataset in the lower dimensional space $\mathbb{R}^k$. Your answer should have exactly two places after the decimal point

Hints

• A hypersphere in $\mathbb{R}^d$ is the set of points with $||x|| = 1$, where $x \in \mathbb{R}^d$.
• The triangle inequality states that the sum of the lengths of two sides of a triangle is greater than the length of the third side.

Consider the following weighted, undirected graph. If an edge is not present in the graph, the corresponding weight is zero.

Based on the above data, answer the given subquestions.

Consider the following weighted, undirected graph. If an edge is not present in the graph, the corresponding weight is zero.

Based on the above data, answer the given subquestions.

Find the Laplacian, L, of the graph.

Consider the following weighted, undirected graph. If an edge is not present in the graph, the corresponding weight is zero.

Based on the above data, answer the given subquestions.

How many zero eigenvalues does L have?