Please read all questions carefully. Answer questions briefly and to the point. You have plenty of room for correct answers.

For questions 1 to 5, use the following graph.

1. Using Kruskal's algorithm, in what order would the edges be added to a minimum-cost spanning tree? (Don't show your work.)
   
   
   
   
2. Using Prim's algorithm, in what order would the nodes be added to a minimum-cost spanning tree, assuming that you start from node A? (Don't show your work.)
   
   
   
   
3. Using Prim's algorithm, in what order would the nodes be added to a minimum-cost spanning tree, assuming that you start from node C? (Don't show your work.)
   
   
   
   
4. If you used Dijkstra's algorithm to compute the shortest paths from node A to every other node, you would end up with a collection of edges pointing towards A. In the above graph, show the edges that would be on these shortest paths by drawing arrowheads on each edge in a shortest path.
   
   
   
   
   
5. Represent (draw) the above graph as an adjacency matrix.
   
   
   
   
   
   
   
   
   
   
   
   
6. Define the "heap property" for a node (as used in Heapsort).
   
   
   
   
7. Consider an array containing the following numbers: 15 10 12 4 8 9 6 1 3 8
   
   
   1. Draw this array as a balanced, left-justified binary tree, as in Heapsort.
      
      
      
      
      
      
      
      
      
      
   2. Is this binary tree a heap? Why or why not?
      
      
      
      
   3. Assuming that arrays are 0-based (as in Java), give the formula for finding:
      1. The index of the left child of node i.
         
         
         
      2. The index of the right child of node i.
         
         
         
      3. The index of the parent of node i.
         
         
         
8. Assume you have the following backtracking algorithm:
   

   boolean explore (Node N) {
      if N is a goal node, return true
      else if N is a leaf node, return false
      else for each child C of N {
             if (explore(C)) return true
   
      }
      return false
   }

   1. What would you add to this algorithm to print out a successful path (reverse order is okay)?
      
      
      
      
      
   2. How would you modify this algorithm so that it works on a directed graph, instead of just a tree?
      
      
      
      
      
      
   3. Assuming you have correctly modified the algorithm to work on a directed graph, what additional change could you make for an undirected graph?
      
      
      
      

9. 	X Y Z
   A B C	6 1 3 7 2 4 9 8 5

   Suppose you are running a dating service, where you want to match up N gals with N guys for dates tomorrow night. By using a questionnaire, you have decided how happy each possible couple is likely to be (higher numbers are better). For gals A, B, C and guys X, Y, Z, your table looks like this:
   
   
   1. If you use a greedy algorithm to pair up couples, what couples do you form?
      
      
      
   2. Does your greedy algorithm maximize the average (arithmetic mean) happiness of couples? Why or why not?
      
      
      
   3. Suppose that, instead of maximizing the average, you want to maximize the worst case (so that the unhappiest couple are as happy as possible). What pairings would you make?
      
      
      
   4. Describe (in words, not code) a simple brute-force algorithm for maximizing the worst case (as in 9c).
      
      
      
      
      
      
   5. What is the running time of your brute-force algorithm? Is it fast enough to be feasible for, say, 100 couples?
      
      
      
      
      
10. Given the following set of frequencies, construct a Huffman encoding for the letters A thru J.

A 20%

B 3%

C 8%

D 12%

E 6%

F 9%

G 16%

H 11%

I 14%

J 1%

Your results:

A =	B =	C =	D =	E =
F =	G =	H =	I =	J =