\documentclass[11pt]{article}
\usepackage{fullpage}
\usepackage{amsmath, amsfonts,graphicx}
\begin{document}
\begin{center} \Large
{\scshape 6.851 Advanced Data Structures (Spring'10)} \\[1ex]
{Prof.~Erik Demaine \qquad Dr.\ Andr\'e Schulz \qquad TA: Aleksandar Zlateski} \\[2ex]
\framebox{Problem 8} \quad {\em Due: Thursday, Apr.\ 8}
\end{center}
Be sure to read the instructions on the assignments section of the
class web page.
\paragraph{\boldmath Cuckoo Hashing.}
We pick two hash-functions $f,g\colon [u]\to[m]$ uniformly at random. Let $S$ be the set of keys we want to store by cuckoo hashing. We define the \emph{cuckoo graph} as done in the lecture: its nodes are the cells of the table, and we have an edge $(f(x),g(x))$, for all $x\in S$. Assume further, that the size of the table is $m=6|S|$.\\
Show that with probability at least $1/2$ the cuckoo graph contains no cycle. \\
\emph{Hint:} Use the analysis by counting (similar to the ``2-cycle case'' in the cuckoo hashing analysis).
\paragraph{\boldmath Conditional Expetations.}
Let $G$ be a simple graph with vertex set $V$ and edge set $E$. A cut of a set of vertices $V'\subseteq V$ is the number of edges that have one endpoint in $V'$ and the other in $V\setminus V'$.
The NP-complete \texttt{MaxCut} problem asks for the largest cut. \\
A simple randomized approximation problem works as follows: Throw for every vertex a coin. If we got ``tails'' we add it to $V'$ otherwise not. In the end an edge is with probability $1/2$ in the cut, so the expected value of the cut for $V'$ is $|E|/2$. Since every cut is at most $|E|$ we have a 2-approximation.\\
Use the concept of conditional expectations to de-randomize this algorithm.
\end{document}