\documentclass[12pt]{article}
\usepackage{amsmath}
%\usepackage{fullpage}
\usepackage[top=1in, bottom=1in, left=0.8in, right=1in]{geometry}
\usepackage{multicol}
\usepackage{wrapfig}
\usepackage{listings}
\usepackage{enumerate}
\usepackage{comment}
\usepackage{tikz}
\usepackage[ruled,vlined]{algorithm2e}
\lstset{language=Java,
basicstyle={\small\ttfamily},
columns=flexible,
belowskip=0mm}

\setlength{\columnsep}{0.1pc}

\begin{document}

\noindent
CS 161 \hfill \textbf{Problem Set 3} \newline 
{Spring 2017} \hfill \textbf{Due:} April 28, 2017, 3pm


\noindent
\rule{\linewidth}{0.4pt}

\noindent
  Please answer each of the following problems.  Refer to the course webpage for
the \textbf{collaboration policy,} as well as for \textbf{helpful advice} for
how to write up your solutions.
\\\\
\textbf{Note:} For all problems, if you include pseudocode in your solution,
please also include a brief English description of what the pseudocode does.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Problems:

\begin{enumerate}

    % Problem 1
    
       \item Suppose that $p$ is an unknown value, $0 < p < 1$.  Suppose that
you can call a function \verb|randP| which returns \verb|true| with probability
$p$ and returns \verb|false| with probability $1 - p$.  Every call to
\verb|randP| is independent.  You have no way to generate random numbers except
through \verb|randP|.
\begin{enumerate}[(a)]
\item (2 pts) Describe an algorithm---using \verb|randP|---that returns
\verb|true| with probability $1/2$ and \verb|false| with probability $1/2$.
Your algorithm should in expectation, use $\frac{1}{p(1-p)}$ calls to
\verb|randP|.  Your algorithm does not have access to the value of $p$, and does
not have access to any source of randomness other than calls to \verb|randP|.
\textbf{[We are expecting pseudocode, and a short English description of what
the algorithm does.  Your pseudocode should be detailed enough that a CS106B
student could implement it without much thought.]}

\underline{Hints:} (i) Your algorithm does not have to compute $p$, or an
approximation to it.  (ii) Notice that in the worst case, your algorithm may use
more calls to \verb|randP|, possibly even infinitely many. 
\item (1pts) Formally prove that your algorithm runs using expected
$\frac{1}{p(1-p)}$ calls to \verb|randP|.
\textbf{[We are expecting a mathematical calculation of the expected value of
the total number of calls to \texttt{randP}.]}

\item (1 pt) Informally argue that your algorithm returns \verb|true| with
probability $1/2$ and \verb|false| with probability $1/2$.
\textbf{[We are expecting an informal justification of why the algorithm returns
\texttt{true} with probability $1/2$ and \texttt{false} with probability $1/2$.
Your argument should convince the reader that you are correct, but does not have
to be a formal proof.]}
\end{enumerate}
    
    %%%%%%%%%%%%%%%% PROBLEM 2 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    
    \item Suppose that $A$ and $B$ are sorted arrays of length $n$, and that all
numbers in the arrays are distinct.
    \begin{itemize}
      \item[(a)](3pts) Design an algorithm to find the median of all $2n$
numbers in $O(\log n)$ time.  For our purposes, we define the median of the 
$2n$ numbers as the $n$th smallest number in the $2n$ values.
\textbf{ [We are expecting: pseudocode, and an
English description of the algorithm, detailed enough that a CS 106B student
could implement it without much thought.] }
         \item[(b)](3pts) Informally argue that your algorithm correctly finds
the median of all $2n$ numbers. \textbf{[We are expecting a short (paragraph or
two) argument that will convince the reader why your algorithm works
correctly.]}
        \item[(c)](2pts) Prove that your algorithm runs in time $O(\log(n))$
time.   \textbf{[We are expecting a formal proof.]}

    \end{itemize}
    
    %%%%%%%%%%%%% PROBLEM 3 %%%%%%%%%%%%%%%%%%%%%%%%%%
    
    \item Suppose you want to sort an array $A$ of $n$ numbers (not necessarily
distinct), and you are guaranteed that all the numbers in the array are in the
set $\{1,\ldots,k\}$.  A \textbf{``20-question sorting algorithm''} is any
deterministic algorithm that asks a series of YES/NO questions (not necessarily
20 of them, that's just a name) about $A$, and then \emph{writes down} the
elements of $A$ in sorted order.  (Specifically, the algorithm does not need to
rearrange the elements of $A$, it can just write down the sorted numbers in a
separate location).  
    
    Note that there are many YES/NO questions beyond just
comparison-questions---for example, the following are also valid YES/NO
questions: ``If I ignored A[3] and A[17] would the array be sorted?'' and ``Did
it rain today?''   
\begin{enumerate}
\item[(a)] (2 pts) Describe a 20-question sorting algorithm that will, for every
input, ask only $O(k \log n)$ questions.  Feel free to assume that the algorithm
is also told $n$ and $k$, although this isn't necessary.  [\underline{Hint}: If
you are stuck, first think about how you would do this with $\log n$ questions
if $k=2$.  What would you need to know about the array to write down the sorted
list of elements?]
   \textbf{[We are expecting a description of the algorithm and an informal
(1-paragraph) argument that it achieves the desired runtime.]}

\item[(b)] (2 pts) Prove that for \emph{every} 20-question sorting algorithm,
there is some array $A$ consisting of $n$ integers between $1$ and $k$ that will
require $\Omega(k \log \frac{n}{k})$ questions, provided $k \le n$.
[\underline{Hints:} Why is it sufficient for this problem to lower-bound the
number of ordered arrays, instead of counting exactly? Once you have understood
this, use a counting argument: how can you lower-bound the number of ordered
arrays are there that consist of $n$ integers $\{1,\ldots, k\}$ (not necessarily
distinct)? There are a number of ways to do this; we suggest you do NOT use
Stirling's approximation: you don't need this in order to prove the result, and
it will be complicated. ]
  \textbf{[We are expecting a mathematically rigorous proof (which does NOT
necessarily mean something long and tedious).]}
  

\end{enumerate}


%%%%%%% PROBLEM 4

\item
Suppose that on your computer you have stored $n$ password-protected files, each
with a unique password. You've written down all of these $n$ passwords, but you
do not know which password unlocks which file. You've put these files into an
array $F$ and their passwords into an array $P$ in an arbitrary order (so $P[i]$
does not necessarily unlock $F[i]$). If you test password $P[i]$ on file $F[j]$,
one of three things will happen:

\begin{enumerate}[1)]
\item $P[i]$ unlocks $F[j]$
\item The computer tells you that $P[i]$ is lexicographically smaller than
$F[j]$'s true password
\item The computer tells you that $P[i]$ is lexicographically greater than
$F[j]$'s true password
\end{enumerate}

You \textbf{cannot} test whether a password is lexicographically smaller or
greater than another password, and you \textbf{cannot} test whether a file's
password is lexicographically smaller or greater than another file's password.

\begin{enumerate}[(a)]
\item(3pts)
Design an randomized algorithm to match each file to its password, which runs in
expected runtime $O(n\log(n))$. \textbf{[We are expecting: pseudocode and/or an English
description of an algorithm.]}
\item(2pts)
Explain why your algorithm is correct.  \textbf{[We are expecting: an informal
argument (a paragraph or so) about why your algorithm is correct, which is
enough to convince the reader/grader.  You may also submit a formal proof if you
prefer.]}
\item(2pts) Analyze the running time of your algorithm, and show that it runs in
expected runtime $O(n\log(n))$. \textbf{[We are expecting: a formal analysis of the
runtime.]}
\end{enumerate}

%%%%%%%%%% PROBLEM 5 %%%%%%%%%%%%%

\item (6pts, 1 pt per part) In the \verb|select| algorithm from class, in order
to find a pivot, we break up our array into blocks of length 5. Why 5? In this
question, we explore \verb|select-3|, in which we break up our array into blocks
of length 3. As you go through this problem, feel free to refer to the course
notes from 4/12 and the week 3 recitation notes. In addition, to simplify your
logic, you should assume throughout this problem that your array is a power of
3.

\begin{enumerate}
\item Consider the pseudocode for \verb|select| and \verb|choosePivot| on pages
2 and 4 of the April 12th course notes. In this pseudocode, we break up our
array into blocks of size 5. What change(s) would you need to make to this
pseudocode in order to write \verb|select-3| and \verb|choosePivot-3|?
\textbf{[We are expecting a one or two sentence description of changes made, so
that a 106b student would know exactly what to do.]}


\item Prove that the recursive call to \verb|select-3| inside of
\verb|choosePivot-3| is on an array of size at most $n/3$. You should assume
that your array is a power of 3. \textbf{[We are expecting a rigorous proof.]}

\item Prove that the recursive call inside of \verb|select-3| is on an array of
size at most $2n/3 + 2$. You should again assume that your array is a power of
3. (Hint: it might be helpful to note that $\lceil x \rceil \leq x + 1$.)
\textbf{[We are expecting a rigorous proof.]}

\item Explain why the work done within a single call to \verb|select-3| and
\verb|choosePivot-3| on an array of size $n$ is $\Theta(n)$. \textbf{[We are
expecting a few sentences of explanation. You do \textit{not} need to do a
formal proof with the definition of $\Theta$.]}

\item Using what you proved in (b), (c), and (d), write down a recurrence
relation for the runtime of \verb|select-3|. (You can do this problem even if
you did not complete all of (b), (c), and (d).)  \textbf{[We are expecting a
one-line answer with your recurrence relation.]}

\item Is \verb|select-3| $O(n)$? Justify your answer. \textbf{[We are not
expecting a formal proof, but you should describe clear reasoning, such as
analyzing a tree, unraveling the recurrence relation to get a summation, or
attempting the substitution method.  (Note that succeeding at the substitution
method would prove select-3 is O(n), but failing at the substitution method does
not prove select-3 is not O(n).)]}

\end{enumerate}
\end{enumerate}

\end{document}
