Homework 1 (assigned January 6, due January 12)

Reading: CLRS chapters 21 and 23

Written assignment: Solve the following problems. You may discuss the problems with your classmates, but you must write up your solutions independently and in your own words. If you borrow a key idea from someone else, please acknowledge them. You may study written sources relevant to an assigned problem, but you may not copy or paraphrase solutions found on the internet or in other written sources.

Problems:

For each problem that requires you to write an algorithm, give an English description of your algorithm, describe your algorithm in pseudocode, analyze its running time, and argue for its correctness. Your argument should be precise, i.e., rigorous enough to be converted into a formal argument if required.

1. CLRS exercise 21.3-3, page 572. (5 points)
   2nd edition, page 509.

2. CLRS Problem 21-1, parts a–c, pages 582–583. For part b, argue correctness by contradiction. (part a, 1 point; part b, 4 points; part c, 5 points)
   2nd edition, pages 518–519.

3. CLRS Problem 21-3, parts a–d, pages 584–585. (part a, 2 points; part b, 2 points; part c, 3 points; part d, 3 points)
   2nd edition, page 521.

4. CLRS Problem 23-1, parts a–d, page 638. (5 points for each part)
   2nd edition, page 575.

5. CLRS Problem 23-3, parts a–b, page 640. (part a, 2 points; part b, 8 points)
   2nd edition, page 577.

6. Alice and Bob are building a network and face the following problem. They have a connected graph G = (V, E), in which the vertices represent sites that want to communicate. Each edge e is a communication link, with a given available bandwidth b(e). For each pair of vertices u, v in V, they want to select a single u-v path P on which this pair will communicate. The bottleneck rate of this path P is the minimum bandwidth of any edge it contains, i.e., b(P) = min over e in P of b(e). The best achievable bottleneck rate for the pair u, v in G is simply the maximum over all u-v paths P of the value b(P).
   Alice claims that one can find a spanning tree T of G so that for every pair of vertices u, v, the unique u-v path in the tree T attains the best achievable bottleneck rate for u-v in G; i.e., if you could choose any u-v path in the graph G, you could not do better than the u-v path in the tree T.
   Show that such a tree exists and give an efficient algorithm to find one; i.e., give an algorithm that constructs a spanning tree T in which, for each u, v in V, the bottleneck rate of the u-v path in T is equal to the best achievable bottleneck rate for the pair u, v in G. Argue that your algorithm is correct and analyze its running time. (10 points for a correct algorithm; 5 points for correctness and time analysis)