1. The numbers refer to the textbook. Don't confuse exercises (at the end of each section) and problems (at the end of each chapter).

2. Write clearly and legibly. Grading will be based on correctness, clarity, and whether your solution is of the appropriate length.

3. Don't forget to acknowledge all sources of assistance. Unless otherwise instructed, you must write up your homework on your own. Turn in this cover sheet with your assignment.

4. Homework is always due at the beginning of class.

• Ex. 34.1-4 (also refer to problem 1 on Exam 2)

• Ex. 34.2-1

• Ex. 34.5-1

• Prob. 34-1, part (a)

• Ex. 35.2-2

• Prob. 35-1

Complete the assignment in Homeworks 5 and 6, by implementing Dijkstra's SSSP algorithm, Bellman-Ford SSSP algorithm, and Floyd-Warshall APSP algorithm. Use a binary heap (implemented with an array) for Dijkstra's algorithm.

Continue with the assignment in Homework 5, by implementing Prim's algorithm and Kruskal's algorithm. Use a binary heap (implemented with an array) for Prim's algorithm. Use the disjoint sets data structure with union by rank (clarified 4/9) and path compression for Kruskal's algorithm.

We are shifting gears here a little - this assignment is a programming assignment.

Using either C, C++, or Java, you are to implement a "graph toolkit". Your program must read in from a text file a description of a graph (see below for specification of the file format), and then provide the user with a menu of choices for what to do with the graph. The choices will include:

• breadth-first search, with user-specified starting node
• depth-first search, with user-specified starting node
• topological sort
• Kruskal's minimum spanning tree, implemented with the disjoint sets data structure
• Prim's minimum spanning tree
• Dijkstra's single-source shortest path, with user-specified starting node
• Bellman-Ford single-source shortest path, with user-specified starting node
• Floyd-Warshall all-pairs shortest path

Input file format: The first line is either "U" or "D", indicating if the graph is undirected or directed. The second line is either "U" or"W", indicating if the graph is unweighted or weighted. The third line is the number of nodes in the graph, n. Nodes are numbered 1, 2, ..., n. The remaining lines in the file describe the edges of the graph, with one line per edge. In an unweighted graph, an edge from node i to node j would be represented by a line containing i and j, separated by a space. In a weighted graph, the two node ids would be followed by the weight of that edge (separated by a space). For example, a possible input would be:

U
W
3
1 2 5.3
2 3 7.6
3 1 10.2

Your program will be tested on our input files, so be sure you use exactly this format!

Use the adjacency list representation for the graph. For the Floyd-Warshall option, convert the adjacency list into an adjacency matrix.

Be sure your program runs on the CS department's Unix machines when compiled with gcc or jdk (as appropriate)

Turn in your code using the "turnin" program in the CS department Unix machines. (Turnin instructions available here.)

In addition to the code turn-in, you must turn in a brief hard copy writeup (like a README file) of what you did. It must explain the correspondence between the implemented functions and the choices (BFS, DFS, Topological Sort, etc.), and how to interpret the program output. This should only be about one paragraph long.

The breadth-first search, depth-first search, and topological sort are due on Friday, April 2. The others will be due a little later, but go ahead and plan for them now in your code.

Collaboration: Although you can obviously find code implementing these algorithms all over the place, you are to write your code all by yourself, from scratch, referring only to the pseudocode in the textbook. You can, of course, ask the TA or professor for assistance. The purpose of the assignment is to give you practice in programming and to increase your understanding of the details of the algorithms. Copying files off the web will not achieve these goals.

• Prob. 15-7 (left-over from HW 3)

• Ex. 21.1-3

• Ex. 21.2-2

• Ex. 21.3-1

• Prob. 21-1

• Ex. 22.1-2 (don't turn in)

• Ex. 22.1-3

• Ex. 22.2-1 (don't turn in)

• Ex. 22.2-3

• Ex. 22.3-2 (don't turn in)

• Ex. 22.3-4

• Ex. 22.4-1 (don't turn in)

• Ex. 22.4-3

• Ex. 12.1-1. Don't turn it in.

• Ex. 12.1-2

• Ex. 12.1-5

• Ex. 12.3-3

• Ex. 18.1-3. Don't turn it in.

• Ex. 18.2-1

• Ex. 18.3-1

• Prob. 18-2, parts (a) and (b)

• Ex. 11.2-2. Don't turn it in.

• Ex. 11.2-3

• Prob. 11-3, part (a).

• Ex. 15.2-1. Don't turn it in.

• Ex. 15.3-2

• Prob. 15-7 *** postponed to HW 4 ***

• Ex. 6.1-5. Don't turn it in.

• Ex. 6.1-6. Don't turn it in.

• Ex. 6.3-1

• Ex. 6.4-4. That is, for every value of n, describe an input of length n that causes the time to be as bad as Omega(n log n).

• Prob. 6-2, parts (a) through (d)

• Ex. 7.1-1. Use the partition algorithm from lecture (Hoare's partition on p. 160 of the textbook). Don't turn it in.

• Ex. 7.4-5

• Prob. 7-3

• Ex. 8.1-3

• Ex. 8.2-1. Don't turn it in.

• Ex. 8.2-2

• Ex. 8.3-1. Don't turn it in.

• Ex. 8.3-3

• Ex. 8.4-1. Don't turn it in.

• Prob. 8-6 parts (a) and (b).

• Ex. 9.2-4

• Ex. 9.3-5

• Ex. 1.2-2. Justify your answer.

• Be sure you can do Ex. 2.1-1 but don't turn it in.

• Ex. 2.2-3. Also analyze the best case.

• Be sure you can do Ex. 2.3-1 but don't turn it in.

• Ex. 2.3-3

• Ex. 2.3-5

• Ex. 2.3-6

• Prob. 2-4

• Ex. 3.1-4. Justify your answers mathematically according to the formal definition of big-oh.

• Prob. 3-2 (a) and (b). Justify your answers mathematically according to the formal definitions of big-oh, etc.

• Be sure you can do Ex. 4.3-1 but don't turn it in.

• Prob. 4-1 (a), (c), (e), and (g).