\documentclass[11pt]{article}
\usepackage{handout2e}
\begin{document}
\input{macros}
\input{courseMacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}
\input{epsf}

\newif\ifexam
%\examtrue
\examfalse

\ifexam
\newcommand{\answer}[1]{}
\else
\newcommand{\answer}[1]{{\bf Answer:} #1}
\fi

\ifexam
\head{CSU690}{Algorithms and Data}{Spring 2005}{21 April 2005}{18}
\else
\head{CSU690}{Algorithms and Data}{Spring 2005}{21 March 2005}{19}
\fi

\ifexam
\begin{center}
\Large{{\bf Final}} 
\end{center}
\else
\begin{center}
\Large{{\bf Sample Solution to Final}} 
\end{center}
\fi

\ifexam
{\bf Instructions.}
\begin{itemize}
\item This is a open-book, open-notes, 120 minute final exam.

\item
Read all the problems through first and attack them in the order that
allows you to make the most progress.  There are 4 problems worth a
total of 40 points and a bonus problem worth 4 points.

\item 
While describing an algorithm, you may use any of the algorithms
  covered in class or in the text as a subroutine.  You need to
  provide a proof of correctness and/or an analysis of the running
  time only for those problems where they are explicitly required.

\item
Show your work, as partial credit will be given.  If you need extra
space, use the blank facing page.

\item
Best of luck!
\end{itemize}

\vfill

{\Large
\begin{center}
\begin{tabular}{||c|c|c||}\hline
Question & Score & Maximum \\ \hline
1 & & 10 \\ \hline
2 & & 10\\ \hline
3 & & 12 \\ \hline
4 & & 8 \\ \hline
Bonus & & 4 \\ \hline
Total & & 40 \\ \hline
\end{tabular}
\end{center}
}

\vfill
\vfill

\begin{center}
{\bf Name:} {\vrule height0.4pt width3in}
\end{center}
\vfill
\vfill


\newpage
\fi


{\bf Problem 1. (2 + 8 = 10 points) \hs Bitonic sequences} 

A {\em bitonic}\/ sequence is a sequence of numbers that monotonically
decreases and then monotonically increases.  That is, a sequence $X =
x_1, x_2, \ldots, x_n$ is bitonic if there exists a $t$ in $[1, n]$
such that $x_{i+1} < x_i$ for $1 \le i < t$ and $x_{i+1} > x_i$ for $t
\le i < n$.  For example, $11, 9, 6, 5, 1, 4, 7$ is bitonic since the
sequence first decreases from $11$ to $1$ and then increases from $1$
to $7$.  On the other hand, the sequence $11, 8, 7, 9, 10, 6$ is not
bitonic since it decreases, then increases, and then again decreases.
\begin{Itemize}
\item[{\bf (a)}]
Give an $O(1)$ time algorithm to find the maximum of a given bitonic sequence.

\answer{
The maximum of the first and last elements yield the maximum of the
sequence.
}
\vfill

\newpage

\item[{\bf (b)}]
Give an $O(\lg n)$ time algorithm to find the minimum of a given bitonic
sequence of length $n$.  Briefly justify the correctness of your
algorithm.

\answer{The minimum of a bitonic sequence is the unique element
$x_i$ in $X$ that satisfies one of the following three conditions: (i)
$i = 1$ and $x_i < x_{i+1}$; (ii) $i = n$ and $x_{i-1} > x_i$; (iii)
$1 < i < n$, $x_{i-1} > x_i$, and $x_{i+1} > x_i$.  

We use a recursive binary-search procedure.  If the length of the list
is $1$, then simply return the lone element.  Otherwise, if any of the
conditions (i) or (ii) hold, we simply return the appropriate element.
If none of these two conditions hold, we probe the middle element, say
$x_i$ of the list.  If $x_i$ satisfies condition (iii), we return this
element.  Otherwise, either $x_{i-1} < x_i < x_{i+1}$ or $x_{i-1} >
x_i > x_{i+1}$.  In the former case, we make a recursive call on the
right half of the list.  In the latter case, we make a recursive call
on the left half of the item.

The recurrence for the running-time is $T(n) \le T(\lfloor n/2
\rfloor) + \Theta(1)$, which yields an $O(\lg n)$ worst-case running
time.
}
\end{Itemize}

\newpage

{\bf Problem 2. (10 points) Fairly splitting a heist}

Two art thieves share a collection of $n$ paintings, numbered $1$
through $n$.  They have agreed on a positive integer value for each
painting, say $x_1$, $x_2$, \ldots, $x_n$.  They would like to split
the paintings into two halves of exactly equal value.

Design an algorithm that determines whether it is possible for the
thieves to fairly split the paintings.  Your algorithm should run in
$O(n T)$ time, where $T$ is the sum of the $x_i$'s. 

({\em Hint:} Maintain an $n \times T$ matrix $S$, where $S[i,j]$ is
$1$ if one of the thieves can get a total value of $i$ using a subset
of the paintings $1$ through $j$.  Obtain a recurrence for computing
$S$ and use $S$ to determine whether the paintings can be split
equally.)

\answer{
We can calculate $S[i,j]$ as follows.  First we set $S[i,0]$ to be $0$
for all $i$.  For any other $i$ and $j$, we set $S[i,j]$ to 1 if
either $i = x_j$, or $i > x_j$ and $S[i-x_j,j-1] = 1$; otherwise, we
set $S[i,j]$ to $0$.

The desired problem can be solved as follows now.  If $T$ is odd, then
the answer is trivial: it is not possible to fairly split the
paintings.  If $T$ is even, then we would like each thief to have a
total value of $T/2$.  So we check whether $S[T/2,n]$ is $1$.  If it
is, then the answer is yes; otherwise, the answer is no.
}
\newpage

{\bf Problem 3 (4 $\times$ 3 = 12 points) \hs Graph properties} 

For each of the following statements, indicate whether it is true or
false.  In each case, briefly justify your answer.
\begin{itemize}
\item[{\bf (a)}]
If vertex $u$ appears before vertex $v$ in a topologically sorted
order of a directed acyclic graph $G$, then there is a directed path
from $u$ to $v$ in $G$.

\answer{
False.  Consider the dag with three vertices $x$, $u$, and $v$ and edges
$(x,u)$ and $(x,v)$.  One topologically sorted order is $x, u, v$.
There is no edge $(u,v)$, however.
}
\vfill

\item[{\bf (b)}]
Every $n$-vertex undirected tree has exactly $n-1$ edges.

\answer{
True.  The proof is by induction.  For $n = 1$, the claim is trivially
true.  Assume the induction hypothesis that a tree $T$ with $n$
vertices has $n-1$ edges.  For the induction step, consider an
$n+1$-vertex tree.  Remove a leaf and the associated edge.  We have an
$n$-vertex tree with $n-1$ edges.  So the $n+1$-vertex tree has $n$
edges.}
\vfill

\newpage

\item[{\bf (c)}] Let $G$ be an undirected connected graph with weights
on edges.  Assume that the edge weights are all distinct.  Then, the
edge with the smallest weight is always in the minimum spanning tree.

\answer{
True.  If not, then we can add the smallest-weight edge to the tree,
remove the heaviest weight edge on the resulting cycle and obtain a
spanning tree with lower weight.}

\vfill

\item[{\bf (d)}]
Let $G$ be a weighted directed graph and $s$ be a vertex in $G$.  Let
$p$ denote a shortest path from $s$ to $t$.  If we increase the weight
of every edge in the graph by $1$, then $p$ remains a shortest path
from $s$ to $t$.

\answer{
False.  Suppose there are two paths from $s$ to $t$ in $G$, one with 3
hops and total weight 3, and another with 1 hop and weight 4.  When we
increase all edges weights by $1$, the 3-hop path gets weight 6, while
the 1-hop path gets weight 5.  Thus, the original shortest path is no
longer the shortest path.
}
\vfill
\end{itemize}
\newpage

{\bf Problem 3. \hs Social interaction and network flows} 

Several families go out to dinner together.  To increase their social
interaction, they would like to sit at tables so that no two members
of the same family are at the same table.  Show how to formulate the
problem of finding a seating arrangement that meets this objective as
a maximum flow problem.

Assume that the dinner contingent has $n$ families and the $i$th
family has $a_i$ members.  Also assume that $m$ tables are available
and the $j$th table has a seating capacity of $b_j$.

({\em Hint:} In the network flow graph, include a vertex for each
family and a vertex for each table together with distinguished source
and sink vertices.)

\item[{\bf (b)}\hs] Give an optimal Huffman code for a data file
  containing $n$ distinct characters, in which the $i$th character ($1
  \le i \le n$) occurs $2^i$ times.  (You may simply state the answer
  without any additional justification.)



{\bf Problem 4. (8 points) \hs Updating all-pairs shortest path
lengths on addition of a new edge}

Applications that maintain all-pairs shortest paths among various
physical locations should be able to address changes in the network
efficiently.  For instance, when a new edge is added, one should be
able to change the all-pairs shortest paths without having to compute
these paths all over again.  

Suppose we are given an $n$-vertex directed graph $G$ with adjacency
weight matrix $W$ for which we have computed the all-pairs shortest
path lengths.  (Recall that the entry in the $i$th row and $j$th
column of $W$ is the weight of the edge $(i,j)$, if it exists, and
$\infty$, otherwise.)  Assume that there are no negative weights in
the graph.  Suppose we are also given $D$, the all-pairs shortest path
length matrix for $G$: for vertices $i$ and $j$, the entry $d_{ij}$
($i$th row and $j$th column of the matrix $D$) gives the shortest path
length between $i$ and $j$.

Suppose a new edge $(x,y)$ with weight $c$ is added to $G$, where $x$
and $y$ are two vertices in $G$: thus, the entry $w_{xy}$ in $W$
changes from $\infty$ to $c$.  Give an efficient algorithm to compute
the new all-pairs shortest path length matrix, and analyze its
worst-case running time.  You need not compute the actual shortest
paths.

({\em Hint}: An $O(n^2)$ worst-case running time is achievable.)

\answer{
We set the new shortest-path length $d'_{ij}$ to $\min\{d_{ij}, d_{ix}
+ c + d_{yj}\}$, in parallel, for all $i$ and $j$.  Originally,
$d_{ij}$ specified the length of the shortest path.  With the addition
of the edge $(x,y)$, we have two cases to consider.  Either the
shortest path contains the edge $(x,y)$, or not.  In the first case,
the shortest such path will have total weight $d_{ix} + c + d_{yj}$.
In the second case, the shortest such path will have weight $d_{ij}$.
}
\newpage

{\bf Bonus Problem. (4 bonus points) \hs Data compression} 

Suppose you are asked to compress large files containing characters
from a 4-element alphabet $\{a, b, c, d\}$.  You are told that each
character of the file is independently drawn at random from the
alphabet with probability distribution $(0.99, 1/300, 1/300, 1/300)$,
respectively.  Which of the following three compression schemes would
you use and why: Huffman coding, Run Length coding, LZ77 compression
with a dictionary of size 4 and lookahead 4.  Credit will be given
only if appropriate justification is provided.

\answer{

Huffman coding will assign 1 bit to $a$, 2 bits to $b$, and $3$ bits
to each of $c$ and $d$.  The average number of bits per character is
close to $1$ bit.

Run length encoding will replace a run of $\ell$ $a$s by $(a, \ell)$.
The average length of a run will be 100, and most of the runs will be
concentrated around this number.  So number of bits per character will
be approximately $7$ (the number of bits needed to code the most
likely run lengths) plus a couple of additional bits, divided by 100.

An LZ77 code with dictionary 4 and lookahead buffer has to output at
least 1 bit every 8 characters (or less).

Hence, run length coding will yield the most compression.
}
\end{document}