\documentstyle[11pt,handout]{article}
\begin{document}
\input{macros}
\input{/home/rraj/Courses/3390/S99/macros/localmacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\head{3390}{Analysis of Algorithms}{Spring 1999}{May 19 1999}{21}

\begin{center}
\Large{\bf Problem Set 3 (due June 2)}
\end{center}

\bigskip
{\bf 1. (10 points total)} Consider a version of the activity selection
problem, in which each activity has a {\em weight}, in addition to the start
and finish times.  (For example, the weight may signify the importance of the
activity.)  The goal is to select a maximum-weight set of mutually compatible
activities, where the weight of a set of activities is the sum of the weights
of the activities in the set.
\begin{Itemize}
\item[{\bf (a) (2 points)}]
Give a counterexample to show that the greedy choice made for the activity
selection problem will not work for the weighted activity selection problem.

\item[{\bf (b) (8 points)}]
Use dynamic programming to solve the weighted activity selection problem.
Analyze the running time of your algorithm.
\end{Itemize}

{\bf 2. (10 points)} Exercise~17.2--4.

{\bf 3. (5 points)} Exercise~24.1--1.

{\bf 4. (10 points)} Let $T$ be any minimum spanning tree of $G$.  Let $T'$ be
a spanning tree of $G$, not necessarily a minimum spanning tree.  Prove or
disprove the following statement: The largest edge weight of $T$ is at most
the largest edge weight of $T'$.

{\bf 5. (15 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.  Justify the
correctness of your algorithm.  (Assume that the bandwidth of every link is
positive.)

{\bf 6. (10 + 5 = 15 points)} Problem~25--3.

{\bf 7. (10 points)} Exercise 26.1--4.

{\bf 8. (3 $\times$ 8 = 24 points)} Problem~27--3.

{\bf 9. (2 $\times$ 8 = 16 points)} Problem~27--4.

\end{document}