Due Dates --- Homework will be collected at the start of class
Section 101 -- Thursday, December 3, 1998
Section 201 --Wednesday, December 2, 1998

Homework should be hand-written and on hard-copy.
Late Homework will not be accepted

Each of the following questions refer to the following graph:

1. Draw an adjaceny table for the graph (5 points).
2. Draw an adjaceny list (Array of lists of indicies) for the graph (5 points)
3. Show a Breadth-First Search of the graph, starting at vertex E.
   Show the contents of the queue at each step of the BFS.(10 points)
4. Show a Depth-First-Search of the graph, starting at vertex C.
   Show the contents of the stack at each step of the DFS (10 points)
5. Run either Prim's or Kruskal's algorithm to generate a Minimum Spanning Tree(10 points)
   Provide a drawing of the graph which clearly indicates your MST (highlight the edges chosen)
   For Prim's algorithm, list the edges of the MST in the order chosen.
   For Kruskal's algorithm -- show the edges in sorted order, then indicate whether the edges is selected or rejected. If rejected, indicate the reason.
6. Run Dijkstra's algorithm to find the shortest path from E to K (10 points).
   Your solution should show all intermmediate values for the calculated shortest distance
   and each node's "predecessor". Indicate both the shortest path and it's total weight