Please read all questions carefully. Answer questions briefly and to the point. You have plenty of room for correct answers. Every question or sub-question is worth 5 points.

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.)
        1  2  4  6  8
   
   
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.)
        A  B  F  D  C  E
   
   
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.)
        C  B  F  D  A  E
   
   
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.
        B -> A,  C -> A,  E -> A,  F -> B,  D -> { either B or F is okay, but not both}
   
   
5. Represent (draw) the above graph as an adjacency matrix.
   

   A B C D E F A B C D E F  0  6  7  -  8 -  6  0  4  3 -  1  7  4  0  -  9  5  -  3  -  0 -  2  8  -  9  -  0 10  -  1  5  2 10  0

   or

   A B C D E F A B C D E F *    *    *    *    * *    * * *       * *    *          * *    *       *    * * * *

   
   
6. Define the "heap property" for a node (as used in Heapsort).
   
   The (value in a) node is at least as large as (the values in) its children.
   
   
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?
      
      Yes, it is balanced and left-justified, and every node has the heap property.
      
      
   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*i + 1
         
         
      2. The index of the right child of node i.
         
         2*i + 2
         
         
      3. The index of the parent of node i.
         
         (i - 1) / 2
         
         
8. Assume you have the following backtracking algorithm:
   

   1  boolean explore (Node N) {
   2     if N is a goal node, return true
   3     else if N is a leaf node, return false
   4     else for each child C of N {
   5            if (explore(C)) return true
   6     }
   7     return false
   8  }

   1. What would you add to this algorithm to print out a successful path (reverse order is okay)?
      
      Add print statements before each "return true" (lines 2 and 5)
      
      
   2. How would you modify this algorithm so that it works on a directed graph, instead of just a tree?
      
      Put in a test to see whether we had reached this node before. The test could be before (or after) line 2, in which case it should just return, or it could be just inside the for loop (line 4), in which case it should "continue" the loop.
      
      
   3. Assuming you have correctly modified the algorithm to work on a directed graph, what additional change could you make for an undirected graph?
      
      Line 3 (test if leaf) could be eliminated, since it should never succeed.
      
      

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?
      
      CX, BZ, AY
      
      
   2. Does your greedy algorithm maximize the average (arithmetic mean) happiness of couples? Why or why not?
      
      No. CX = 9, BZ = 4, AY = 1, and (9+4+1)/3 = 14/3.
      However, the pairings CY = 8, BX = 7, AZ = 3 give (8+7+3)/3 = 18/3.
      
      
   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?
      
      BZ, AX, CY
      
      
   4. Describe (in words, not code) a simple brute-force algorithm for maximizing the worst case (as in 9c).
      
      Try each possible set of pairs, and choose the set with the best worst case.
      
      
      
   5. What is the running time of your brute-force algorithm? Is it fast enough to be feasible for, say, 100 couples?
      
      For the first of N gals there are N choices of guy, for the second there are N-1 choices, for the third there are N-2, .... Hence, there are N! possible pairings.
      This is definitely not feasible for 100 couples (100! possible pairings).
      
      
10. Given the following set of frequencies, construct a Huffman encoding for the letters A thru J.
    
    There are many possible encodings. This solution gives the "expected" answer, but any answer that has the right number of bits for each character and has the prefix property (no code is a prefix of any other code) is also a correct answer.
    
    

A 20%

B 3%

C 8%

D 12%

E 6%

F 9%

G 16%

H 11%

I 14%

J 1%

Your results:

A = 00 (2 bits)	B = 01010 (5 bits)	C = 1000 (4 bits)	D = 110 (3bits)	E = 0100 (4 bits)
F = 1001 (4 bits)	G = 101 (3 bits)	H = 011 (3 bits)	I = 111 (3 bits)	J = 01011 (5 bits)