\documentstyle[11pt,handout]{article}
\begin{document}
\input{macros}
\input{/home/rraj/Courses/1390/Syllabus/localmacros}
\newcommand{\hs}{\hspace{1em}}
\newcommand{\Hspace}{\hspace{1em}}

\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\head{1390}{Algorithms}{Winter 1999}{25 February 1999}{19}

\begin{center}
\Large{\bf Problem Set 5 (due March 11 -- no late homework)}
\end{center}

\bigskip

{\bf 1. (15 points)} Exercise~23.3--4.

{\bf 2. (35 points)} Problem~23--1.  Assume that the given graph does not have
any self-loops.

{\bf 3. (20 points)} Exercise~23.4--5.

{\bf 4.} We are given a set of $n$ empty boxes $B_i=(h_i,w_i,\ell_i)$, $1\leq
i\leq n$, where $h_i$, $w_i$, and $\ell_i$ denote the height, width, and
length of box $B_i$.  Let us say that box $B_i$ {\em nests}\/ within box $B_j$
if and only if box $B_i$ can be oriented so that it is {\em strictly
smaller\/} than box $B_i$ in each corresponding dimension.  For example, even
though the box $B_i=(5,1,1)$ is taller than the box $B_j=(2,6,3)$, $B_i$ can
be placed inside $B_j$ by orienting it as a $(1,5,1)$.

\begin{Itemize}
\item[{\bf (a) (5 points)}] Describe an $O(1)$ time algorithm to determine
whether one box nests within another.

\item[{\bf (b) (20 points)}] We would like to compute the maximum length $k$
of a sequence of boxes $B_{i_1},\ldots,B_{i_k}$ such that $B_{i_j}$ nests
inside $B_{i_{j+1}}$, $1\leq j<k$.  Design and analyze an $O(n^2)$-time
algorithm for the problem by expressing it as a shortest-path problem in a
suitably defined graph.
\end{Itemize}

({\em Remark:}\/ Problem~25--2 of text is a generalization of the above
problem.  Both of these problems can also be solved directly by dynamic
programming.  For partial credit, you may solve part~(b) using dynamic
programming.)

{\bf 5. (25 points)} One can model a communication network by
a weighted directed graph $G$, in which the vertices of $G$ represent the
nodes of the network, the edges of $G$ represent the communication links of
the network and the weight of an edge is the bandwidth of the link.  We define
the {\em effective bandwidth}\/ of a path $p$ as the bandwidth of the
minimum-bandwidth link in $p$.  

Design and analyze an efficient algorithm to determine a path with the largest
effective bandwidth from a given node $s$ to a given node $t$.  If no path
from $s$ to $t$ exists, then your algorithm must indicate so.  Briefly justify
the correctness of your algorithm.  You may assume that the bandwidth of every
link is positive.  ({\em Hint:} Modify Dijkstra's algorithm.)

{\bf 6. (15 points)} Exercise~26.2--1.

{\bf 7. (25 points)} Prove that if $T_1$ and $T_2$ are two minumum spanning
trees of a graph $G$, then $T_1$ and $T_2$ have the same ``weight
distribution'' (i.e., for any weight $w$, both $T_1$ and $T_2$ contain the
same number of edges with weight $w$).

{\bf 8. Programming assignment (40 bonus points)} Airline flight schedules define
a natural graph, where the vertices are the airports and there is an edge
between any two airports for every direct flight between them.  Since there
may be multiple flights between two cities, one may get multiple edges between
two nodes in the graph.  An extensive airplane data set due to Roberto
Tammasia at Brown University is available at {\tt \~{}rraj/Data/flights}.  The
file also describes the format in which the flight entries are listed.

Write a program that explicitly constructs the airport graph from the airplane
data set.  For this purpose, you may copy the file to your account and may
modify the format to suit your program.  Develop and implement an algorithm
that takes as input a departure time and the airport codes of a source city
and a destination city and returns a flight schedule that employs a single
airline and minimizes the total {\em travel}\/ time from the source to the
destination.  (That is, you must take into account the waiting time incurred
due to flight changes.)

Your program will be tested for correctness only (using a small number of test
cases).  You should assume that the input information will be provided through
the standard input.  Please mail your program to {\tt rraj@ccs.neu.edu} by 
11:59 PM on March 11.
\junk{
Implement an algorithm that takes as input the airport codes of a source city
and a destination city and returns a flight path that minimizes the total {\em
flight} time from the source to the destination.  (Thus, you may ignore the
waiting time incurred due to flight changes.  Furthermore, the schedule is
allowed to use multiple airlines.)
}
\end{document}

