% -*- compile-command: "pdflatex --enable-write18 hw-07-dynamic-programming.tex" -*-
\documentclass[11pt]{tufte-handout}
\usepackage{times,graphicx,epstopdf,fancyhdr,amsfonts,amsthm,amsmath,url,xspace}
\usepackage[linesnumbered,ruled]{algorithm2e}
% \usepackage[left=.75in,top=.75in,right=.75in,bottom=.75in]{geometry}

\usepackage{pgf}
\usepackage[outputdir=diagrams, extension=pgf, backend=pgf, input]{diagrams-latex}

\usepackage{qrcode, enumitem, algorithmic}

\pagestyle{fancy}

\newtheorem{claim}{Claim}
\newtheorem{definition}{Definition}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{observation}{Observation}

\theoremstyle{definition}
\newtheorem{question}{Question}

\begin{document}

\lhead{CSCI 382: Algorithms -- Fall 2017}
\chead{}
\rhead{Brent Yorgey}
\lfoot{Homework 7}
\cfoot{\thepage}
\rfoot{Due: 3:00pm, Friday, Oct 27}
\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\headwidth}{\textwidth}
\renewcommand{\footrulewidth}{0.4pt}

\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]
  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
      \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.
  \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}

\begin{question} \label{q:subset} This problem is similar to one we
  did in class, but slightly different.  Suppose we have a set
  $\{x_1, x_2, \dots, x_n\}$ of $n$ positive integers, and a target
  sum $S$, which is a positive integer.  In class, we considered
  finding a subset of $\{x_1, \dots, x_n\}$ whose sum is \emph{exactly
    equal to} $S$.  Instead, let's now consider finding a subset whose
  sum is \emph{as close to $S$ as possible without going over}; that
  is, the subset with the largest possible sum $\leq S$.  For example,
  given the set $\{1,2,7,12\}$ and the target sum $18$, there is no
  subset which sums exactly to $18$, but the one which comes closest
  without going over is $\{12,2,1\}$ which sums to $15$.  Note that
  $\{12,7\}$, with a sum of $19$, is closer to the target in an
  absolute sense, but it is greater than the target; we are interested
  in the biggest sum which is $\leq$ the target.

  \begin{enumerate}[label=(\alph*)]
  \item Describe a simple brute-force algorithm for solving this
    problem.  What is the running time of the algorithm?
  \item \marginnote{\emph{\ref{q:subset}}\quad\qrcode{Let\ $m[k,s]$\ be\
        the\ best\ possible\ sum\ using\ only\ $x_1$\ through\ $x_k$\ which\ is\ at\
        most\ $s$.}}
    Using dynamic programming, describe an algorithm with running time $\Theta(nS)$.
    Be sure that you explain how to find not only the maximum possible
    sum, but also the actual subset which has that sum.  Justify the
    correctness of your algorithm.

  \item This is known as a \emph{psuedopolynomial-time} algorithm: the
    running time is a polynomial in the \emph{value} of $S$, but
    actually exponential in terms of the \emph{size} of the input
    (\emph{i.e.} the number of bits needed to represent $S$).

    Give one example of a set of inputs for which your dynamic programming
    solution would be faster, and one example of a set of inputs for
    which the brute force algorithm would be faster.
  \end{enumerate}
\end{question}

% This question is totally screwed up.  With the size given as M_i +
% M_j, it turns out you get the same noise no matter what order you
% combine.  I then tried changing it to |M_i - M_j| but the problem
% now is that you can't do DP: the "size" of the supermagnet (M_i
% ... M_j) depends on how you combined them, so you can't just find
% the least-noise solution for M_i ... M_j and go from there.

% Next year maybe should just literally do matrix chain (perhaps dress
% it up to make it harder to google).

% \begin{question} \label{q:matrix} Mae T.\ Ricks has $n$ magnets, with
%   strengths given by $M_1, M_2, \dots, M_n$ (each strength is a
%   positive real number, measured in XXX).  At the start, the magnets are
%   all separate; but for Reasons,\footnote{Probably because her PhD
%     advisor told her she has to.} she wants to stick them all together
%   to make one big ``supermagnet''.  The magnets are heavy and could
%   damage sensitive equipment if they are moved around too much, so
%   they are all mounted on a track where they can slide back and
%   forth. So at each step, she takes two magnets (or clumps of
%   connected magnets which now count as a single ``supermagnet'') which
%   are next to each other on the track, and slides them toward each
%   other until they stick.  She continues this process until all the
%   magnets are stuck together.  For example, given magnets
%   $M_1 M_2 M_3 M_4$, she could first stick $M_2$ and $M_3$ together,
%   which we might write as $M_1 (M_2M_3) M_4$, indicating that $M_2$
%   and $M_3$ are now stuck together into one ``supermagnet''.  She
%   might then choose to slide $(M_2M_3)$ and $M_4$ together, resulting
%   in $M_1 (M_2 M_3 M_4)$; finally she slides the two final magnets
%   together, yielding $(M_1 M_2 M_3 M_4)$.  Alternatively, she could
%   have first stuck $(M_1 M_2)$ together, then $(M_3 M_4)$ together,
%   and finally stuck those two resulting supermagnets together.  As you
%   can see, although the final product will always be the same, there
%   are many different orders in which Mae could choose to stick the
%   magnets together.

%   \marginnote[-8em]{\emph{\ref{q:matrix}}\quad\qrcode{Let\ noise[i,j]\
%       be\ the\ least\ possible\ noise\ needed\ to\ combine\ only\
%       magnets\ M_i\ ...\ M_j\ into\ a\ supermagnet.\ Can\ you\ come\
%       up\ with\ a\ recurrence\ for\ noise?}}
%   \marginnote{\emph{\ref{q:matrix}}\quad\qrcode{In\ problems\ we\
%       have\ seen\ so\ far\ there\ are\ usually\ two\ choices\ to\
%       consider\ at\ each\ step.\ However,\ to\ compute\ noise[i,j]\
%       you\ will\ need\ to\ consider\ more\ than\ two\ choices.}}

%   Because of very complicated physics that no one understands, when
%   two magnets combine the effects are somewhat counterintuitive.  When
%   two magnets with strengths $M_i$ and $M_j$ stick together, they form
%   a new magnet with strength $|M_i - M_j|$, that is, the positive
%   difference between the two strengths. A bit strange perhaps, but the
%   real problem is the noise: when magnets of strength $M_i$ and $M_j$
%   stick together, they make a sound with loudness proportional to the
%   \emph{product} $M_i M_j$.  Naturally, Mae wants to minimize the
%   total noise produced during the process.  Design and
%   analyze\footnote{By ``design and analyze'' I mean to describe an
%     algorithm, prove its correctness, and analyze its asymptotic
%     running time.} an efficient algorithm which takes a sequence of
%   magnet strengths $M_1, \dots, M_n$ as input, and computes the minimum
%   possible noise needed to combine them all.
% \end{question}

\end{document}
