College of Computer & Information Science Spring 2005 Northeastern University Handout 12 CSU690: Algorithms and Data 14 March 2005

Problem Set 5 (due Monday, March 28)

1. Weighted activity selection

Consider a weighted version of the activity selection problem, in which each activity has a 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.

(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.

(b) (15 points) Use dynamic programming to solve the weighted activity selection problem. Analyze the running time of your algorithm.

2. (15 points) Edit distance

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

3. (10 points) Depth-first search

Exercise 22.3-2, page 547.

4. (10 points) Connected components

Exercise 22.3-11, page 549.

5. (10 points) Topological sort

Exercise 22.4-5, page 552.

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.

(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.)