COS 226 Homework #6
Due: Friday, April 8, 2005

Written Exercises

Follow the instructions on the assignments page on how and when to turn these in.  Point values of each problem are shown in brackets.  Be sure to also complete the programming part of this assignment, including the program report.  Although the programming part of this assignment can be done with a partner, these exercises, as well as the program report, must be completed and submitted individually (as usual).

1. [4]  For the following graph, show the search tree (as in class) that is induced by DFS, and list the vertices in the order in which they are visited for the first time, starting from vertex A.  Assume that you iterate through the vertices adjacent to v in increasing order.
   
   
    
2. [4]  Repeat the last exercise for BFS.  Also give the length of the shortest path (number of edges) from vertex A to each other vertex.
    
3. [4]  For the following weighted graph, list the order in which edges are added to the MST by Prim's algorithm, starting with vertex A.  What is the total weight of the MST that was found?
   
   
    
4. [4]  Repeat the last exercise for Kruskal's algorithm.  What is the total weight of the MST that was found?
    
5. [10]  (CLRS exercise 15-7, slightly adapted)  Suppose you have one machine and a set of N jobs a₁, a₂, ..., a_N to process on that machine.  Each job a_j has a processing time t_j, a profit p_j, and a deadline d_j.  The machine can process only one job at a time, and job a_j must run uninterruptedly for t_j consecutive time units.  If job a_j is completed by its deadline d_j, you receive a profit p_j, but if it is completed after its deadline, you receive a profit of 0.  Give a dynamic-programming algorithm to find the schedule that obtains the maximum amount of profit, assuming that all processing times and deadlines are integers between 1 and M.  What is the running time of your algorithm?