%%  Problem Set 2 for CSC373H1, Fall 2014,
%%  at the University of Toronto.
%%
%%  Copyright (c) 2014 Francois Pitt <fpitt@cs.utoronto.ca>
%%  last updated at 08:24 (EDT) on Wed 24 Sep 2014
%%
%%  CC BY-SA 4.0
%%  This work (the current file named 'PS3handout.tex') is licensed under
%%  the Creative Commons Attribution-ShareAlike 4.0 International License.
%%  To view a copy of this license, visit
%%      http://creativecommons.org/licenses/by-sa/4.0/
%%  or send a letter to: Creative Commons, 444 Castro Street, Suite 900,
%%  Mountain View, California, 94041, USA.
%%  This is a human-readable summary of (and not a substitute for) the
%%  license.
%%  You are free to:
%%      Share -- copy and redistribute the material in any medium or format
%%      Adapt -- remix, transform, and build upon the material for any
%%          purpose, even commercially.
%%      The licensor cannot revoke these freedoms as long as you follow the
%%          license terms.
%%  Under the following terms:
%%      Attribution -- You must give appropriate credit, provide a link to
%%          the license, and indicate if changes were made. You may do so in
%%          any reasonable manner, but not in any way that suggests the
%%          licensor endorses you or your use.
%%      ShareAlike -- If you remix, transform, or build upon the material,
%%          you must distribute your contributions under the same license as
%%          the original.
%%      No additional restrictions -- You may not apply legal terms or
%%          technological measures that legally restrict others from doing
%%          anything the license permits.
%%  Notices:
%%      You do not have to comply with the license for elements of the
%%      material in the public domain or where your use is permitted by an
%%      applicable exception or limitation.
%%      No warranties are given. The license may not give you all of the
%%      permissions necessary for your intended use. For example, other
%%      rights such as publicity, privacy, or moral rights may limit how you
%%      use the material.

\RequirePackage[l2tabu,orthodox]{nag}  % warn about common LaTeX pitfalls
\RequirePackage[ascii]{inputenc}  % input is 7-bit ASCII
\RequirePackage{fixltx2e}  % fix LaTeX2e kernel bugs

\documentclass[11pt,twoside]{article}
\usepackage{calc}
\usepackage{enumitem}
\usepackage{fancyhdr}
\usepackage[hmargin=1in,vmargin=1in]{geometry}
\usepackage{lastpage}
\usepackage{relsize}
\usepackage[normalem]{ulem}
\usepackage{url}
\usepackage{amsmath}
\usepackage{amssymb}

% Set up fonts.
\usepackage[T1]{fontenc}  % use true 8-bit fonts
\usepackage[notextcomp]{kpfonts}  % "Kepler" fonts
\usepackage{slantsc}  % allow slanted small-caps
\usepackage{microtype}  % perform various font optimizations
% Redefine left/right brackets to use curvier glyphs than kpfont's default.
\DeclareSymbolFont{lmsymb}     {OMS}{lmsy}{m}{n}
\DeclareSymbolFont{lmlargesymb}{OMX}{lmex}{m}{n}
\DeclareMathDelimiter{\rbrace}{\mathclose}{lmsymb}{"67}{lmlargesymb}{"09}
\DeclareMathDelimiter{\lbrace}{\mathopen}{lmsymb}{"66}{lmlargesymb}{"08}

% For drawing diagrams.
\usepackage{tikz}
\usetikzlibrary{positioning}

% Page layout: stretch text to fill up page.
\addtolength\footskip{.25\headheight}
\flushbottom

% Common list settings.
\setlist{topsep=\parsep,itemsep=0pt}  % no extra vertical space around lists

% Common macros.
\input{macros-373}

% Headings.
\pagestyle{fancy}
\let\headrule\empty
\let\footrule\empty
\lhead{CSC\,373\,H1}
\chead{\large\scshape Problem Set \#\,3}
\rhead{\scshape Fall 2014}
\lfoot{\scshape Dept.\@ of Computer Science, University of Toronto,
       St.~George Campus}
\cfoot{}
\rfoot{\scshape page \thepage\space of \pageref{LastPage}}


\begin{document}

\noindent
\strong{Worth:}  2\%
\hfill
\strong{Due:}  By 9:59pm on Monday 29 September\\[2ex]
\strong
   {Remember to write
    your \emph{full name} and \emph{student number}
    prominently on your submission.}

\medskip

\noindent
\rule{\textwidth}{.5pt}\\[1ex]
\begingroup\slshape
    Please read and understand the policy on Collaboration
    given on the Course Information Sheet.
    Then, to protect yourself,
    list on the front of your submission
    \strong{every} source of information
    you used to complete this homework
    (other than your own lecture and tutorial notes,
    and materials available directly on the course webpage).
    For example, indicate clearly
    the \strong{name} of every student with whom you had discussions,
    the \strong{title} of every additional textbook you consulted,
    the \strong{source} of every additional web document you used,
    \etc.\par
        For each question, please write up detailed answers carefully.
    Make sure that you use notation and terminology correctly, and
    that you explain and justify what you are doing.
    Marks \strong{will} be deducted
    for incorrect or ambiguous use of notation and terminology, and
    for making incorrect, unjustified, ambiguous, or vague claims
    in your solutions.
\endgroup\\
\rule{\textwidth}{.5pt}

\bigskip

\noindent
Consider the following problem, which we will call \lang{GridPaths}.
\begin{description}
\item[Input:]
    A directed acyclic graph $G = (V,E)$, as in the example below.
    That is, the graph can be laid out on a grid so that
    all directed edges point either right or down, and
    no two edges cross.
    Further assume that $V = \{p_1,\dots,p_n\}$ and that
    the vertices appear in order on the grid,
    when scanning left-to-right and top-to-bottom.
\item[Output:]
    The number of distinct directed paths
    from $p_1$ (the vertex at the top left corner)
    to $p_n$ (the vertex at the bottom right corner).
\end{description}
For example, in the diagram below,
there are three distinct paths from $p_1$ to $p_{10}$
($p_1 \to p_2 \to p_5 \to p_6 \to p_{10}$,
$p_1 \to p_2 \to p_5 \to p_9 \to p_{10}$,
$p_1 \to p_8 \to p_9 \to p_{10}$) but
there is only one path from $p_1$ to $p_{13}$
($p_1 \to p_8 \to p_{13}$).
\begin{center}
\begin{tikzpicture}[scale=.6,>=latex]
    \draw ( 0,  0) node (p01) {$p_{1}$};
    \draw ( 3,  0) node (p02) {$p_{2}$};
    \draw ( 8,  0) node (p03) {$p_{3}$};
    \draw (13,  0) node (p04) {$p_{4}$};
    \draw ( 3, -3) node (p05) {$p_{5}$};
    \draw ( 5, -3) node (p06) {$p_{6}$};
    \draw ( 8, -3) node (p07) {$p_{7}$};
    \draw ( 0, -5) node (p08) {$p_{8}$};
    \draw ( 3, -5) node (p09) {$p_{9}$};
    \draw ( 5, -5) node (p10) {$p_{10}$};
    \draw ( 8, -6) node (p11) {$p_{11}$};
    \draw (13, -6) node (p12) {$p_{12}$};
    \draw ( 0, -8) node (p13) {$p_{13}$};
    \draw ( 3, -8) node (p14) {$p_{14}$};
    \draw ( 5, -8) node (p15) {$p_{15}$};
    \draw ( 8, -8) node (p16) {$p_{16}$};
    \draw (11, -8) node (p17) {$p_{17}$};
    \draw (13, -8) node (p18) {$p_{18}$};
    \draw ( 0,-11) node (p19) {$p_{19}$};
    \draw ( 3,-11) node (p20) {$p_{20}$};
    \draw ( 5,-11) node (p21) {$p_{21}$};
    \draw (13,-11) node (p22) {$p_{22}$};
    \draw[->] (p01) -- (p02);
    \draw[->] (p02) -- (p03);
    \draw[->] (p03) -- (p04);
    \draw[->] (p02) -- (p05);
    \draw[->] (p03) -- (p07);
    \draw[->] (p05) -- (p06);
    \draw[->] (p06) -- (p07);
    \draw[->] (p01) -- (p08);
    \draw[->] (p05) -- (p09);
    \draw[->] (p06) -- (p10);
    \draw[->] (p07) -- (p11);
    \draw[->] (p04) -- (p12);
    \draw[->] (p08) -- (p09);
    \draw[->] (p09) -- (p10);
    \draw[->] (p11) -- (p12);
    \draw[->] (p08) -- (p13);
    \draw[->] (p09) -- (p14);
    \draw[->] (p10) -- (p15);
    \draw[->] (p11) -- (p16);
    \draw[->] (p12) -- (p18);
    \draw[->] (p13) -- (p14);
    \draw[->] (p14) -- (p15);
    \draw[->] (p15) -- (p16);
    \draw[->] (p16) -- (p17);
    \draw[->] (p17) -- (p18);
    \draw[->] (p13) -- (p19);
    \draw[->] (p14) -- (p20);
    \draw[->] (p15) -- (p21);
    \draw[->] (p18) -- (p22);
    \draw[->] (p19) -- (p20);
    \draw[->] (p20) -- (p21);
    \draw[->] (p21) -- (p22);
\end{tikzpicture}
\end{center}
Use the dynamic programming paradigm covered in lecture
to solve the \lang{GridPaths} problem.
This problem is not particularly difficult to solve, so
take the time to explain carefully what you are doing and
to write up a detailed answer\dash in particular,
follow closely the paradigm given in class.

\noindent
Assume that you have at your disposal
two arrays $\var{up}[i]$ and $\var{left}[i]$,
defined as follows for $1 \le i \le n$:
\[
    \var{up}[i] =
        \begin{cases}
            j & \text{if there is a vertex $x_j$ such that}\\[-.5ex]
              & \text{$(x_j,x_i)$ is an edge going down},\\
            0 & \text{otherwise}.
        \end{cases}
    \qquad
    \var{left}[i] =
        \begin{cases}
            j & \text{if there is a vertex $x_j$ such that}\\[-.5ex]
              & \text{$(x_j,x_i)$ is an edge going right},\\
            0 & \text{otherwise}.
        \end{cases}
\]
For example, in the graph above,
$\var{up}[3]=0$ and $\var{left}[3]=2$,
$\var{up}[11]=7$ and $\var{left}[11]=0$.

\end{document}
