CSE 326 Autumn 2001

Homework Assignment 4

Due:

Wednesday, December 5

Readings:

Weiss Chapters 9.1-9.3, 9.5, 8, 7

Note:

Write all of your algorithms in pseudocode, following the course pseudocode guidelines.

Problems:

1. Topological sort with stack vs. queue.

a. (3 points) Weiss 9.2.

b. (2 points) Show the result of stack-based topological sort on the graph in Figure 9.79.

2. (3 points) Prove that Dijkstra’s Algorithm will not work on a graph with negative edge weights.

3. Weiss 9.16. Negative edge weights with Prim’s and Kruskal’s.

a. (2 points) Prove whether or not Prim’s Algorithm works with negative edge weights.

b. (2 points) Prove whether or not Kruskal’s Algorithm works with negative edge weights.

4. (5 points) Weiss 9.20. Maximum spanning tree.

5. (5 points) Weiss 8.6. Prove uniqueness of maze path, using “standard” maze construction algorithm.

6. (5 points) Weiss 7.16. Algorithm for non-recursive mergesort.

7. Running times for quicksort.

a. (3 points) Weiss 7.20. Assume median-of-3 pivoting.

b. (5 points) Weiss 7.21(a)-(c). Repeat with different pivot strategies.

8. (5 points) Weiss 7.24. Construct a pathological input for quicksort.

9. (Extra Credit - 3 points) Weiss 9.51. Currency hogs! Modify your implementation of Dijkstra’s Algorithm (Project 3) to make money on the currency exchanges. Hand in your test data set and output.

10. (Extra Credit - 2 points) Weiss 8.7. Algorithm for “single-barrier” maze construction.