\documentclass{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{listings}
\usepackage{enumitem}
\usepackage{hyperref}
\usepackage{algorithmicx,algorithm}
\usepackage{algpseudocode}
\usepackage{float}

\usepackage{etoolbox}
\usepackage{url}
\usepackage[most]{tcolorbox}
\usepackage{xcolor}
% 0.0in to center
\setlength{\topmargin}{-.53in}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{0.0in}
\setlength{\evensidemargin}{0.0in}
\setlength{\textheight}{9in}
%\setlength{\parskip}{\medskipamount}
\setlength{\marginparwidth}{1.2in}
%\renewcommand{\baselinestretch}{1.3}

\lstset{
  language=Python,
  showstringspaces=false,
  formfeed=newpage,
  tabsize=4,
  commentstyle=itshape,
  morekeywords={models, lambda, forms}
}


\newtheorem{theorem}                {Theorem}
\newtheorem{lemma}      [theorem]   {Lemma}
\newtheorem{remark}     [theorem]   {Remark}
\newtheorem{fact}       [theorem]   {Fact}
\newtheorem{claim}      [theorem]   {Claim}
\newtheorem{corollary}      [theorem]   {Corollary}
\newtheorem{definition}     [theorem]   {Definition}
\newtheorem{prop}       [theorem]   {Proposition}
\newtheorem{warning}        [theorem]   {Warning}

\def\proof{\rm \trivlist \item[\hskip \labelsep{\bf Proof. }]}
\def\endproof{\hfill $\rule{1.3ex}{1.3ex}$ \endtrivlist}

\newcommand{\ip}[2]{
{\langle {#1} , {#2} \rangle}
}
\newcommand{\n}[1]{
{\| {#1} \|}
}
\newcommand{\ns}[1]{
{\| {#1} \|^2}
}

\providetoggle{solution}
\settoggle{solution}{false}

\def\prop{{\em Proposition: }}
\def\L{\mathcal{L}}
\def\N{\mathcal{N}}
\def\C{\mathcal{C}}
\def\Z{\mathcal{Z}}
\def\Q{\mathcal{Q}}
\def\R{\mathcal{R}}
\def\P{\mathcal{P}}
\def\M{\mathcal{M}}
\def\B{\mathcal{B}}
\def\TV{$T \in \mathcal{L}(V)$ }
\def\pf{\noindent {\bf Proof Sketch: }}
%\def\limsup{\overline{\lim}}
%\def\liminf{\underline{\lim}}
\def\sm{\setminus}


\newcommand{\bfx}{{\bf x}}
\newcommand{\bfy}{{\bf y}}

\begin{document}

\begin{center}
{\Large CS265/CME309, Problem Set 1}

\begin{tabular}{rl}
SUNet ID(s): & \\
Name(s): & \\
\end{tabular}
\end{center}

By turning in this assignment, I agree by the Stanford honor code and declare that all of the writing is the work of my partner and I (discussion in larger groups is permissible).


\begin{center}
{\large Due by 11:59 PM on \textbf{Tuesday}, October 1st.}
\end{center}

\begin{enumerate}
       \item 	Random Bits:  
       \begin{enumerate}
       \item (4 points) Given access to coins whose probability of landing heads is $1/5$, describe a scheme for generating a uniformly random bit. In other words, how can one simulate a flip of a coin that lands heads with probability exactly $1/2$?  \\
       
       \medskip
       SOLUTION: xxxxx
       
       \medskip 
       
       \item (4 points) Given access to coins whose probability of landing heads is $1/2$, describe a scheme for simulating the flip of a coin whose probability of heads is $1/3$.   For full credit, your scheme should, \emph{in expectation}, flip at most two coins.\\
       
              \medskip
       SOLUTION: xxxxx
       
       \medskip 
       
       
       \item (4 points) In one or two sentences, explain why the above problems are impossible if you were required to write a protocol that flips the given coins at most some fixed number, $k$, times. \\
       
              \medskip
       SOLUTION: xxxxx
       
       \medskip 
       
       \end{enumerate}

       
       \item (Linearity of Drunk Pigeons) Suppose there are 100 pigeons, and 100 pigeon-holes, with each pigeon-hole belonging to a pigeon.  One crazy night, all the pigeons get rather drunk, and each one selects a pigeon-hole to return to \emph{uniformly at random} .
       \begin{enumerate}
       \item (4 points) What is the expected number of pigeons that end up returning to their proper hole?  (Hint: use linearity of expectation!)
       \item (4 points) What is the expected number of pigeons that will end up in a hole with exactly one other pigeon? (Hint: use linearity of expectation!)
       \item (Bonus 1 point) Suppose we have $n$ pigeons, and $n$ holes.  Show that in the limit as $n\rightarrow \infty,$ the expected fraction of empty holes after the drunken night approaches $1/e$.
       \end{enumerate}  

       
       \item  Suppose we have $n$ students in the class, and exactly $k \le n$ are infected with the wait-until-Monday-to-start-homework illness.  Fortunately, there is a blood test for identifying this, though it is very expensive.  Suppose we take a sample of blood from each student.  There are two options: 1) test a drop from each of the $n$ samples, 2) randomly partition the $n$ samples into groups of $m$, for each group, mix together a drop from each of the $m$ samples in the group and test that mixture; if that mixture tests positive, then individually test each of the $m$ students in that group.  For the following problems, feel free to assume that $n$ is a multiple of $m$ if that simplifies calculations.
       \begin{enumerate}
       	\item (4 points) If we use the second strategy, as a function of $n, k$ and $m$, what is the expected number of combined samples (i.e. groups) that will test positive? (Hint: linearity of expectation!)
	\item (4 points) If we use the second strategy, what is the expected total number of tests that we will need to perform to identify all of the $k$ infected students, as a function of $n,k,$ and $m$?  When is this significantly better than using the first strategy (testing all $n$ students separately)?  Justify your answer with one or two sentences.
	\item  (4 points) If we use the second strategy, what is a near-optimal group size, $m$, as a function of $n$ and $k$, and what is the expected number of total tests that will be conducted using this value of $m$?   
       \item (Double Bonus---this part is not graded.)  Strategy 2 is a two-step scheme---can you design an optimal multistep scheme?  What changes if the test is not 100\% accurate, but only accurate with probability $3/4$? Some variants of these questions are still open research problems!
       \end{enumerate}
       
       \item Improving the random min-cut algorithm seen in class.  Recall that the algorithm proceeds by iteratively choosing a random edge to ``contract'' until the graph has only 2 vertices, and then outputs the corresponding cut.  (In class we showed that the probability that this scheme outputs a minimum cut is at least $\frac{2}{n(n-1)} \approx 2/n^2$.)
              \begin{enumerate}
     		\item  (4 points) Consider the following variation:  starting with a graph on $n$ vertices, first contract the graph down to $k$ vertices, and now run the randomized algorithm on this smaller graph $\ell$ (independent) times and output the smallest cut found in any of the $\ell$ runs.  Determine the number of edge contractions and bound the probability of finding a minimum cut, as functions of $n,k,\ell.$
		\item   (4 points) What are near-optimal values of $k,\ell$, (as functions of $n$) which maximize the probability of finding a minimum cut, while using at most $2n$ total edge contractions?  [Feel free to just give the asymptotics---i.e. ``$k=\Theta(n^{blah}),$ in which case the probability of success is $\Theta(n^{-blah'})$''.  For comparison, if we were to repeat the algorithm from class twice, and output the better of the two cuts found, we would end up using $2(n-2) \approx 2n$ contractions, and have probability of success $\ge 1-(1-\frac{2}{n(n-1)})^2 \approx \frac{4}{n^2}.$]
		\item (Bonus 2 points) Note that one could extend the above improvements by having a multi-stage algorithm with $k_1,k_2,\ldots,$ and corresponding $\ell_1,\ell_2,\ldots$ (as opposed to the two-stage algorithm considered above).  Describe an (optimal) scheme that requires at most $\tilde{O}(n^2) = O(n^2 \text{ polylog }n)$ edge contractions to achieve a probability of success $> 1/2$. For this part, feel free to ignore all poly-logarithmic factors of $n$. [For comparison, the scheme in class would need to be repeated $O(n^2)$ times to achieve success probability $1/2$, and hence the total number of edge contractions would be $\Theta(n^3)$.]
		\item (Bonus 1 point) Prove that it is impossible for any scheme of the above form to achieve success probability greater than $1/2$ using fewer than $\Theta(n^2)$ edge contractions. 
 \end{enumerate}
       
       
\end{enumerate}


\end{document} 