\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}
\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 2} \newline 
{Spring 2023} \hfill \textbf{Due:} Wednesday, April 19 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.
\noindent

 Please list all members of your homework group and all other students in the class you have collaborated with on this homework, in accordance with the Collaboration Policy, at the beginning of each homework submission. 
 \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}  Compute the \emph{best} (that is, the smallest) upper-bound that you can on the following recurrence relations.  You may use any method we've seen in class (Master Theorem, Substitution Method, algebra, etc.)

\begin{enumerate}
\item \pts{2} $T(n) = 2T(\lfloor n/2\rfloor) + O(\sqrt{n})$, where $T(0) = T(1) = 1$.
\item \pts{2} $T(n) = T(n-2) + 1$, where $T(0) = T(1) = 1$.
\item \pts{2} $T(n) = 6T(\lfloor n/4 \rfloor) + n^2$ for $n \geq 4$, and $T(n) = 1$ for $n < 4$.
\end{enumerate}

\expecting{For each part, a statement of your answer of the form ``$T(n) = O(\_\_\_\_)$'', as well as a short justification.  You don't need to give a rigorous proof, but your justification should be convincing to the grader.}

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


%%%%%%%%%%%%%% EXERCISE 2 %%%%%%%%%%%%%%%%%%%%%%%%%

\item \pts{3} Consider the following algorithm, which takes as input an array $A$:

\begin{verbatim}
def printStuff(A):
    n = len(A)
    if n <= 4:
        return
    for i in range(n):
        print(A[i])

    printStuff(A[:(n//3)]) # recurse on the first floor(n/3) elements of A
    printStuff(A[(n//3):2*(n//3)]) # recurse on the second floor(n/3) elements of A
    return
\end{verbatim}

What is the asymptotic running time of \texttt{printStuff} on an array of length $n$?

\expecting{ The best answer you can give of the from ``The running time of \texttt{printStuff}$(n)$ is $O(\_\_\_\_)$, and a short explanation, including a clear statement of the relevant recurrence relation. }

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

%%%%%%%%%%%%%% EXERCISE 3 %%%%%%%%%%%%%%%%%%%%%%%%%

\item \pts{4} Let $T(n) = T(\lfloor \sqrt{n} \rfloor) + 1$, where $T(n_{\text{small}}) = 1$ for all $0 \leq n_\text{small} \leq 9$.  Prove formally that $T(n) = O(\log \log n)$.

You can use any method you like.  

\hint{The substitution method is a good approach!  If you do that, make sure that you clearly state your inductive hypothesis, base case, inductive step and conclusion.  You could also try the Master Theorem...but (hint hint) you might need to manipulate the recurrence relation a bit to get it to apply...}

\expecting{A formal proof.  You may assume that $n$ is $2^{2^m}$ for some positive integer $m$, if you like.}

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



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

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

\begin{enumerate}
\setcounter{enumi}{3}

%%%%%%%%%%%%%%%%%%%%%%%% Problem 4: Fish! %%%%%%%%%%%%%%%%%%%

\item \pts{6} [\textbf{Fishing.}] Plucky the Pedantic Penguin is fishing.  Plucky catches $n$ fish, but plans to keep only the $k$ largest fish and to throw the rest back.  Plucky has already named all of the fish, and has measured their length and entered it into an array $F$ of length $n$.  For example, $F$ might look like this:
\[ F = \begin{bmatrix} 
\text{(Frederick the Fish, 14.2in)}\\ \text{(Fabiola the Fish, 10in)}\\ \text{(Farid the Fish, 12.35in)} \\ \vdots \\ \text{(Felix the Fish, 6.234523in)} \\ \text{(Finlay the Fish, 6.234524in)} \end{bmatrix} \]
\begin{enumerate}

\item \pts{3} Give a simple $O(n\log(n))$-time deterministic algorithm that takes $F$ and $k$ as inputs and returns a list of the names of the $k$ largest fish. 
You may assume that the lengths of the fish are distinct. 

\textbf{Note:} Your algorithm should run in time $O(n\log(n))$ even if $k$ is a function of $n$.  For example, if Plucky wants to keep the largest $k = n/2$ fish, your algorithm should still run in time $O(n\log(n))$.

\expecting{Pseudocode \textbf{AND} a short English description of your algorithm.  You may (and, hint, may want to...) invoke algorithms we have seen in class.  You do not need to justify why your algorithm is correct or its running time. }

\item \pts{3} Give an $O(n)$-time deterministic algorithm that takes $F$ and $k$ as inputs and returns a list of the names of the $k$ largest fish.
You may assume that the lengths of the fish are distinct. 
Your algorithm should also be fundamentally different than your algorithm for part (a).  (That is, don't solve part (b) and then use that as your solution to part (a); part (a) should be easier).

\textbf{Note:} Your algorithm should run in time $O(n)$ even if $k$ is a function of $n$.  For example, if Plucky wants to keep the largest $k = n/2$ fish, your algorithm should still run in time $O(n)$.

\expecting{Pseudocode \textbf{AND} a short English description of your algorithm.  You may (and, hint, may want to...) invoke algorithms we have seen in class.  You do not need to justify why your algorithm is correct or its running time. }
\end{enumerate}

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


%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Problem 5: Dancing Ducks %%%%%%%%%%%%%%%%%%%%%%
\newpage
\item \pts{14} \textbf{[Dancing ducks.]}

You have encountered a troupe of $n$ dancing ducks who are each labeled with a number $0, \ldots, n-1$ in some order, where $n$ is a power of $2$. The $i^{th}$ duck is labeled with the number $A[i]$.

The $n$ ducks dance in a line, and they only know one type of dance move, called \texttt{Flip(A,i,j)}:  for any $i$ and $j$ such that $0 \leq i < j \leq n$, \texttt{Flip(A,i,j)} flips the order of the ducks standing in positions $i, i+1, \ldots, j-1$ in array $A$.  For example, if the ducks started out like this:
\begin{center}
\begin{tikzpicture}
\foreach \i in {0, ..., 7}
{
\node at (\i, 0) {\includegraphics[width=1cm]{duck}};
}
\begin{scope}[xshift=0.05cm, yshift=-.1cm]
\node at (-1,0) {Duck:};
\node at (0, 0) {$4$};
\node at (1, 0) {$1$};
\node at (2, 0) {$2$};
\node at (3, 0) {$3$};
\node at (4, 0) {$0$};
\node at (5, 0) {$7$};
\node at (6, 0) {$5$};
\node at (7, 0) {$6$};
\end{scope}
\begin{scope}[xshift=0.05cm, yshift=-1.3cm]
\node[blue] at (-1,0) {Index:};
\node[blue] at (0, 0) {$0$};
\node[blue] at (1, 0) {$1$};
\node[blue] at (2, 0) {$2$};
\node[blue] at (3, 0) {$3$};
\node[blue] at (4, 0) {$4$};
\node[blue] at (5, 0) {$5$};
\node[blue] at (6, 0) {$6$};
\node[blue] at (7, 0) {$7$};
\end{scope}
\end{tikzpicture}
\end{center}

then after executing \texttt{Flip(A,1,5)}, the ducks would look like this:
\begin{center}
\begin{tikzpicture}
\foreach \i in {0, ..., 7}
{
\node at (\i, 0) {\includegraphics[width=1cm]{duck}};
}
\begin{scope}[xshift=0.05cm, yshift=-.1cm]
\node at (-1,0) {Duck:};
\node at (0, 0) {$4$};
\node at (1, 0) {$0$};
\node at (2, 0) {$3$};
\node at (3, 0) {$2$};
\node at (4, 0) {$1$};
\node at (5, 0) {$7$};
\node at (6, 0) {$5$};
\node at (7, 0) {$6$};
\begin{scope}[xshift=0.05cm, yshift=-1.3cm]
\node[blue] at (-1,0) {Index:};
\node[blue] at (0, 0) {$0$};
\node[blue] at (1, 0) {$1$};
\node[blue] at (2, 0) {$2$};
\node[blue] at (3, 0) {$3$};
\node[blue] at (4, 0) {$4$};
\node[blue] at (5, 0) {$5$};
\node[blue] at (6, 0) {$6$};
\node[blue] at (7, 0) {$7$};
\end{scope}
\draw[thick, orange] (.5,.4) -- (.5,1.1) -- (4.5,1.1) -- (4.5,.4);
\node[orange] at (2.5,1.5) {These ducks were reversed.};
\end{scope}
\end{tikzpicture}
\end{center}

Executing this dance move is pretty complicated: it takes the ducks $O(j - i)$ seconds to perform \texttt{Flip(A,i,j)}. 

In this problem, you will design and analyze a duck dance (a.k.a. a sorting algorithm) that solely uses the \texttt{Flip} move (after all, it's the only dance move ducks know) such that after finishing the dance, all $n$ ducks are sorted by their labels. 

The input to your algorithm will be an array $A$ that contains the ducks' values. As an example, if the ducks were organized as pictured above after the flip, then the input array would be $A = [4,0,3,2,1,7,5,6]$.
Your algorithm can do whatever computations it wants, but the only way you can get the ducks to move is by calling \texttt{Flip(A,i,j)}, which will make them do their \texttt{Flip(A,i,j)} dance move.
The algorithm will wait until the ducks are done dancing to continue its computations.
Thus, the total running time of the algorithm includes \em both \em the time spent computing, and the time that the ducks spend dancing.


\begin{enumerate}[(a)]
\item \pts{10} 
First, you will design an algorithm that tells the ducks how to perform a dance called \texttt{Partition(A, i)}. 
For this dance, the ducks will partition themselves around the duck in position $i$, so that all ducks whose labels are smaller than the duck's label at position $i$ will end up to the left, and all the ducks whose labels are larger will end up to the right.  For example, if the ducks were initially ordered as so:
\begin{center}
\begin{tikzpicture}
\foreach \i in {0, ..., 7}
{
\node at (\i, 0) {\includegraphics[width=1cm]{duck}};
}
\begin{scope}[xshift=0.05cm, yshift=-.1cm]
\node at (-1,0) {Duck:};
\node at (0, 0) {$0$};
\node at (1, 0) {$4$};
\node at (2, 0) {$3$};
\node at (3, 0) {$2$};
\node at (4, 0) {$1$};
\node at (5, 0) {$7$};
\node at (6, 0) {$6$};
\node at (7, 0) {$5$};
\end{scope}
\begin{scope}[xshift=0.05cm, yshift=-1.3cm]
\node[blue] at (-1,0) {Index:};
\node[blue] at (0, 0) {$0$};
\node[blue] at (1, 0) {$1$};
\node[blue] at (2, 0) {$2$};
\node[blue] at (3, 0) {$3$};
\node[blue] at (4, 0) {$4$};
\node[blue] at (5, 0) {$5$};
\node[blue] at (6, 0) {$6$};
\node[blue] at (7, 0) {$7$};
\end{scope}
\end{tikzpicture}
\end{center}
then after executing \texttt{Partition(A,3)}, the ducks partition themselves around the duck in position 3, whose label is 2.  The resulting ducks formation could look like this:
\begin{center}
\begin{tikzpicture}
\foreach \i in {0, ..., 7}
{
\node at (\i, 0) {\includegraphics[width=1cm]{duck}};
}
\begin{scope}[xshift=0.05cm, yshift=-.1cm]
\node at (0, 0) {$1$};
\node at (1, 0) {$0$};
\node at (2, 0) {$2$};
\node at (3, 0) {$5$};
\node at (4, 0) {$6$};
\node at (5, 0) {$3$};
\node at (6, 0) {$7$};
\node at (7, 0) {$4$};
\node[orange](a) at (2,2) {Goal: The other ducks should partition around this duck.};
\draw[thick, orange, ->] (a) to (2,1);
\end{scope}
\begin{scope}[xshift=0.05cm, yshift=-1.3cm]
\node[blue] at (-1,0) {Index:};
\node[blue] at (0, 0) {$0$};
\node[blue] at (1, 0) {$1$};
\node[blue] at (2, 0) {$2$};
\node[blue] at (3, 0) {$3$};
\node[blue] at (4, 0) {$4$};
\node[blue] at (5, 0) {$5$};
\node[blue] at (6, 0) {$6$};
\node[blue] at (7, 0) {$7$};
\end{scope}
\end{tikzpicture}
\end{center}
Notice that it doesn't matter what order the smaller ducks and larger ducks are in.

Give an algorithm that instructs the ducks to implement \texttt{Partition} that runs in total time $O(n \log n)$. Remember, you can only move the ducks around with calls to \texttt{Flip}. 

\hint{Try divide-and-conquer.}

\expecting{
 Pseudocode \textbf{AND} a clear English explanation of what your algorithm is doing.
Additionally, an informal justification of the running time. You may appeal to the master theorem if it is relevant. 
}

\item \pts{1} 
You are excited about the \texttt{Partition} algorithm from part (a), because it allows you to tell the ducks how to perform a dance called \texttt{Sort()}, which puts the ducks in sorted order.  The algorithm is as follows:

\begin{verbatim}
def Sort(A):
    //A is an array of length n, with the positions of the n ducks
    //Assume that n is a power of 2.

    //base case:
    if n == 1:
        return
 
    //get the index of the median, using the Select algorithm from lecture 4
    i = Select(A,n/2)

    //tell the ducks to partition themselves around the i'th duck:
    Partition(A,i)

    //recurse on both the left and right halves of the duck array.
    Sort(A[:n/2])
    Sort(A[n/2:])
\end{verbatim}

That is, this algorithm first partitions the ducks around the median, which puts the smaller-labeled ducks on the left and the larger-labeled ducks on the right.  Then it recursively sorts the smaller-labeled ducks and the larger-labeled ducks, resulting in a sorted list.

Let $T(n)$ be the running time of \texttt{Sort(A)} on an array $A$ of length $n$.  Write down a recurrence relation that describes $T(n)$.

\expecting{A recurrence relation of the form $T(n) = a \cdot T(n/b) + O(\text{something...})$, and a short explanation.}

\item \pts{3} Explain, without appealing to the master theorem, why the running time of \texttt{Sort(A)} is $O(n \log^2 n)$ on an array of length $n$.  (Note: ``$\log^2n$'' means $(\log n)^2$).  

If it helps, you may ignore the big-Oh notation in your answer in part (b). That is, if your answer in part (b) was $T(n) = a T(n/b) + O(something)$, then you may drop the big-Oh and assume that your recurrence relation is of the form
$T (n) = a T (n/b) + something$. You may assume that $T(1) \leq 1$, $T(2) \leq 2$. Recall that we are assuming that $n$ is a power of $2$.

\hint{Either the tree method or the substitution method is a reasonable approach here.}

\expecting{An explanation.  You do not need to give a formal proof, but your explanation should be convincing to the grader.  You should \textbf{NOT} appeal to the master theorem, although it's fine to use the ``tree method'' that we used to prove the master theorem.}

\end{enumerate}


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


\end{enumerate}

\end{document}
