CS 5114 Homework 3 (Spring 2009)

Describe your algorithms as clearly as possible. The style used in the book is fine, as long as your description is not ambiguous. Do not make any assumptions not stated in the problem. If you do make any assumptions, state them clearly, and explain why the assumption does not decrease the generality of your solution. If you use any new words or phrases, define them, especially if we have not used these words/phrases in class. Do not describe your algorithms only for a specific example you may have worked out. You must also provide a clear proof that your solution is correct (or a counter-example, where applicable). Describe an analysis of your algorithm and state its running time. You will only get partial credit if your analysis is not tight, i.e., if the bound you prove for your algorithm is not the best upper bound possible.

1. (40 points) Solve exercise 19 in Chapter 4 (pages 198-199) of your textbook. You may assume that all bandwidth values are distinct. If you decide to use an algorithm we have already discussed in class, it is enough to name the algorithm.
2. (25 points) Solve exercise 21 in Chapter 4 (page 200) of your textbook. Note that you cannot sort the edges, since your algorithm must run in O(n) time. (Hint: First solve exercise 2 in Chapter 3 (page 107) of your textbook. If you like, you can give your algorithm for this exercise some name, e.g., FindCycle, and use this algorithm as a sub-routine for solving exercise 21 in Chapter 4.)
3. (35 points) You are given a graph G(V, E) and a minimum spanning tree (V, T) for G. You now pick an edge e in E and change its cost from c to c'. Describe an algorithm to update T so that it is a minimum spanning tree for the graph with the new edge weight. Your algorithm must run in time linear in the number of nodes and edges in G. There are multiple cases to consider, depending on whether e is in T or not and whether c is larger or smaller than c'. You may find it useful to describe each case separately. You can assume that all edge costs are distinct, both before and after the change.