\documentclass[11pt]{article}
% Problem set: do not define TEMPLATE or SOL
% LaTeX template: define TEMPLATE but not SOL
% Solution: define both TEMPLATE and SOL
%
%\def\sol{1}
\def\template{1}
% STUDENTS:
% You can enter your solutions into this template by just
% typing them right after it says "SOLUTION".
% Ignore the \ifdefined\sol blocks; you can delete them if you want.
% (Note that it won't compile if you try to uncomment the
% solution flag :))
%
\usepackage{fullpage,graphicx}
\usepackage{amsmath,amsfonts,amsthm,amssymb,multirow, url}
\usepackage{tikz}
\usetikzlibrary{shapes.symbols}
\usepackage{wrapfig}
\usepackage{algorithmic}
\usepackage{enumerate}
\usepackage{wasysym}
\usepackage{framed}
\usepackage{float}
\usepackage[ruled,vlined,commentsnumbered,titlenotnumbered]{algorithm2e}
\newcommand{\expecting}[1]{\noindent{[\textbf{We are expecting:} \em #1\em]}}
\newcommand{\pts}[1]{\textbf{(#1 pt.)}}
\newcommand{\hint}[1]{\noindent{[\textbf{Hint:} \em #1 \em]}}
\definecolor{shadecolor}{gray}{0.95}



\begin{document}
\noindent
CS 161 \hfill \textbf{Problem Set 3} \newline 
{Spring 2023} \hfill \textbf{Due:} Wednesday, April 26 at 1pm on Gradescope.

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

\noindent
\textbf{Style guide and expectations:} Please see the ``Homework" part of the ``Resources" section on the webpage for guidance on what we are looking for in homework solutions.  We will grade according to these standards.

Make sure to look at the ``\textbf{We are expecting}'' blocks below each problem to see what we will be grading for in each problem!
\newline\newline
\textbf{Collaboration policy:} You may do the HW in groups of size up to three.  Please submit one HW for your whole group on Gradescope.  (Note that there is an option to submit as a group).  See the ``Policies'' section of the course website for more on the collaboration policy.
 \ifdefined\template
\begin{shaded}
 \noindent  \textbf{Group members' name(s): } %enter your group names here
\\\\
 \noindent  \textbf{Collaborator name(s):} %enter your collaborator names here
\\\\
 \noindent \textbf{(Optional) Group name:} 
 % tell us what your homework group believes in 
\end{shaded}
\fi 
\noindent
\rule{\linewidth}{0.4pt}


\section*{Exercises}
We recommend you do the exercises on your own before collaborating with your group.

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


%%%%%%%%%%%%%% EXERCISE 1 %%%%%%%%%%%%%%%%%%%%%%%%%


\item \pts{6}
In this exercise, we'll explore different types of randomized algorithms.  We say that a randomized algorithm is a \textbf{Las Vegas Algorithm} if it is always correct, but the running time is a random variable.  We say that a randomized algorithm is a \textbf{Monte Carlo Algorithm} if there is some probability that it is incorrect.  For example, QuickSort (with a random pivot) is a Las Vegas algorithm, since it always produces a sorted array (but if we get very unlucky QuickSort may be slow).  

Suppose that there is a population of $n$ flamingos.  Half of the flamingos are pink, and half are white, but it's dark outside and you can't tell the difference until you catch one and look at it with a flashlight.  Assume that catching a random flamingo and looking at it takes time $O(1)$.

The algorithms given in Figure~\ref{algs} all attempt to find a single pink flamingo. 
Fill in the chart below.  You may use asymptotic notation for the running times; give the best big-Oh bound that you can.  For the probability of returning a correct flamingo, do not use asymptotic notation; give the best bound that you can.
\begin{center}
\begin{tabular}{|c|p{3cm}|p{2cm}|p{2cm}|p{4cm}|}
\hline
Algorithm & Monte Carlo or Las Vegas? & Expected running time 
& Worst-case running time & Probability of returning a pink flamingo \\
\hline
\textbf{Algorithm 1} &  &  &  & \\
\hline
\textbf{Algorithm 2} &  &  &  & \\
\hline
\textbf{Algorithm 3} &  &  &  & \\
\hline
\end{tabular}
\end{center}
Note that the \LaTeX \ code for the table is available in the source file.

\hint{Remember (see Lecture 5 and the pre-lecture exercise) that the expectation of a geometric random variable with probability $p$ is equal to $\frac{1}{p}$}

\expecting{A filled-in table.  No justification is required.}

\begin{figure}[h]
\begin{algorithm}[H]
\KwIn{A flock of $n$ flamingos}
\While{true}
{
Choose a random flamingo from the flock\;
\If{That flamingo is pink}{ \Return{ that flamingo } }
\Else{Release the flamingo back into the flock}
}
\caption{\textsc{findPinkFlamingo1}}
\end{algorithm}

\begin{algorithm}[H]
\KwIn{A flock of $n$ flamingos}
\For{100 iterations}
{
Choose a random flamingo from the flock\;
\If{That flamingo is pink}{ \Return{ that flamingo } }
\Else{Release the flamingo back into the flock}
}
Choose a random flamingo from the flock\;
\Return{ That flamingo }
\caption{\textsc{findPinkFlamingo2}}
\end{algorithm}

\begin{algorithm}[H]
\KwIn{A flock of $n$ flamingos}
Put the flamingos in a line, in a random order \;
\tcc{Assume it takes time $O(n)$ to put the $n$ flamingos in a random order; and assume that they stay put once ordered.}
\For{ $i = 0, \ldots, n-1$ }
{
\If{Flamingo $i$ is pink}{ \Return{ Flamingo $i$ } }
}
\caption{\textsc{findPinkFlamingo3}}
\end{algorithm}
\caption{Three algorithms for finding a pink flamingo}\label{algs}
\end{figure}\clearpage

\ifdefined\template
\begin{shaded}
\textbf{SOLUTION:}

\begin{center}
\begin{tabular}{|c|p{3cm}|p{2cm}|p{2cm}|p{4cm}|}
\hline
Algorithm & Monte Carlo or Las Vegas? & Expected running time 
& Worst-case running time & Probability of returning a pink flamingo \\
\hline
\textbf{Algorithm 1} &  &  &  & \\
\hline
\textbf{Algorithm 2} &  &  &  & \\
\hline
\textbf{Algorithm 3} &  &  &  & \\
\hline
\end{tabular}
\end{center}
\ifdefined\sol
\input{solutions/E1.tex}
\fi
\end{shaded}
\fi


\end{enumerate}
\newpage
\noindent
\rule{\linewidth}{0.4pt}
\section*{Problems}

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

\begin{enumerate}
\setcounter{enumi}{1}

%%%%%%%%%%%%%%%%%%%%%%%% Problem 2: Flamingo Politics %%%%%%%%%%%%%%%%%%%

\item \textbf{[Flamingo Politics]} \pts{6} Suppose that $n$ flamingos are standing in a line.  
\begin{center}
\includegraphics[width=2cm]{flamingo}
\hspace{.1cm}
\includegraphics[width=2cm]{flamingo}
\hspace{.1cm}
\includegraphics[width=2cm]{flamingo}
\hspace{.1cm}
\includegraphics[width=2cm]{flamingo}
\hspace{.1cm}
\includegraphics[width=2cm]{flamingo}
\hspace{.1cm}
\includegraphics[width=2cm]{flamingo}
\end{center}

Each flamingo has a political leaning: left, right, or center.  You'd like to sort the flamingos so that all the left-leaning ones are on the left, the right-leaning ones are on the right, and the centrist flamingos are in the middle.
You can only do two sorts of operations on the flamingos:

\begin{center}
\begin{tabular}{|c|c|c|}
\hline
Operation & Result\\
\hline
\texttt{poll(j)} & Ask the flamingo in position $j$ about its political leanings \\ 
\hline
\texttt{swap(i,j)} & Swap the flamingo in position $j$ with the flamingo in position $i$ \\
\hline
\end{tabular}
\end{center}

However, in order to do either operation, you need to pay the flamingos to cooperate: each operation costs one brine shrimp.\footnote{According to Wikipedia, flamingos eat brine shrimp.  Yum!}  Also, you didn't bring a piece of paper or a pencil, so you can't write anything down and have to rely on your memory!  Like many humans, your memory is limited, and you can only remember up to seven\footnote{\url{https://en.wikipedia.org/wiki/The_Magical_Number_Seven,_Plus_or_Minus_Two}} integers between $0$ and $n-1$ at a time (i.e. you can use at most seven integer-valued variables at a time in your algorithm).

Design an algorithm to sort the flamingos, which costs $O(n)$ brine shrimp, and uses no extra memory other than storing at most seven\footnote{You don't need to use all seven storage spots, but you can if you want to.  Can you do it with only two?} integers between $0$ and $n-1$.

\hint{Does this task look like anything we've seen in class?}

\expecting{Pseudocode \textbf{AND} a short English description of your algorithm; \textbf{AND} a short explanation of why it uses only $O(n)$ brine shrimp and never uses more than seven numbers of memory.}

\ifdefined\template
\begin{shaded}
\textbf{SOLUTION:}
\ifdefined\sol
\input{solutions/flamingo1.tex}
\fi
\end{shaded}
\fi


%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Problem 3: Flamingos of new heights  %%%%%%%%%%%%%%%%%%%%%%
\newpage
\item \textbf{[Flamingos of new heights]} \pts{6}
Suppose that $n$ flamingos of distinct heights are standing in a line, ordered from shortest to tallest. 
\begin{center}
\includegraphics[height=2cm]{yardstick}
\includegraphics[width=1.5cm,height=1.2cm]{flamingo}
\hspace{.1cm}
\includegraphics[width=1.5cm,height=1.7cm]{flamingo}
\hspace{.1cm}
\includegraphics[width=1.5cm,height=1.9cm]{flamingo}
\hspace{.1cm}
\includegraphics[width=1.5cm,height=2cm]{flamingo}
\hspace{.1cm}
\includegraphics[width=1.5cm,height=2.5cm]{flamingo}
\hspace{.1cm}
\includegraphics[width=1.5cm,height=3cm]{flamingo}
\end{center}

You have a measuring stick of a certain height, and you would like to identify a flamingo which is the same height as the stick, or else report that there is no such flamingo. The only operation you are allowed to perform is \texttt{compareToStick(f)}, where $f$ is a flamingo (that is, you cannot directly access the heights of each flamingo). \texttt{compareToStick(f)} returns \texttt{taller} if $f$ is taller than the stick, \texttt{shorter} if $f$ is shorter than the stick, and \texttt{the same} if $f$ is the same height as the stick.  As in the previous problem, you can only store up to seven integers in $\{0,\ldots,n-1\}$ at a time.  And, as in the previous problem, you have to pay flamingos one brine shrimp every time you perform \texttt{compareToStick}.

\begin{enumerate}
\item \pts{2} Give an algorithm in this model of computation which either finds a flamingo the same height as the stick, or else returns ``No such flamingo," and uses $O(\log(n))$ brine shrimp. 

\expecting{Pseudocode \textbf{AND} an English description.  You do not need to justify the correctness or brine shrimp usage. } 
\item \pts{4} Prove that any algorithm in this model of computation must use $\Omega(\log(n))$ brine shrimp.

\expecting{A short but convincing argument.}
\end{enumerate}

\ifdefined\template
\begin{shaded}
\textbf{SOLUTION:}
\ifdefined\sol
\input{solutions/flamingo2.tex}
\fi
\end{shaded}
\fi

\newpage
%%%%%%%%%%%%%%%%%%%% PROBLEM 4: Wisdom of flamingos %%%%%%%%%%%%%%%%%%%%%%

\item  \textbf{[Wisdom of Flamingos]} \pts{5} A wise flamingo has knowledge of an array $A$ of length $n$, such that $A[i] \in \{1,\ldots,k\}$ for all $i$.  (Note that the elements of $A$ are not necessarily distinct). 
You don't have direct access to $A$, but you can ask the wise flamingo \em any \em yes/no questions about it.  For example, you could ask ``If I remove $A[5]$ and swap $A[7]$ with $A[8]$, would the array be sorted?'' or ``do molecular and morphological studies support a relationship between grebes and flamingos?''

Unlike in the previous two problems, this time you did bring a paper and pencil, and your job is to write down all of the elements of $A$ in sorted order.\footnote{Note that you don't have any ability to change the array $A$ itself, you can only ask the wise flamingo about it.}  As usual, the wise flamingo charges one brine shimp per question.
\vspace{-.2cm}

\begin{center}
\begin{tikzpicture}
\node(a) {\includegraphics[width=2cm]{alice}};
\draw[black!20, fill=black!20] (8, -1) ellipse (.8cm and .15cm); 
\node[rotate=-2](b) at (8,.5) {\includegraphics[width=2.6cm]{wiseflamingo}};
\node[draw, cloud, cloud puffs=20.5, cloud ignores aspect] at (11,2.5) {$A = [6,2,4,3,3,5,2,1,2,6]$};
\node(c) at (3,2.8) {Is $7$ in the array?};
\node(d) at (5,2) {\textbf{No.}};
\node(e) at (3.5,1) {\begin{minipage}{3.5cm}\begin{center} Do you get your delightful pink color from beta-carotene?\end{center}\end{minipage}};
\node(f) at (4.5,-.2) {\textbf{Yes.}};
\draw (c) -- (a);
\draw (e) -- (a);
\draw (d) -- (b);
\draw (f) -- (b);
\end{tikzpicture}
\end{center}

\vspace{-.7cm}
\begin{enumerate}
\item\pts{5} Give a procedure that outputs a sorted version of $A$ which uses $O(k\log(n))$ brine shrimp.  You may assume that you know $n$ and $k$, although this is not necessary.

\expecting{Pseudocode \text{AND} a short English description of your algorithm; \textbf{AND} a brief explanation of why it uses $O(k \log(n))$ brine shrimp.
}
\item \pts{1 BONUS} Prove that any procedure to solve this problem must use $\Omega(k \log(n/k))$ brine shrimp.

\expecting{Nothing; this part is not required.} 
\end{enumerate}

\ifdefined\template
\begin{shaded}
\textbf{SOLUTION:}
\ifdefined\sol
\input{solutions/flamingo3.tex}
\fi
\end{shaded}
\fi

\newpage
%%%%%%%%%%%%%%%%%%%% PROBLEM 5: Feedback %%%%%%%%%%%%%%%%%%%%%%

\item  \textbf{[Please (Flamin-)Go Fill Out This Group-Work Survey]} \pts{1} 

In collaboration with Professor Shima Salehi of the Stanford Ed School and her team, we have created a short google form on your experience with group-work in this class, which is linked below. SUNet IDs will be collected, but we will only use hashes of IDs for the study, so the responses will be effectively anonymous. The form is very short, and will take $\approx 1$ minute to fill out: \url{https://forms.gle/PzTZpMBaoDjrzNdA7}. 

We really appreciate all your feedback and help with making CS161 the best possible learning experience it can be! If you would like to give more general feedback on the class as a whole, please check out the many possible options highlighted in the linked Ed post\footnote{\url{https://edstem.org/us/courses/38246/discussion/2970522}}. 

Have you submitted your answers to the google form above? 

\expecting{Yes}

\ifdefined\template
\begin{shaded}
\textbf{SOLUTION:}
\ifdefined\sol
\input{solutions/feedback.tex}
\fi
\end{shaded}
\fi

\end{enumerate}

\end{document}
