% CS91T Homework 2
% https://tinyurl.com/hc4p8jf2
\documentclass[11pt]{article}
\usepackage{fullpage}
\usepackage{clrscode3e}
\usepackage{xspace}
\usepackage{amsmath}
\allowdisplaybreaks

\newcommand{\latex}{\LaTeX\xspace}
\newcommand{\flipcoin}{\textsc{flipCoin()}\xspace}
\newcommand{\bogocoin}{\textsc{bogoCoin()}\xspace}
\newcommand{\eqlong}{\textsc{Equality}\xspace}
\newcommand{\spot}{\textsc{SpotTD}\xspace}

\begin{document}
\begin{center}
{\huge \textbf{CS91T Lab Assignment 2} }
\end{center}
\vspace{0.2in} This homework is due at 11:59PM on Wednesday, February
22.  Write your solution using \LaTeX.  Submit this homework using
\textbf{github}.
%

This is a partnered assignment.  You should primarily be discussing
this assignment with your partner.
%
It's ok to discuss approaches at a high level.  However, you should
not reveal specific details of a solution, nor should you show your
written solution to anyone else.  

When you submit homework assignments this semester, please keep the
following in mind:
\begin{itemize}
\item Don't forget to fill out the {\bf homework submission poll}
  using Pollster.
\item Don't submit a .pdf -- just the .tex will do.
\item I will compile your .tex file using pdflatex.  It is your
  responsibility to make sure the \latex compiles.
\end{itemize}

The main \textbf{learning goals} of this assignment are to gain more
practice with discrete probabilty and to think more deeply about
randomized algorithms.

\begin{enumerate}
\item We've modeled the randomness in a randomized algorithm as a
  single operation \flipcoin, which takes no input and returns $1$
  with probability 0.5 and $0$ with probability 0.5.  However, in
  reality it might be very difficult to find a source of randomness
  that produces truly uniform random bits.

  In particular, suppose that instead of \flipcoin, you're given an
  operation \bogocoin, which also takes no inputs, but returns $1$
  with probability $p$ and $0$ with probability $1-p$, for some
  $0<p<1$.  Furthermore, suppose that the precise value of $p$ is
  \emph{unknown} to you.  How can you use \bogocoin to generate
  uniform random bits?

  \begin{enumerate}
  \item Design an implementation of \flipcoin that uses \bogocoin as a
    subroutine.
  \item Argue that your implementation of \flipcoin works; i.e., that
    the bit it returns is uniform.
  \item What is the expected number of calls to \bogocoin that your
    algorithm makes?  Express your answer in terms of $p$.
  \end{enumerate}

  
\item A random variable $X \in \{0,1\}$ has bias $\delta$ for some
  $0\leq \delta \leq 1$ if either $\Pr[X=1] = \frac{1}{2}(1+\delta)$
  or $\Pr[X=1] = \frac{1}{2}(1-\delta)$.  In the former case, we say
  that $X$ is \emph{biased towards 1}.  In the latter case, $X$ is
  \emph{biased towards 0}.  For example, if $X==1$ with probabiltiy
  $3/4$, then $X$ has bias $1/2$ since $\frac{3}{4} =
  \frac{1}{2}(1+\frac{1}{2})$.

  Now, suppose you have $n$ random bits $X_1,\ldots, X_n$, and let $Y$
  be the \textsc{XOR} of the random bits: $$Y := X_1 \oplus X_2 \oplus
  \cdots \oplus X_n\ .$$ Show that if the bias of each $X_i$ is
  $\delta_i$, then the bias of $Y$ is $\delta_1\delta_2\cdots\delta_n$.

  \textbf{Hint:} Prove this by induction on $n$.

\item \label{low-error-eq} Recall the \eqlong problem from class:
  Alice and Bob are given $n$ bit strings $x,y\in \{0,1\}^n$ and must
  communicate to decide whether or not $x$ equals $y$.

  In class we saw a strategy that used seven bits of communication and
  had error $1/128$.  Suppose even this error isn't good enough.  Give
  an algorithm for $\eqlong$ that has error $1/k$.  Express the
  communication cost as a function of $k$.

\item \textbf{Spot the Difference.} In this problem, Alice and Bob
  again have $n$-bit strings $x,y \in \{0,1\}^n$.  This time, they
  know the strings are equal, except in one bit; i.e., there is a
  unique index $1\leq i \leq n$ such that $x_i \neq y_i$.  Define
  $\spot(x,y) :=i$ to be this unique location.

  Give a randomized communication protocol for Alice and Bob to
  compute $\spot(x,y)$.  What is the communication cost of your
  protocol?  You will earn full credit for any protocol that uses
  $O(log(n))$ bits.


\item \textbf{Probabilistic Method.} Suppose there are 650 points in a
  circle of radius 16 inches.  You have a washer of outer radius 3
  inches, inner radius 2 inches.

  Show you can place the washer so it covers at least 10 points.
\end{enumerate}

\end{document}
