% -*- compile-command: "rubber -d hw.7.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{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 280: Algorithms -- Spring 2016}
\chead{}
\rhead{Brent Yorgey}
\lfoot{Homework 7}
\cfoot{\thepage}
\rfoot{Due: 4:00pm, Friday, March 18}
\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\headwidth}{\textwidth}
\renewcommand{\footrulewidth}{0.4pt}

\begin{question}[Micah's cafeteria problem]
  The Yankees have made it to the World Series against your favorite
  team, the Houston Astros.  The World Series is a best of 7 series,
  which means that the first team to win 4 total games is declared the
  winner.  Thus, the series can be as short as 4 games or as long as 7
  games.  As an amateur gambler, you plan to place bets on each of the
  games in the series.  Unfortunately, your gambling exploits from the
  Academy Awards have left you with only \$100 in your pocket.
  \marginnote{\emph{Note}: There is no probability involved in this
    question---your strategy is based purely on the wins and loses of
    the two teams in the series.}  While your love for the Astros is
  unbounded, so too is your enmity for the Yankees.  This acrimony has
  led you to the following decision: {\em If the Yankees win, you want
    to lose all \$100, but if the Astros win, you want to double your
    money.}  What should your strategy be?  In particular, how much
  money should you bet on the first game?

\begin{enumerate}[label=(\alph*)]
\item Start by letting $p(i,j)$ be your current winnings or
  losings (that is, the amount gained or lost relative to your
  starting \$100) when the Astros have $i$ wins and the Yankees have
  $j$ wins.  For example, $p(4,1)=100$, because if the Astros win, you
  should win \$100, while $p(1,4)=-100$ since if the Yankees win you
  should lose \$100. In general, what are the base cases for $p$?

\item Write a recursive definition for $p(i,j)$.

\item Now, $p(0,0)$ should be 0, so $p(1,0)$ should reveal your
  bet.  What is it?

\end{enumerate}
\end{question}

\begin{question} \label{q:subset} Suppose we have a set
  $S = \{x_1, x_2, \dots, x_n\}$ of $n$ positive integers, and let $M$
  be a positive integer.  The goal is to find the subset of $S$ with
  the largest possible sum, subject to the constraint that the sum
  must be $\leq M$.

  \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[i,k]$\ be\
        the\ maximum\ possible\ sum\ using\ only\ $x_1$\ through\ $x_i$\ which\ is\ at\
        most\ $k$.\ So\ we\ ultimately\ want\ to\ know\ $m[n,M]$.}}
    Using dynamic programming, describe an algorithm with running time $\Theta(nM)$.
    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 $M$, but
    actually exponential in terms of the \emph{size} of the input
    (\emph{i.e.} the number of bits needed to represent $M$).

    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}

\newpage
\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}

% \subsection*{Greedy Failure}

% \begin{question}
%   Recall the {\em matrix-chain order} problem which asks, {\em given
%     $n$ matrices $A_{1}, \ldots, A_{n}$ with corresponding dimensions
%     $p_{0},p_{1}, \ldots, p_{n}$, in what order should we perform the
%     matrix multiplications so as to minimize the number of scalar
%     multiplications?}  It is tempting to consider greedy strategies to
%   solve this problem. For example, consider the following two greedy
%   algorithms:

% \paragraph{Algorithm 1}
% \begin{quote}
%   Given an interval of matrices $A_{1}, \ldots, A_{n}$, choose the
%   pair of matrices $A_{i},A_{i+1}$ requiring the fewest scalar
%   multiplications.  That is, choose $i$ such that
%   $p_{i-1}p_{i}p_{i+1}$ is minimal.  Multiplying these two matrices
%   leaves us with $n-1$ matrices; recursively apply the strategy on the
%   remaining matrices.
% \end{quote}

% \paragraph{Algorithm 2}
% \begin{quote}
% Given an interval of matrices $A_{i}, \ldots, A_{j}$, choose the split point $t$ such that $p_{i-1}p_{t}p_{j}$ is minimal.  Use this strategy recursively on the intervals $A_{i}, \ldots ,A_{t}$ and $A_{t+1}, \ldots, A_{j}$.   The top-level recursion begins with the interval $A_{1}, \ldots, A_{n}$.
% \end{quote}
% For each algorithm, give an example where applying the strategy to the example yields a sub-optimal solution.
% \end{question}

\begin{question}[Derived from K\&T 6.6] \label{q:format}
In a word processor, the goal of loose justification is to take text with a ragged right margin, like this,

\begin{verbatim}
Call me Ishmael.
Some years ago,
never mind how long precisely,
having little or no money in my purse,
and nothing particular to interest me on shore,
I thought I would sail about a little
and see the watery part of the world.
\end{verbatim}

and turn it into text whose right margin is ``as even as possible'',
like this:

\begin{verbatim}
Call me Ishmael. Some years ago, never
mind how long precisely, having little
or no money in my purse, and nothing
particular to interest me on shore, I
thought I would sail about a little
and see the watery part of the world.
\end{verbatim}

To make this precise enough for us to start thinking about how to
write a justifier for text, we need to figure out what it means for
the right margins to be ``even''.  Suppose our text consists of a
sequence of {\em words}, $W=\{w_{1}, w_{2}, \ldots, w_{n}\}$ where
$w_{i}$ consists of $c_{i}$ characters.  We have a maximum line length
of $L$.  We will assume we have a fixed-width font, so we just need to
make sure that the number of characters on each line is no more than
$L$.

A {\em formatting of $W$} consists of a partition of the words in $W$ into {\em lines}.  In the words assigned to a single line, there should be a space after each word except the last; and so if $	w_{j}, w_{j+1}, \ldots, w_{k}$ are assigned to one line, then we should have
\[
c_{k} + \sum_{i=j}^{k-1}(c_{i} + 1) \leq L.
\]
We will call an assignment of words to a line {\em valid} if it
satisfies this inequality.  The difference between the left-hand side
and the right-hand side will be called the {\em slack} of the
line---that is, the number of spaces remaining at the right margin.
For example, suppose $L = 10$.  Then
\begin{verbatim}
Call me Ishmael.
\end{verbatim}
is not valid, since it has length $(4+1) + (2+1) + 8$ which is greater
than $10$.  On the other hand,
\begin{verbatim}
Call me
\end{verbatim}
is valid, and has a slack of $3$, since it has length only $7$,
leaving $3$ remaining spaces at the end.

We will say that a formatting is optimal when the sum of the {\em
  squares} of the slacks of all lines (including the last line) is
minimized.

\begin{enumerate}[label=(\alph*)]
\item Describe a greedy algorithm to find a formatting of a list of
  words, and give an example where your greedy algorithm does
  \emph{not} produce an optimal solution.
\item Using dynamic programming,
  \marginnote[-1.5in]{\emph{\ref{q:format}}\quad\qrcode{Let\ score[i]\
      denote\ the\ best\ score\ achievable\ using\ only\ the\ first\
      i\ words.}\vspace{1em} \\ Medium hint}\marginnote{\emph{\ref{q:format}}\quad\qrcode{To\
        compute\ score[k],\ focus\ on\ the\ last\ line.\ First\ try\
        putting\ just\ one\ word\ on\ the\ last\ line,\ then\ try\
        two\ words,\ then\ three,\ ...\ and\ pick\ the\ best\ resulting\
        score.}\vspace{1em} \\ Big hint}design and analyze an efficient algorithm to find an
    optimal formatting of a set of words $W$ into valid lines for a
    given line length $L$. (As usual, ``analyze'' means to prove it is
    correct, and analyze its asymptotic running time.)
\item Why did we use the sum of the {\em squares} instead of just,
  say, the sum?  That is, what sort of bias does this optimization
  function create?
\end{enumerate}
\end{question}

\begin{question}
  (\textbf{Optional}/\textbf{Extra Credit})

  If you want some practice actually implementing a dynamic
  programming solution to a problem, write a program that implements
  your algorithm from Question~\ref{q:format}. Your program should
  take two command-line arguments: (1) an integer representing the
  maximum line length; and (2) a file name. It should then output a
  justified version of the file to {\tt stdout} using the algorithm
  above.

  For example, suppose \verb|lorem.txt| contains the text:
\begin{verbatim}
Lorem ipsum dolor sit amet, consectetur adipiscing elit. Quisque
rhoncus interdum odio, mattis finibus eros imperdiet non. Praesent egestas lectus.
\end{verbatim}
  Then running your program with the arguments \verb|25| and
  \verb|lorem.txt| should print
\begin{verbatim}
Lorem ipsum dolor sit
amet, consectetur
adipiscing elit. Quisque
rhoncus interdum
odio, mattis finibus
eros imperdiet non.
Praesent egestas lectus.
\end{verbatim}
  which is an optimal formatting of the text into lines of length at
  most $25$.

  % If you want to use Python, I have prepared a skeleton program from
  % which you can start, available on the course website. However, you
  % may use any programming language you wish.
  % \marginnote{Ask me if you
  %   want some ideas on how to write it in Haskell, which has a really
  %   slick way to express dynamic programming algorithms using lazy,
  %   recursively defined arrays.}
  Also available is a file
  \verb|neruda.tgz| which contains a Pablo Neruda poem together with
  two outputs: \verb|neruda.50.out| and \verb|neruda.30.out| are the
  results of running my solution on \verb|neruda| using a line length
  of $50$ and $30$, respectively.  Note that in both cases, there are
  multiple correct solutions with the same minimum score. Your program
  may not produce exactly the same output as mine, but you should
  ensure that it produces a solution with the same score.

  % You should submit your program on Moodle.  If necessary, you should
  % also submit a file \verb|README.txt| with instructions explaining
  % how to compile and run your program.
\end{question}

% \subsection*{Extra Credit:  Generalized Huffman Coding with Integer Values}

% \begin{question}
% Suppose you are given an alphabet $\Sigma=\{a_{1}, \ldots, a_{t}\}$ of $t$ symbols.  A word $w=u_{1}u_{2} \cdots u_{l}$ is a finite sequence of (possibly repeated) symbols from $\Sigma$.  A code is a set of words $C=\{w_{1}, w_{1}, \ldots, w_{n}\}$.  A code is prefix-free if no word in $C$ is a prefix of another word in $C$.  Any code of this form can be expressed as a tree $T$ where a root-to-leaf path in $T$ yields a word in $C$.  If the cost of character $a_{i}$ is $c_{i}$ then the cost of a word $w=a_{j_{1}}a_{j_{2}}a_{j_{m}}$ is
% \[
% c(w)=\sum_{i=1}^{m} c_{j_{i}}.
% \]
% If codeword $w_{i}$ has associated probability $p_{i}$, then the cost of a code $C$ is
% \[
% \sum_{w_{i} \in C} c(w_{i})p_{i}.
% \]
% In the standard Huffman coding problem you are given a discrete
% probability distribution with $n$ values $\mathcal{P}=p_{1}, \ldots,
% p_{n}$ and asked to find a minimum cost prefix-free code for
% $\mathcal{P}$ over the alphabet $\Sigma=\{0,1\}$ where $c(0)=c(1)=1$.
% In this case the algorithm that greedily builds a binary tree by
% always combining the pair of values with lowest probability yields an
% optimal solution.  \marginnote{\emph{4}\quad\qrcode{Think\ about\
%       associating\ a\ length\ with\ each\ edge\ in\ the\ tree.\ \ Can\
%       you\ grow\ a\ tree\ and\ express\ its\ cost\ in\ terms\ of\ the\
%       number\ of\ leaves\ it\ currently\ has,\ as\ well\ as\ the\
%       height\ of\ every\ non-leaf\ path?}}  However, the greedy
% algorithm does not work when the costs of the encoding symbols are not
% equal.  The {\em generalized Huffman coding problem with unequal,
%   integer symbol costs} asks for a minimum-cost prefix free code for
% $\mathcal{P}$ over an alphabet of size $t$ where $c(a_{i}) \in
% \mathbb{Z}^{+}$ for all $a_{i} \in \Sigma$.  Develop a dynamic
% programming algorithm for this problem that runs in $O(n^{\alpha+2})$
% time where $\alpha=\max\{ c(a_{i}) \,|\, a_{i} \in \Sigma\}$.

% \end{question}


\end{document}
