Homework 3

Update (12/3/03, 7:17pm):

• In problem 8, there are no negative-cost cycles (read the modified statement of the problem)
• The due date of this assignment has been changed from Wednesday, Dec 3 to to Friday, Dec 5.
• The recommended problems can now be handed in for Above and Beyond credit. For ease of grading, please hand them in separately from the rest of your assignment.

Recommended problems: (Now Above and Beyond) Here are a few interesting problems from the textbook that didn't find their way into the assignment. If you are looking for more practice problems to work on, this should form a good list:
    Union find    8.1, 8.2, 8.6, 8.7
    Sorting         7.12, 7.17, 7.19, 7.20, 7.24, 7.33, 7.37, 7.38, 7.41
    Graphs         9.4, 9.7a, 9.10, 9.16, 9.20, 9.51

Note: Please review the collaboration policy on the course web page. You must mention the names of fellow students who you worked with on this assignment.

Total: 110 points. 10 points for each problem.

1. [Union-find] Suppose you start with elements a through j with each in its own set, and perform the following operations:
   
   find(d), union(d,a), union(b, c), union(h,j), find(c), union(h,b), find(j), union(b,a).
   
   
   1. Without union-by-size or path compression, and choosing the root of a union by selecting the alphabetically smaller node, show the final uptree forest that results from the above operations. You may choose to show or omit the intermediate steps. At what depth does node j end up in the final forest?
   2. Repeat part a. but this time with union-by-size. Break any ties by giving preference to the alphabetically smaller node.
   3. Repeat part b. but now add path compression as well.
   
   
2. [Union-find] Problem 8.4, page 288 (union-by-height)
   
   
3. [Sorting] Problem 7.13, page 261 (bad case for heap-sort)
   
   
4. [Sorting] Problem 7.19, page 262 (quicksort with cutoff)
   
   
5. [Sorting] Problem 7.30, page 263. Also answer: The analysis of which algorithm does this recurrence correspond to? Is this a worst-case, average-case, best-case or amortized-case analysis of that algorithm?
   
   
6. [Sorting] (5 points each part)
   1. Problem 7.3, page 261. For what value of k will this change the Omega(n²) average case lower bound of adjacent-element-exchange-sorting to Omega(n log n)?
   2. Problem 7.34, page 263 (Stirling's formula)
      
      
7. [Sorting] Suppose you are given as input n positive integers and a number k. Write an algorithm (pseudocode is fine) to determine if there are any four of them, repetitions allowed, that sum to k. Your algorithm should run in time O(n² log n). Partial credit will be given if your algorithm is correct but takes longer than O(n² log n). As an example, if n = 7, the input numbers are 6, 1, 7, 12, 5, 2, 14 and k = 15, the answer should be yes because 6+5+2+2 = 15.
   
   Hint #1: First solve the simpler problem that determines if there are any two numbers that sum to k.
   
   Hint #2: Sum of four numbers is the sum of two pairs of numbers.
   
   
8. [Graphs] Suppose you are given a graph that has negative-cost edges but no negative-cost cycles. Why does the following strategy fail to find shortest paths: uniformly add a constant k to the cost of every edge so that all costs become non-negative, run Dijkstra's algorithm, return the result with edge costs reverted back to the original costs (i.e. with k subtracted). Give an argument as well as a small example where it fails.
   
   Will this strategy of adding a constant k to the cost of every edge work if, instead, we were trying to construct an MST?
   
   
9. [Graphs] Problem 9.50, page 348, with a little modification. Instead of finding any sequence of words that transform A into B, find the shortest one. If your solution uses a graph, state clearly what the nodes, the edges and the costs are in the graph, whether it is directed or undirected, etc.
   
   
10. [Graphs] Problem 9.15, page 343.
    
    
11. [Graphs] Prove the correctness of Prim's algorithm. As part of your proof, you should argue that when Prim's algorithm adds an edge e to the tree it is constructing, edge e is guaranteed to be present in a minimum spanning tree. In other words, the algorithm never makes a mistake in its greedy selection.

	Department of Computer Science & Engineering University of Washington Box 352350 Seattle, WA  98195-2350 (206) 543-1695 voice, (206) 543-2969 FAX [comments to cse326-staff]