\documentclass[answers]{exam}
 
 \usepackage{graphicx}
 \usepackage{float}
 \usepackage{amsmath}
 \usepackage{amsthm}
 \usepackage{amsfonts} 
 \usepackage{mdframed}
% \usepackage{xcolor}
 \usepackage[dvipsnames]{xcolor}

 
 
\newcommand{\NP}{\mathsf{NP}}
\newcommand{\p}{\mathsf{P}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\veps}{\varepsilon}
\newtheorem{theorem}{Theorem}
 
% First, we setup the header and footer
\pagestyle{headandfoot}
\runningheadrule
\runningfootrule
\header{COL758: Advanced Algorithms (CSE, IITD, Semester-II-2022-23)}{}{Homework-3}
\footer{}{\thepage  \, of \numpages}{}
 
% We want the points for each question displayed on the left
%\pointname{points}
%\pointsinmargin
 
% Automatically total the points - make sure to compile TWICE
\addpoints
 
\begin{document}
 
%\begin{center} 
%\fbox{\parbox{5.5in}{
%\vspace{-0.1in}
%\begin{itemize}
%\item \small{You may use any of the following known $\mathsf{NP}$-complete problems to show that a given problem is $\mathsf{NP}$-complete: 3-SAT, INDEPENDENT-SET, VERTEX-COVER, SET-COVER, HAMILTONIAN- CYCLE, HAMILTONIAN-PATH, SUBSET-SUM, 3-COLORING.}
%\end{itemize}
%\vspace{-0.1in}
%}}
%\end{center}

\vspace{0.1in}


\vspace{0.1in}
% Some general text together with several questions and total points possible
There are \numquestions\, questions for a total of \numpoints\, points.
\vspace{0.1in}
\hrule
 \vspace{0.2in}
\begin{questions}
 
% First question, worth 3 points
\question[20] Given an $n \times n$ matrix $A$, use a known SVD algorithm ({\em given $A$, it outputs $n \times n$ matrices $U, V, D$ such that $A = UDV^{T}$}) to find a matrix $B$ such that $B^{T}B = I$ and the cost function $||A - B||_F$ is minimised. Discuss the correctness of your algorithm.

\begin{solution}
Write your answer here.
\end{solution}




\vspace{0.2in}



\question[20] Suppose we flip the quantifiers in the statement of the JL theorem.

\begin{quote}
(JL Flipped) For any $0 < \veps < 1$ and any integer $n$, let $k \geq \frac{3}{c \veps^2} \ln{n}$ with $c$ as in the Random Projection Theorem. The random projection $f : \R^d \rightarrow \R^k$ defined before has the property that for any set of $n$ points in $\R^d$, for all pairs of points $\mathbf{v_i}$ and $\mathbf{v_j}$, with probability at least $(1 - \frac{3}{2n})$,
\[
(1 - \veps) \sqrt{k} ||\mathbf{v_i} - \mathbf{v_j}|| \leq ||f(\mathbf{v_i}) - f(\mathbf{v_j})|| \leq (1 +\veps) \sqrt{k} ||\mathbf{v_i} - \mathbf{v_j}||.
\]
\end{quote}

Is the above statement true? Given reasons. 
%({\em \underline{Hint}: For every projection, can you construct a set of points that is bad for this projection?})



\vspace{0.2in}



\question[30] The $k$-median problem is defined as follows: Given a set $X \subset \R^d$ in $d$-dimensional Euclidean space, find a set $C \subset \R^d$ of $k$ points ({\em called centers}) such that the following cost function is minimised: 
\[
cost(X, C) \equiv \sum_{x \in X} \min_{c \in C} ||x - c||.
\]
Suppose there is an {\em approximation scheme} for the problem, which means that there is an algorithm $A$ that takes as input the instance $(X, k)$ and an error parameter $\veps > 0$ and outputs a $(1+\veps)$-approximate solution.
Suppose the running time of the algorithm $A$ is $O(nk2^{d})$, where $n = |X|$. Can you improve the dependency of the running time on the dimension using the JL theorem? In other words, you are asked to design a faster approximation scheme. Discuss.



\vspace{0.2in}



\question[30] Consider the hypothesis class of {\em Linear Threshold Functions (LTFs)} in $\R^d$. An LTF is defined using vectors $\mathbf{w}, \mathbf{b} \in \R^d$ with the label function being:
\[
f(\mathbf{x}) = 
\begin{cases}
1, & \text{if $\mathbf{w}^T \cdot \mathbf{x} + \mathbf{b} > 0$}\\
0, & \text{otherwise}
\end{cases}
\]
Show that the VC dimension of this concept class is $d+1$.





\end{questions}
\end{document}