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

\head{CSU690}{Algorithms and Data}{Spring 2005}{14 March 2005}{12}

\begin{center}
\Large{\bf Problem Set 5 (due Monday, March 28)}
\end{center}

{\bf 1. Weighted activity selection} 

Consider a weighted 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) (5 points)}]
Consider a greedy algorithm that repeatedly performs the following
step until no more activities can be selected: select an activity that
has the maximum ratio of weight over length among all activities that
do not overlap with the activities selected thus far.

Give a counterexample to show that the above greedy algorithm will not
yield an optimal solution for the weighed activity selection problem.

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

{\bf 2. (15 points) Edit distance} 

Part (a) of Problem 15--3, pages 364--366.

{\bf 3. (10 points) Depth-first search} 

Exercise 22.3-2, page 547.

{\bf 4. (10 points) Connected components}

Exercise 22.3-11, page 549.

{\bf 5. (10 points) Topological sort} 

Exercise 22.4-5, page 552.

{\bf 6. (10 points) Minimum spanning tree}

Let $G$ be an undirected weighted graph.  Show the weight of the
maximum-weight edge of any MST of $G$ is minimum among all spanning
trees of $G$.  

({\em Hint:} Consider two trees $T_1$ and $T_2$, where $T_1$ is an
MST.  If the maximum-weight edge of $T_1$ has higher weight than the
maximum-weight edge of $T_2$, then argue that you can replace this
edge of $T_1$ with another edge of $T_2$, thus yielding a
contradiction.)

\end{document}