\documentclass[12pt]{article}
\usepackage[margin=1in]{geometry} 
\usepackage{amsmath,amsthm,amssymb,amsfonts}
%\usepackage{xcolor}
\usepackage{graphicx,fancyhdr,algorithm,algorithmic}
\usepackage[space]{grffile}
\usepackage{titlesec}
\usepackage{multicol}
\usepackage{enumitem} 
\usepackage{tikz}
\usepackage{tikz-qtree}
\usetikzlibrary{arrows,automata}


\cfoot{\thepage}
\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\headwidth}{\textwidth}
\renewcommand{\footrulewidth}{0.4pt}

%some custom commands for problem 2
%want some nice colors
\definecolor{darkred}{rgb}{.87,0,0}
\definecolor{niceblue}{rgb}{.392,.584,.929}
%change the font, change the color, and raise the first word's letters slightly
\newcommand{\firstword}[1]{\textsf{{\color{darkred}{\raisebox{.3em}{#1}}}}}
\newcommand{\secondword}[1]{\textsf{{\color{niceblue}{#1}}}}

\newcommand{\defn}{\textbf}


\theoremstyle{definition}
\newtheorem{problem}{Problem}
\newtheorem{claim}{Claim}
\newtheorem{definition}{Definition}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{observation}{Observation}
\newtheorem{question}{Problem}

\newenvironment{solution}{\bigskip\noindent{\it Solution.}  \ignorespaces}{\hfill\qed}

\usepackage{hyperref}
\hypersetup{
    colorlinks=true,
    linkcolor=blue,
    filecolor=magenta,      
    urlcolor=cyan,
}
\urlstyle{same}
\PassOptionsToPackage{hyphens}{url}
\newcommand{\homework}[6]{
   \pagestyle{myheadings}
   \thispagestyle{plain}
   \newpage
   \setcounter{page}{1}
   \noindent
   \begin{center}
   \framebox{
      \vbox{\vspace{2mm}
    \hbox to 6.28in { {\bf CS 256:~Algorithm Design and Analysis \hfill} }
       \vspace{6mm}
       \hbox to 6.28in { {\Large \hfill #1 \normalsize{(#2)}  \hfill} }
       \vspace{6mm}
     \hbox to 6.28in { {\it Instructor: #3 \hfill } }
   }
   }
   \end{center}
   \markboth{#1}{#1}
   \vspace*{4mm}
}



\begin{document}
\homework{Assignment 9}{due 12/03/2020}{Sam McCauley}{}{}{}

\begin{question}[KT 13.2]
  Consider a county in which 100,000 people vote in an election.  There are only two candidates on the ballot: a Democratic candidate (denoted \textit{D}) and a Republican candidate (denoted \textit{R}).  As it happens, this county is heavily Democratic, so 80,000 people go to the polls with the intention of voting for \textit{D}, and 20,000 go to the polls with the intention of voting for \textit{R}.

  However, the layout of the ballot is a little confusing, so each voter, independently and with probability  $1/100$, votes for the wrong candidate---that is, the one that he or she \emph{didn't} intend to vote for.  (Remember that in this election, there are only two candidates on the ballot.)

  Let $X$ denote the random variable equal to the number of votes received by the Democratic candidate $D$, when the voting is conducted with this process of error.  Determine the expected value of $X$.
\end{question}
\begin{solution}
\end{solution}


  \newpage
\begin{question} 
Consider the process of throwing $n$ balls into $m$ bins, where each ball
is thrown into a uniformly random bin, independent of other balls.  What is the expected
number of balls in a particular bin $b$? ({\em Hint.}  Define appropriate indicator random
variables and use linearity of expectation.)

\noindent
{\em Number of collisions in a hash table with chaining.}  This analysis gives, under a 
random hash function, the expected number
of collisions in a hash table with chaining if $n$ items are stored in a hash table with $m$ slots.
\end{question}
\begin{solution}
\end{solution}

  \newpage
\begin{question}[Erickson handout]
 Your boss wants you to find a perfect hash function for mapping a known set of $n$ items into a table of size $m$. A hash function is perfect if there are no collisions; each of the $n$ items is mapped to a different slot in the hash table. Of course, a perfect hash function is only possible if $m\geq n$.  

 After cursing your algorithms instructor for not teaching you about (this kind of) perfect hashing, you decide to try something simple: repeatedly pick random hash functions until you find one that happens to be perfect.

\begin{enumerate}[label = (\alph*)]
  \item Suppose you pick an random hash function $h$. What is the exact expected number of collisions, as a function of $n$ (the number of items) and $m$ (the size of the table)? 

 Don’t worry about how to resolve collisions; just count them.
\item\label{probperfect} What is the exact probability that a random hash function is perfect?
\item What is the expected number of different random hash functions you have to test before you find a perfect hash function?  Give an exact answer (using your answer to part~\ref{probperfect}), then simplify your answer using the techniques we've seen in class.  (The simplified answer should be a function of $m$ and $n$, rather than a product of many terms.)
\end{enumerate}
\end{question}
\begin{solution}
\end{solution}

  \newpage
\begin{question}
In class, we saw simple randomized algorithms that give a constant factor
approximation to NP hard problems like MAX-3-SAT and Max-Cut.  
%
In this question, we design a simple deterministic approximation
algorithm for the NP hard problem, Vertex Cover.  Consider the following simple strategy: 

\begin{itemize}[noitemsep]
    \item[] Start with vertex cover $S \leftarrow \emptyset$
    \item[] While there is an uncovered edge $e = (u,v)$:
    \begin{itemize}
        \item Add both endpoints to $S$, that is, $S \leftarrow S \cup \{u, v\}$
        \item Delete all edges that are incident on $u$ and $v$
    \end{itemize} 
\end{itemize}
Show that the above algorithm is a $2$-approximation. In particular, show that
$S$ is a vertex cover and that $|S| \leq 2 \cdot |S^*|$, where $S^*$ is a optimal (minimum-size) vertex cover.
    
\end{question}
\begin{solution}
\end{solution}



\end{document}

