\documentclass[12pt]{article}
\usepackage[margin=1in]{geometry} 
\usepackage{amsmath,amsthm,amssymb,amsfonts}
\usepackage[table,dvipsnames]{xcolor}
\usepackage{graphicx,fancyhdr,algorithm,algorithmic}
\usepackage[space]{grffile}
\usepackage{titlesec}
\usepackage{multicol}
\usepackage{enumitem} 
\usepackage{tikz}
\usepackage{tikz-qtree}
\usetikzlibrary{arrows,automata}
\usepackage{thmtools}


\cfoot{\thepage}
\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\headwidth}{\textwidth}
\renewcommand{\footrulewidth}{0.4pt}

%some custom commands for problem 2
%want some nice colors
\definecolor{darkred}{rgb}{.87,0,0}
\definecolor{niceblue}{rgb}{.392,.584,.929}
%change the font, change the color, and raise the first word's letters slightly
\newcommand{\firstword}[1]{\textsf{{\color{darkred}{\raisebox{.3em}{#1}}}}}
\newcommand{\secondword}[1]{\textsf{{\color{niceblue}{#1}}}}


\theoremstyle{definition}
\newtheorem{problem}{Problem}
\newtheorem{claim}{Claim}
\newtheorem{definition}{Definition}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{observation}{Observation}
\newtheorem{question}{Problem}

\newenvironment{solution}{\bigskip\noindent{\it Solution.}  \ignorespaces}{\hfill\qed}

\usepackage{hyperref}
\hypersetup{
    colorlinks=true,
    linkcolor=blue,
    filecolor=magenta,      
    urlcolor=cyan,
}
\urlstyle{same}
\PassOptionsToPackage{hyphens}{url}
\newcommand{\homework}[6]{
   \pagestyle{myheadings}
   \thispagestyle{plain}
   \newpage
   \setcounter{page}{1}
   \noindent
   \begin{center}
   \framebox{
      \vbox{\vspace{2mm}
    \hbox to 6.28in { {\bf CS 256:~Algorithm Design and Analysis \hfill} }
       \vspace{6mm}
       \hbox to 6.28in { {\Large \hfill #1 \normalsize{(#2)}  \hfill} }
       \vspace{6mm}
     \hbox to 6.28in { {\it Instructor: #3 \hfill } }
   }
   }
   \end{center}
   \markboth{#1}{#1}
   \vspace*{4mm}
}


\declaretheoremstyle[
    headfont=\bfseries\sffamily\color{ForestGreen!70!black}, bodyfont=\normalfont,
    mdframed={
        linewidth=2pt,
        rightline=false, topline=false, bottomline=false,
        linecolor=ForestGreen, backgroundcolor=ForestGreen!5,
    }
]{thmgreenbox}
\declaretheoremstyle[
    headfont=\bfseries\sffamily\color{Red!70!black}, bodyfont=\normalfont,
    mdframed={
        linewidth=2pt,
        rightline=false, topline=false, bottomline=false,
        linecolor=Red, backgroundcolor=Red!5,
    }
]{thmredbox}
\declaretheorem[style=thmgreenbox, name=Hint,numbered=no]{hint}
\declaretheorem[style=thmredbox, name=Note,numbered=no]{warning}


\begin{document}
\homework{Assignment 5}{due 04/10/24}{Sam McCauley}{}{}{}

\bigskip
For this assignment, you are allowed to work in groups of 2 or 3.  If you do, please write the names of the students in this group here:

\begin{itemize}
	\item Student 1
	\item Student 2
	\item Student 3
\end{itemize}

\bigskip
\noindent
{\bf Note on Dynamic Programs.} For full credit on a dynamic program, you must clearly state the following parts.
\begin{enumerate}[ leftmargin=*, noitemsep, label = (\alph*)]

\item {\em Subproblem definition:}  your subproblem must have an optimal substructure. 

\item {\em Recurrence:}  how should the next subproblem be computed using the previous ones? This is the core of your algorithm and its correctness.
A less ideal alternative to a recurrence is clear pseudocode for the final iterative dynamic-programming algorithm. 
\item {\em Base case(s):}  you need to start somewhere!  

\item {\em Final output:}  in terms of your subproblem.

\item {\em Memoization data structure:}  this is often obvious but should not be skipped.

\item {\em Evaluation order:}  describes the dependencies between the subproblems.

\item {\em Time and space analysis.} 
\end{enumerate}

For this assignment, these are sufficient to argue correctness (that is to say, if you explain why the above parts are correct, that's sufficient to show that your algorithm works properly).

\newpage
\begin{question}(Erickson 3.6)
  Solving part (a) is sufficient for full credit on this problem; part (b) is extra credit.  

  \bigskip

  A shuffle of two strings  $X$ and  $Y$ is formed by interspersing the characters into a new string, keeping the characters of  $X$and  $Y$in the same order.For example, the string \textsf{BANANAANANAS} is a shuffle of the strings \textsf{\color{darkred} BANANA} and \textsf{\color{niceblue} ANANAS} in several different ways. 

  \bigskip

  %here's some latex for you!
  %the commands \firstword and \secondword are homemade commands, defined at the top
  %of the document.  The percent signs % are comments---but here they're used at the end
  %of the line to comment out the invisible "nextline" at the end of the line---much of the following
  % is on the same line.
  %\hspace{\fill} balances horizontal space---think of it as "pushing out" with equal force on either side
  \hspace{\fill}~
  \firstword{BANANA}\secondword{ANANAS}~
  \hspace{\fill}~
  \firstword{BAN}%
  \secondword{ANA}%
  \firstword{ANA}%
  \secondword{NAS}~
  \hspace{\fill}~
  \firstword{B}%
  \secondword{AN}%
  \firstword{AN}%
  \secondword{A}%
  \firstword{A}%
  \secondword{NA}%
  \firstword{NA}%
  \secondword{S}~
  \hspace{\fill}

  \bigskip

  Similarly, the strings \textsf{PRODGYRNAMAMMIINCG} and \textsf{DYPRONGARMAMMICING} are both shuffles of \textsf{\color{niceblue} DYNAMIC} and \textsf{\color{darkred} PROGRAMMING}:

  \bigskip
  \hspace{\fill}
  \firstword{PRO}%
  \secondword{D}%
  \firstword{G}%
  \secondword{Y}%
  \firstword{R}%
  \secondword{NAM}%
  \firstword{AMMI}%
  \secondword{I}%
  \firstword{N}%
  \secondword{C}%
  \firstword{G}
  \hspace{\fill}
  \secondword{DY}%
  \firstword{PRO}%
  \secondword{N}%
  \firstword{G}%
  \secondword{A}%
  \firstword{R}%
  \secondword{M}%
  \firstword{AMM}%
  \secondword{IC}%
  \firstword{ING}~
  \hspace{\fill}
  \bigskip


  \begin{enumerate}[label = (\alph*)]
  \item Given three strings $A[1..m]$, $B[1..n]$, and $C[1..m+n]$, describe and analyze an algorithm to determine whether $C$ is a shuffle of $A$ and $B$.

	  \begin{solution}
	  \end{solution}

	  \bigskip
	  \bigskip
  \item \textbf{(Extra credit: 5 pts)} A \textbf{smooth} shuffle of $X$ and $Y$ is a shuffle of $X$ and $Y$ that never uses more than two consecutive symbols of either string. For example,
    \begin{itemize}[itemsep=12pt]
      \item 
        \firstword{PR}%
        \secondword{D}%
        \firstword{O}%
        \secondword{Y}%
        \firstword{G}%
        \secondword{NA}%
        \firstword{RA}%
        \secondword{M}%
        \firstword{MM}%
        \secondword{I}%
        \firstword{I}%
        \secondword{C}%
        \firstword{NG}
        is a smooth shuffle of the strings \textsf{\color{niceblue}{DYNAMIC}} and \textsf{\color{darkred}{PROGRAMMING}}.
      \item 
        \firstword{DY}%
        \secondword{PR}%
        \firstword{N}%
        \secondword{OGR}%
        \firstword{A}%
        \secondword{A}%
        \firstword{M}%
        \secondword{MM}%
        \firstword{IC}%
        \secondword{ING}
        is a shuffle of \textsf{\color{darkred}{DYNAMIC}} and \textsf{\color{niceblue}{PROGRAMMING}}, but it is not a smooth shuffle (because of the substrings \textsf{OGR} and \textsf{ING}).
      \item 
        \firstword{XX}%
        \secondword{X}%
        \firstword{X}%
        \secondword{X}%
        \firstword{X}%
        \secondword{XX}%
        \firstword{XX}%
        \secondword{XX}%
        \firstword{XX}%
        \secondword{X}%
        \firstword{X}%
        \secondword{X}%
        \firstword{XX}
        is a smooth shuffle of the strings \textsf{\color{darkred}{XXXXXXX}} and \textsf{\color{niceblue}{XXXXXXXXXXX}}.
      \item There is no smooth shuffle of the strings \textsf{\color{darkred}{XXXX}} and \textsf{\color{niceblue}{XXXXXXXXXXXX}}.
    \end{itemize}
    Describe and analyze an algorithm to decide, given three strings $X$, $Y$,and $Z$, whether $Z$ is a smooth shuffle of $X$ and $Y$.

	\begin{hint}
	What do you need to change in order to build up a smooth shuffle rather than a normal shuffle?  What do you need to keep track of to ensure that you can make this distinction?
\end{hint}
\end{enumerate}
  
\end{question}
\begin{solution}
\end{solution}



\newpage
\begin{question}(From Steve Skiena's {\em Algorithm Design Manual}) Consider the problem of storing $n$ books
on shelves in a library. The order of the books is fixed by the
cataloging system and so cannot be rearraged. 
Let book $b_i$ have thickness $t_i$ and height $h_i$, for $1 \leq i \leq n$. Let the length of each bookshelf at this library be $L$.
Suppose we have the freedom to adjust the height of each shelf to fit the tallest book on it. The cost of a particular layout is the sum, over each shelf, of the height of the largest book on 
that shelf.  (So if shelf $1$ has books with heights $(1, 5, 3)$ and shelf $2$ has books with heights $(2,4)$, the total cost is $5 + 4 = 9$.)

\begin{enumerate}[label = (\alph*),  leftmargin=*]
\item Give an example to show that the greedy algorithm of stuffing each shelf as full as possible (that is, fill the first shelf with as many books as possible until book $b_i$ does not fit, and then repeat the same process on subsequent shelves) does not always give the minimum overall height.  

\item Give a dynamic programming algorithm that computes the height of the optimal arrangement, and analyze its time and space complexity. 

		\begin{hint}
		We have done a similar
example in class with a different cost function and constraints.
\end{hint}
\end{enumerate}

\end{question} 
\begin{solution}
\end{solution}


\newpage

\begin{question}
Two friends Rosa and Beth are planning a hike to the top of a mountain.  There are $n$ lookout points situated at varying points on the mountain (including one at the top), and an extensive network of trails connecting these lookout points.\footnote{Note that we don't use the specific trail layout in this problem: we just use the distance between any two lookout points.  Basically: assume there is some path from any lookout point to any other.}

Rosa and Beth want to find the shortest path from the base of the mountain to the top of the mountain under two constraints.  First, Rosa and Beth want to (between the two of them) visit all $n$ lookout points: any lookout point $i$ should either be on Rosa's route or Beth's route.  
Second, neither wants to backtrack: if Rosa visits lookout point $i$, Rosa's next lookout point should be at a higher elevation.  Similarly, when Beth visits some lookout point $j$, Beth's next lookout point should be at a higher elevation.

Assume that the $n$ lookout points are given in sorted order of elevation and that there are no ties (so lookout point $i$ is higher than lookout point $k$ when $i > k$).  

You are given the following input: for each pair of lookout points $x, y$, you are given the distance $d(x,y)$ to hike from lookout point $x$ to lookout point $y$.  Give an algorithm to find the shortest \emph{total} path length (i.e.\ the sum of Rosa's path length and Beth's path length) through the mountain such that (1) Rosa or Beth visit all lookout points, and (2) the path Rosa takes, and the path Beth takes, each visit lookout points in increasing order.
Both paths start at lookout point $1$, and end at lookout point $n$ (lookout point $n$ is at the top of the mountain).\footnote{This means that both Rosa and Beth visit lookout points $1$ and $n$.  Any other lookout point will only be visited by one of them.}

Give an $O(n^2)$ dynamic programming algorithm to find the optimal pair of paths, minimizing the total distance hiked in sum by Rosa and Beth  (In the ``time and space'' section please explain why your algorithm is $O(n^2)$.)

\end{question}

\begin{solution}


\begin{enumerate}[ leftmargin=*, label = (\alph*)]

	\item {\bf Subproblem definition:}  
		\begin{hint}
			Use the following subproblem definition.  You do not need to create your own subproblem for this problem.  (If you want to change this that's OK---but there is a correct answer that uses this subproblem definition.)
		\end{hint}

		Entry $(i,j)$ in the dynamic programming table represents two paths such that Rosa's path is from $1$ to $i$; Beth's path is from $1$ to $j$, and every vertex from $1$ to $\max\{i,j\}$ is visited by one of the two paths.

Let $S(i,j)$ be the smallest total length (sum of the two paths) of Rosa and Beth's path satisfying these constraints.

(We do not use $S(i,i)$.)

	\item {\bf Recurrence:}  

		\begin{hint}
			First, let's say that either $i > j+1$, or $j > i+1$.  What is the recurrence for $S(i,j)$?  (This recurrence is unusually short.)

			Then, let's say that $i = j+1$ or $j = i+1$.  What is the recurrence for $S(i,j)$?
		\end{hint}


\item {\bf Base case(s):}  

\item {\bf Final output:}  

\item {\bf Memoization data structure:}  

\item {\bf Evaluation order:}  

\item {\bf Time and space analysis}  
	\begin{hint}
		For the time analysis, treat the total time of the two cases in your recurrence separately.
	\end{hint}

\end{enumerate}

\end{solution}


\newpage
\begin{warning}
	Problem~\ref{trading} relies on material we will not see until Monday, 04/08/24.
\end{warning}
\begin{question}[KT 6.13]
	\label{trading}
	Consider a firm that trades shares in $n$ different companies. For each pair $i \neq j$, they maintain a trading rate $r_{ij}$, meaning that one share of $i$ trades for $r_{ij}$ shares of $j$. Here we allow the rate $r$ to be fractional; that is, $r_{ij} = \frac 23$ means that you can trade three shares of $i$ to get two shares of $j$.

	A trading cycle for a sequence of shares $i_1, i_2, \dots, i_k, i_1$ consists of successively trading shares in company $i_1$ for shares in company $i_2$, then shares in company $i_2$ for shares $i_3$, and so on, finally trading shares in $i_k$ back to shares in company $i_1$.\footnote{If it helps, you can think about trading different curriences: suppose that 1 U.S. (item $i$)
	dollar buys 0.7 British pound (item $j$), then $r_{ij} =1/0.7 = 10/7$.}

	After such a sequence of trades, one ends up with shares in the same company $i_1$ that one starts with. Trading around a cycle, in practice, is usually a bad idea, as you tend to end up with fewer shares than you started with. But occasionally, for short periods of time, there are opportunities to increase shares. 

	We will call such a cycle an {\em opportunity cycle}, if trading along the cycle {\em increases} the number of shares. This happens exactly if the product of the ratios along the cycle is above $1$. In particular, a sequence of trades $i_1, i_2, \dots, i_k, i_1$ form an opportunity cycle if $r_{i_1, i_2} \cdot r_{i_2, i_3} \cdots  r_{i_k, i_1} > 1$.

	In analyzing the state of the market, a firm engaged in trading would like to know if there are any opportunity cycles.
Give an efficient algorithm that determines whether or not such an opportunity cycle exists.  

\begin{hint}
	Reduce this problem to a problem we have discussed in class.  A reduction from a problem $A$ to a problem $B$ means you take an input instance of $A$ and turn it into an input instance of problem $B$.  

	\textbf{This means that your solution does not need to have a dynamic program.}  Instead, describe how to use a dynamic programming algorithm we already know from class to describe this problem.  How can you transform an instance of the above trading problem into an instance of a problem we've already seen?
\end{hint}


\end{question}
\begin{solution}
\end{solution}

\end{document}



