% -*- compile-command: "./build.sh" -*-
\documentclass[11pt]{tufte-handout}
\usepackage{pgf}
\usepackage[outputdir=diagrams, extension=pgf, backend=pgf, input]{diagrams-latex}
\usepackage[num=7,date=October\ 23,topic=Dynamic\ programming\ I]{algorithms-hw}
\begin{document}
\coversheet
\begin{question}[K\&T 6.4, 10 points] \label{q:consult}
You are running a consulting business, with clients on both east and
west coasts. Each month, you can run your business from an office
in either New York or San Fransisco. In month $i$, you will incur
an \emph{operating cost} of $N_i$ if you run the business out of New York;
you will incur an operating cost of $S_i$ if you run the business
out of San Fransisco (the costs can change each month depending on
the distribution of client demands).
However, if you run the business out of one city in month $i$, and
then out of the other city in month $i+1$, then you incur a fixed
\emph{moving cost} of $M$ to switch cities.
Given a sequence of $n$ months, a \emph{plan} is a sequence of $n$
locations---each one equal to either NY or SF---such that the $i$th
location indicates the city in which you will be based in the $i$th
month. The \emph{cost} of a plan is the sum of the operating costs
for each of the $n$ months, plus a moving cost of $M$ for each time
you switch cities. The plan can begin in either city.
Given a value for the moving cost $M$, and sequences of operating
costs $N_1, \dots, N_n$ and $S_1, \dots, S_n$, the problem is to
find a plan with minimum total cost.
\begin{enumerate}[label=(\alph*)]
\item Show that the following greedy algorithm does not correctly
solve this problem, by giving an instance on which it does not
return the correct answer.
\begin{algorithm*}[h]
\caption{{\sc GreedyPlan}} \label{alg:greedyplan}
\begin{algorithmic}[1]
\For{$i \gets 1$ to $n$}
\If{$N_i < S_i$}
\State Output ``NY in month $i$''
\Else
\State Output ``SF in month $i$''
\EndIf
\EndFor
\end{algorithmic}
\end{algorithm*}
In your example, say what the correct answer is and also what the
above algorithm finds.
\item Give an efficient algorithm that takes values for $n$, $M$,
and sequences of operating costs $N_1, \dots, N_n$ and $S_1,
\dots, S_n$, and returns the \emph{cost} of an optimal plan.
\item Explain how to extend your algorithm to also find the optimal
plan itself, not just its cost.
\end{enumerate}
\end{question}
\newpage
\begin{question}[5 points] \label{q:track} You are building a toy train track
out of a sequence of straight pieces laid end-to-end. Some pieces
are one unit long, and some are three units long. How many
different ways are there to build a track that is five hundred units
long? \marginnote[-3em]{\emph{\ref{q:track}}\quad\qrcode{Come\ up\ with\
a\ recurrence.\ What\ are\ your\ choices\ for\ the\ last\ track\
segment?}}
For example, there are $9$ different ways to build a track that is
$7$ units long, as illustrated below.
\begin{figure}
\begin{center}
\begin{diagram}[width=300]
import Data.List.Split (chunksOf)
segGap = 0.2
railOffset = 0.35
trackSeg n = rails <> ties
where
rails = mconcat [ rail # translateY railOffset
, rail # translateY (-railOffset)]
rail = hrule (n' - segGap) # alignL # lw veryThick # lc silver
k = 2
ties = hcat' (with & catMethod .~ Distrib
& sep .~ (1/fromIntegral k))
(replicate (k * n) tie)
# translateX (1/(2*fromIntegral k) - segGap/2)
tie = rect 0.1 1 # lw none # fc (trackColor n)
n' = fromIntegral n
trackColor 1 = black
trackColor 3 = orange
drawTrack = hsep segGap . map trackSeg
tracks :: Int -> [[Int]]
tracks n | n < 0 = []
tracks 0 = [[]]
tracks 1 = [[1]]
tracks n = map (1:) (tracks (n-1)) ++ map (3:) (tracks (n-3))
dia :: Diagram B
dia = hsep 1 . map (vsep 0.8) . chunksOf 5
$ map drawTrack (tracks 7) -- $
\end{diagram}
\end{center}
\caption{The nine ways to build a length-$7$ train track}
\label{fig:tracks}
\end{figure}
\marginnote[-10em]{\emph{\ref{q:track}}\quad\qrcode{To\
answer\ this\ you\ will\ need\ to\ write\ a\ small\ program.\ \
If\ you\ use\ Java,\ be\ sure\ to\ use\ BigInteger.}}
\end{question}
\newpage
\begin{question}[K\&T 6.3, 10 points] \label{q:graph}
Let $G = (V,E)$ be a directed, unweighted graph with nodes
$v_1, \dots, v_n$. We say that $G$ is an \emph{ordered graph} if it
has the following properties:
\begin{enumerate}[label=(\roman*)]
\item Each edge goes from a node with a lower index to a node with a
higher index. That is, every directed edge has the form $(v_i,
v_j)$ with $i < j$.
\item Every node other than $v_n$ has at least one outgoing edge.
\end{enumerate}
Given an ordered graph $G$, we want to find the \emph{longest} path
from $v_1$ to $v_n$.
\begin{enumerate}[label=(\alph*)]
\item Consider the following greedy algorithm.
\begin{algorithm*}[h]
\caption{{\sc GreedyLongestPath}} \label{alg:x}
\begin{algorithmic}[1]
\State $w \gets v_1$
\State $L \gets 0$
\While{$w \neq v_n$}
\State Choose the outgoing edge $(w, v_j)$ with the smallest
$j$
\State $w \gets v_j$
\State Increment $L$
\EndWhile
\State \Return $L$
\end{algorithmic}
\end{algorithm*}
Show that this algorithm does \emph{not} correctly solve the
problem, by giving an example of an ordered graph for which it does
not return the correct answer. Be sure to explain what the correct
answer is and what incorrect answer is returned by the algorithm.
\item Give an efficient algorithm that takes an ordered graph $G$ and
returns the length of the longest path from $v_1$ to $v_n$.
Justify its correctness and analyze its time complexity.
\marginnote{\emph{\ref{q:graph}}(b)\quad\qrcode{If\ you\ know\
the\ length\ of\ the\ longest\ path\ from\ v_j\ to\ v_n\ for\ every\ j
> i,\ can\ you\ figure\ out\ the\ length\ of\ the\ longest\ path\ from\
v_i\ to\ v_n?}}
\item Explain how to modify your algorithm so that it can also be
used to recover the longest path itself, rather than only its
length.
\end{enumerate}
\end{question}
\end{document}