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

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

\head{1390}{Algorithms}{Winter 2000}{28 February 2000}{15}

\begin{center}
  \Large{\bf Problem Set 5 (due March 9)}
\end{center}

\bigskip

{\bf 1. (15 points)} Exercise~24.1-5, page 503.

{\bf 2. (15 + 10 = 25 points)} Problem~25--3, page 546.

{\bf 3. (20 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.  Analyze the
running time of your algorithm.  You may assume that the bandwidth of
every link is positive.  ({\em Hint:} Modify Dijkstra's algorithm.)

{\bf 4. (20 points)} Exercise~17.3-2, page 344.

{\bf 5. (20 points)} Exercise~17.2-4, page 337.

{\bf 6. (30 points)} Problem~16--3, page 325.

{\bf 7. Programming assignment (80 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 9.
\end{document}

