\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{decorations.pathreplacing, shapes,positioning}
\usepackage{wrapfig}
\usepackage{algorithmic}
\usepackage{enumerate}
\usepackage{wasysym}
\usepackage{framed}
\usepackage{float}
\usepackage{hyperref}
\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 6} \newline 
{Spring 2023} \hfill \textbf{Due:} Wednesday, May 24 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  


\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{8} Let $A$ be an array of length $n$ containing real numbers.  A \em longest increasing subsequence \em (LIS) of $A$ is a sequence of indices $0 \leq i_1 < i_2 < \ldots i_\ell < n$ such that $A[i_1] < A[i_2] < \cdots < A[i_\ell]$ and $\ell$ is as large as possible.  For example, if 
$A = [6,3,2,5,6,4,8]$, then one LIS is $i_1 = 1, i_2 = 3, i_3 = 4, i_4 = 6$, which corresponds to the increasing values $3,5,6,8$.  (Notice that a LIS doesn't need to be unique).

In the following parts, we'll walk through the recipe that we saw in class for coming up with DP algorithms, in order to develop an $O(n^2)$-time algorithm for finding an LIS. 
\begin{enumerate}
\item\pts{2} \textbf{(Identify optimal sub-structure and a recursive relationship).}  We'll come up with the sub-problems and recursive relationship for you, although you will have to justify it.  Let $D[i]$ be the length of the longest increasing subsequence of $[A[0], \ldots, A[i]]$ that ends on $A[i]$.
Explain why
\[ D[i] = \max\left(\{ D[k] + 1\,:\, 0 \leq k < i, A[k] < A[i] \} \cup \{1\} \right). \]
That is, $D[i]$ is the maximum of ``$1$'' and the values $D[k] + 1$, where $k$ ranges over all values between $0$ and $i-1$ so that $A[k] < A[i]$.

\expecting{A short informal explanation (a paragraph or so).  You do not need to write a formal proof.}

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

\item\pts{3} \textbf{(Develop a DP algorithm to find the value of the optimal solution)} Use the relationship above to design a dynamic programming algorithm that returns the length of the longest increasing subsequence.  Your algorithm should run in time $O(n^2)$ and should fill in the array $D$ defined above.

\expecting{Just pseudocode.  No justification is required.}

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

\item \pts{3} \textbf{(Adapt your DP algorithm to return the optimal solution)} Adapt your algorithm above to return the values of the LIS instead of its length.  Your algorithm should run in time $O(n^2)$.

Note that you should return the values of the LIS: for example, for the array $A = [6,3,2,5,6,4,8]$ given at the beginning of this question, if your LIS is $[1,3,4,6]$, you should return the corresponding values $[3,5,6,8]$.

\expecting{Pseudocode \textbf{AND} a short English explanation of what your algorithm is doing.  You do not need to justify correctness or runtime.}


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

\end{enumerate}

\textbf{Note:} Actually, there is an $O(n\log(n))$-time algorithm to find an LIS, which is faster than the DP solution in this exercise!  



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

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

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

%%%%%%%%%%%%%%%%%%%%%%%% Problem 1 : MinElementSum  %%%%%%%%%%%%%%%%%%%

\item\pts{7} (\textbf{Improving on Divide-and-Conquer}) 
Consider the following problem, \textsc{MinElementSum}.
\begin{quote}
\textsc{MinElementSum}$(n,S)$:
Let $S$ be a set of positive integers, and let $n$ be a non-negative integer.  Find the minimal number of elements of $S$ needed to write $n$ as a sum of elements of $S$. (Note: it's okay to use an element of $S$ more than once, but this counts towards the number of elements).  If there is no way to write $n$ as a sum of elements of $S$, return \texttt{None}.
\end{quote}

For example, if $S = \{1,4,7\}$ and $n = 10$, then we can write $n = 1 + 1 + 1 + 7$ and that uses four elements of $S$.  The solution to the problem would be ``4."  On the other hand if $S = \{4,7\}$ and $n=10$, then the solution to the problem would be ``\texttt{None},'' because there is no way to make $10$ out of $4$ and $7$.

Your friend has devised a divide-and-conquer algorithm to solve \textsc{MinElementSum}.  Their pseudocode is below.
\begin{verbatim}
def minElementSum(n, S):
     if n == 0:
         return 0
     if n < min(S):
         return None
     candidates = []
     for s in S:
         cand = minElementSum( n-s, S )
         if cand is not None: 
              candidates.append( cand + 1 )
     if len(candidates) == 0:
         return None
     return min(candidates) 
\end{verbatim}

Your friend's algorithm correctly solves \textsc{MinElementSum}.  Before you start doing the problems on the next page, it would be a good idea to walk through the algorithm and to understand what this algorithm is doing and why it works.  

\vfill \hfill [Questions on next page]
\newpage

\begin{enumerate}
\item \pts{1} Argue that for $S = \{1,2\}$, your friend's algorithm has exponential running time.  (That is, running time of the form $2^{\Omega(n)}$).   

\hint{You may use the fact (stated in class) that the Fibonacci numbers $F(n)$ satisfy $F(n) = 2^{\Omega(n)}$.}

\expecting{
\begin{itemize}
\item A recurrence relation that the running time of your friend's algorithm satisfies when $S = \{1,2\}$.
\item A convincing argument that the closed form for this expression is $2^{\Omega(n)}$.  You do not need to write a formal proof.  \end{itemize}}

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

\item \pts{3} Turn your friend's algorithm into a top-down dynamic programming algorithm.  
Your algorithm should take time $O(n|S|)$.

\hint{Add an array to the pseudocode above to prevent it from solving the same sub-problem repeatedly.}


\expecting{\begin{itemize} 
\item Pseudocode \textbf{AND} a short English description of the idea of your algorithm.
\item An informal justification of the running time.\end{itemize}}

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

\item \pts{3} Turn your friend's algorithm into a bottom-up dynamic programming algorithm.  
Your algorithm should take time $O(n|S|)$.

\hint{Fill in the array you used in part (b) iteratively, from the bottom up.}

\expecting{\begin{itemize} 
\item Pseudocode \textbf{AND} a short English description of the idea of your algorithm.
\item An informal justification of the running time.\end{itemize}}


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


\end{enumerate}
%%%%%%%%%%%%%%%%%%%%% PROBLEM 3: Spring flowers! %%%%%%%%%%%%%%%%%%%%%

\newpage
\item \pts{12} \textbf{[Spring flowers!]}
It's spring!  You are planting your flower garden, which 
has $n$ spots arranged in a line.  Different spots in the garden will result in different quality flowers, measured by fragrance: suppose that the location $i$ will result in flowers of frangrance $F[i]$, where $F[i]$ is a positive integer.  Further, you cannot plant two plants directly next to each other, because they will compete for resources and wilt.  
Your goal is to create the most fragrant flower garden possible (summed up over all of the flowers in the garden).  

\textbf{For example,} if the input was
$F = [21,4,6,20,2,5],$
then you should plant flowers in the pattern
\begin{center}
    \begin{tikzpicture}
\foreach \i in {1,2,3,4,5,6}
{
\draw (\i -1, 0) rectangle (\i, 1);
}
\foreach \i in {1,4,6}
{
\node at (\i -.5, .5) {\includegraphics[width=.8cm]{flower}};
}
\end{tikzpicture}
\end{center}
and you would obtain fragrance $21 +20+5 = 46$.  You would \textbf{not} be allowed to plant flowers in the pattern
\begin{center}
\begin{tikzpicture}
\foreach \i in {1,2,3,4,5,6}
{
\draw (\i -1, 0) rectangle (\i, 1);
}
\foreach \i in {1,2,4,6}
{
\node at (\i -.5, .5) {\includegraphics[width=.8cm]{flower}};
}
\end{tikzpicture}
\end{center}
because there are two flowers next to each other. 

You will first
design a dynamic programming algorithm which runs in time $O(n)$, takes as input the array $F$, and returns the maximum fragrance possible given $F$.  Do this by answering the two parts below.

\begin{enumerate}
	\item \pts{3} What sub-problems will you use in your dynamic programming algorithm?  What is the recursive relationship satisfied between the sub-problems? 

\expecting{\begin{itemize}
\item A clear description of your sub-problems.
\item A recursive relationship that they satisfy, along with any necessary base case(s).
\item An informal justification that the recursive relationship is correct.
\end{itemize}}
	
\ifdefined\template
\begin{shaded}
\textbf{SOLUTION:}
\ifdefined\sol
\input{solutions/plantA.tex}
\fi
\end{shaded}
\fi
	
	\item \pts{3} Write pseudocode for your algorithm.  Your algorithm should take as input the array $F$, and return a single number which is the maximum amount of fragrance possible.  Your algorithm does not need to output the optimal way to plant the flowers.

\expecting{Clear pseudocode. 
 You do not need to justify that your algorithm is correct, but correctness should follow from your reasoning in part (a).}


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

\item \pts{6} You're pretty happy with your approach from the previous parts, but you realized that you forgot about the cost of planting the flowers!  Now there's also a length-$n$ array $C$, so that $C[i]$ is a positive integer representing the cost of planting a flower in position $i$.  You have a total budget of $B$.  Design a DP algorithm that runs in time $O(nB)$, takes as input $F$, $C$, and $B$, and returns the maximum fragrance possible, given the additional constraint that you can't exceed your budget $B$: that is,
\[ \sum_{i=1}^n C[i] \cdot \mathbf{1}[\text{there is a flower in position $i$}] \leq B. \]
Your algorithm does not need to return how to plant the flowers.

Note that you are still not allowed to plant two flowers next to each other.

\hint{Consider filling in a two-dimensional array.}

\expecting{A clear description of your sub-problems and the recursive relationship that they satisfy, pseudocode, and a short justification for the runtime.}

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

\end{enumerate}


%%%%%%%%%%%%%%%%%% Problem 4: fish fish eat eat fish %%%%%%%%%%%%%%


\newpage
\item \pts{6} \textbf{[Fish fish eat eat fish.] }
Plucky the Pedantic Penguin enjoys fish, and wants to catch as many fish as possible from two nearby Lakes named $A$ and $B$. They have discovered that on some days the fish supply is better in Lake A, and some days the fish supply is better in Lake B.
Plucky has access to two tables $A$ and $B$, where $A[i]$ is the number of fish they can catch in Lake A on day $i$, and $B[i]$ is the number of fish they can catch in Lake B on day $i$, for $i=0,\ldots,n-1$.    

If Plucky is at Lake $A$ on day $i$ and wants to be at Lake $B$ on day $i+1$, they may pay $L$ fish to a polar bear who can take them from Lake $A$ to Lake $B$ overnight; the same is true if they want to go from Lake $B$ back to Lake $A$. 
The polar bear does not accept credit, so \textbf{Plucky  must pay \em before \em they travel}. (And if they cannot pay, they cannot travel).

Assume that when day $0$ begins, Plucky is at Lake $A$, and they have zero fish.  Also assume that $A[i]$ and $B[i]$ are positive integers for $i =0,1,\ldots,n-1$ and that $L$ is also a positive integer. 


\fbox{
\begin{minipage}{0.9\textwidth}
For example, suppose that $n=3$, $L=3$, and that $A$ and $B$ are given by
\[ A = [5,2,3] \qquad B = [2,7,4]. \]
Then Plucky might do:
\begin{center}
\begin{tikzpicture}
\node at (1, .6) {Lake $A$};
\node at (7, .6) {Lake $B$};
\begin{scope}[yscale=.8]
\draw [decorate,decoration={brace,amplitude=10pt},xshift=-4pt,yshift=0pt]
(0,-2.4) -- (0,.4)node [black,midway,xshift=-30pt] {Day 0};
\node(p0) at (1,0) {\includegraphics[width=.5cm]{plucky}};
\node(p1) at (1,-2) {\includegraphics[width=.5cm]{plucky}};
\node at (1.7, 0) {$0$ fish};
\node at (1.7, -1.7) {$5$ fish};
\draw[dashed] (p0) to node[right,pos=0.5] {$+5$} (p1);
\end{scope}
\begin{scope}[yscale=.8,yshift=-3cm]
\draw [decorate,decoration={brace,amplitude=10pt},xshift=-4pt,yshift=0pt]
(0,-2.4) -- (0,.4)node [black,midway,xshift=-30pt] {Day 1};
\node(p2) at (7,0) {\includegraphics[width=.5cm]{plucky}};
\node(p3) at (7,-2) {\includegraphics[width=.5cm]{plucky}};
\node at (7.7, 0) {$2$ fish};
\node at (7.7, -2) {$9$ fish};
\draw[dashed] (p2) to node[right,pos=0.5] {$+7$} (p3);
\end{scope}
\begin{scope}[yscale=0.8, yshift=-6cm]
\draw [decorate,decoration={brace,amplitude=10pt},xshift=-4pt,yshift=0pt]
(0,-2.4) -- (0,.4)node [black,midway,xshift=-30pt] {Day 2};
\node(p4) at (7,0) {\includegraphics[width=.5cm]{plucky}};
\node(p5) at (7,-2) {\includegraphics[width=.5cm]{plucky}};
\node at (7.7, 0) {$9$ fish};
\node at (7.7, -2) {$13$ fish};
\draw[dashed] (p4) to node[right,pos=0.5] {$+4$} (p5);
\end{scope}
\draw[dashed] (p1) to node[above,pos=0.5] {$-3$} (p2);
\end{tikzpicture}
\end{center}

So Plucky's total fish at the end of day $n-1=2$ is $13$.
\end{minipage}
}

In this question, you will design an $O(n)$-time dynamic programming algorithm that finds the maximum number of fish that Plucky can have at the end of day $n-1$.   Do this by answering the two parts below.


\begin{enumerate}
	\item \pts{3} What sub-problems will you use in your dynamic programming algorithm?  What is the recursive relationship which is satisfied between the sub-problems? 

\expecting{\begin{itemize}
\item A clear description of your sub-problems.
\item A recursive relationship that they satisfy, along with a base case.
\item An informal justification that the recursive relationship is correct.
\end{itemize}}

\ifdefined\template
\begin{shaded}
\textbf{SOLUTION:}
\ifdefined\sol
\input{solutions/pluckyA.tex}
\fi
\end{shaded}
\fi
	
	\item \pts{3} Design a dynamic programming algorithm that takes as input $A,B,L$ and $n$, and in time $O(n)$ returns the maximum number of fish that Plucky can have at the end of day $n-1$.
	
\expecting{Clear pseudocode, and a justification of why it runs in time $O(n)$.  You do not need to justify the correctness of your pseudocode, but it should follow from your reasoning in part (a).}

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

\newpage


%%%%%%%%%%%%% EthiCS: Vaccine Distribution %%%%%%%%%%%%%%%

\item \pts{4} \textbf{[EthiCS: Vaccine Distribution]}

In all of the problems above (and in general in the sorts of DP problems we solve on pedagogical CS161 HW assignments), we have a very tidy set of options and constraints.  In the flower-bed problem, we want to maximize ``fragrance'' subject to not having two flowers next to each other; in Plucky's fishing problem, we want to maximize fish subject to Plucky being able to pay the polar bear.  However, the real world is not so tidy.  For example, imagine it is early 2021, and you are deciding how to allocate a limited number of COVID-19 vaccines.  At a first pass, it might look a bit like our optimization problems with options and constraints.  We'd like to optimize public health, by vaccinating some people, given a limited amount of vaccine and with the additional constraint of being equitable.  

We can see that our goals and constraints are not as easy to mathematically formulate as with our tidy story problems above, but in order to come up with a good policy, we need to try!  How might you define the goal of ``maximizing population health'' and the constraint of ``equitable access'' for vaccine distribution? What other factors do you need to consider that aren't necessarily represented in the problem formulation of optimization and constraints? 

Of course, there is not a right answer to this question!  What we are looking for is a serious attempt to think about how you might model this, and what the issues might be.

\expecting{(1) A paragraph or so describing what might contribute to formal definitions of ``population health'' and ``equitable access,'' and (2) 2-3 sentences describing  at least two other factors you might need to consider about vaccine distribution when designing a policy.}

(Optional Reading: \href{https://www.nature.com/articles/s43856-021-00023-1}{Nature} and \href{https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8580866/}{NIH} have articles about research that tested different vaccine distribution strategies)



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

\newpage

%%%%%%%%%%%% Feedback %%%%%%%%%%%%%%%%%

\item \textbf{[Please 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/qW9vRAyFGHQvg1UD9}. 

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

\newpage


\end{enumerate}



\end{document}
