% -*- 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\ 25,topic=Dynamic\ programming\ I]{algorithms-hw}
\begin{document}
\coversheet
\begin{question} \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}
\begin{question}[K\&T 6.3] \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 X}} \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}