\documentclass[11pt]{article}\pagestyle{empty}
\usepackage{amsmath,amssymb,amsthm,color,graphicx}
\usepackage{euscript}
\usepackage{mathpazo}

\usepackage[top=1.5in,bottom=1.5in,left=1.25in,right=1.25in]{geometry}
%improve trypography

\usepackage{microtype}
\usepackage{fixltx2e}
\usepackage{fullpage}
\usepackage{xspace}
\usepackage{tikz}
\usepackage{enumitem}
\usepackage{mathtools}

{\catcode`\@=11
\gdef\setft#1#2#3{%
\def\@oddfoot{%
{\setbox0=\hbox{#1}%
\setbox1=\hbox{#3}%
\ifdim\wd0>\wd1%
\dimen0=\wd0%
\box0\hfil#2\hfil\hbox to\dimen0{\hfil\hfil\box1}%
\else \dimen0=\wd1%
\hbox to\dimen0{\box0\hfil}\hfil#2\hfil\box1\fi%
}}}}

{\catcode`\@=11
\gdef\sethd#1#2#3{%
\def\@oddhead{\vbox{\hbox to\hsize{{#1}\hfil{#2}\hfil{#3}}%
\vspace{0.06in}%
\hbox to \hsize{\hrulefill}\vspace*{-0.09in}}}
\def\@evenhead{\@oddhead}
	}
}

\def\reals{\mathbb{R}}
\def\sphere{\mathbb{S}}
\def\xx{\mathbf{x}}
\def\norm#1{\Vert #1 \Vert}
\def\hint#1{(\textbf{Hint:} #1)}
\def\floor#1{\lfloor #1 \rfloor}
\def\ceiling#1{\lceil #1 \rceil}

\DeclareMathOperator*{\argmin}{arg\,min}
\DeclareMathOperator*{\pr}{Pr}


\marginparsep=1pt
\oddsidemargin=0.25in
%
%%%%%% A few macros %%%%%%%%%%%%%%%%
\newtheorem{probm}{Problem}
\newenvironment{prob}{\noindent{\bf Problem \addtocounter{probm}{1}
\hspace{-1mm}\theprobm:\hspace{2mm}}}{\vspace{2mm}}

\def\hint#1{\noindent ({\bf Hint:} {\it #1})}
\def\eps{\varepsilon}
\def\conv{\mathop{\mathrm{conv}}}

\parskip=2mm
\sethd{{\sc Assignment 8}}{}{{\sc Course: COMPSCI531D}}
\setft{{\sc Fall 2021}}{{\sc Introduction to Algorithms}}{{\sc Page \thepage}}

\begin{document}
\vspace*{2mm}

\noindent\textbf{Due Date: November 20, 11:59pm}

% \noindent In all problems, prove the correctness of your algorithm and analyze its running time.



\begin{prob}[10pts]
Given a ground set $U = \{e_1, e_2, \dots, e_n\}$, a collection of sets $\mathcal S = \{S_1, S_2, \dots, S_m\}$ where each $S_j\subseteq U$ and $\bigcup_{j=1}^m S_j = U$, and a weight function $w: S_j \rightarrow \reals^+$, we want to find a set cover $\mathcal C\subseteq \mathcal S$ such that $\bigcup_{S_j \in \mathcal C}S_j = U$ and the total weight of sets in $\mathcal C$ is minimized. Below is a linear program relaxation for the problem. 
\begin{alignat*}{3}
	& \min & \sum_{j=1}^m w(S_j)\cdot x_j& \\
	& \text{subject to} & \sum_{e_i \in S_j} x_{j}& \ge 1 \quad \text{for } 1&\le i \le n\\
	&& x_{j} &\ge 0 \quad \text{for } 1&\le j \le m.
\end{alignat*}
Let $f$ be the maximum number of sets in $\mathcal S$ in which an element of $U$ appears. Consider the algorithm for this problem that first computes an optimal 
fractional solution $x^*$ then returns $\{ S_j \mid x^*_j \ge 1/f\}$. Prove this algorithm returns a feasible solution and prove the best approximation 
guarantee for it that you can.
\end{prob}

\begin{prob}[10pts]
	Let $G$ be an undirected cycle with $n$ vertices. Write the Laplacian matrix of $G$. Prove that its eigenvalues and eigenvectors are 
	\[ \lambda_k = 2-2\cos \left(2\pi \frac{k}{n}\right) \quad \mbox{and} \quad u_k = \begin{bmatrix} \cos\left(0\pi \frac{k}{n}\right)\\
	\cos\left(2\pi \frac{k}{n}\right)\\ 
	\cos\left(4\pi \frac{k}{n}\right) \\ 
	\dots \\ 
	\cos\left(2(n-1)\pi \frac{k}{n}\right) 
	\end{bmatrix} \]
	respectively, for $0 \le k \le n-1$.
\end{prob}

\begin{prob}[10pts]
	Let $\mathcal U$ be the universe of items to be hashed, and $m$ be the size of the hash table.
	A family $\mathcal H$ of hash functions is \emph{uniform} if choosing a hash function uniformly at random from $\mathcal H$ makes every hash value equally likely for every item in the universe:
	\[ \pr_{h\in \mathcal H}[h(x) = i] = \frac{1}{m} \quad\text{for all $x\in \mathcal U$ and all $i\in [m]$},
		\]
	and \emph{near-uniform} if the probability is bounded by at most $2/m$. 
	A family $\mathcal H$ of hash functions is \emph{universal} if, for any two items in the universe, the probability of collision is as small as possible, i.e.
	\[ \pr_{h\in \mathcal H}[h(x) = h(y)\mid x\ne y] \le \frac{1}{m},
	\]
	and \emph{near-universal} if the probability of collision is at most $2/m$. 
	
	\begin{enumerate}[label=(\alph*)]
		\item {[5pts]} Describe a set of hash functions that is uniform but not (near-)universal. 
		\item {[5pts]} Describe a set of hash functions that is universal but not (near-)uniform.
	\end{enumerate}
\end{prob}





\end{document}
