CIT594 Third Quiz
Spring 2004 
Name_________________________________________ 
Please read all questions carefully. Answer questions briefly
and to the point. You have plenty of room for correct answers. Every question
or subquestion is worth 5 points.
For questions 1 to 5, use the following graph.
 Using Kruskal's algorithm, in what order would the edges be added
to a minimumcost spanning tree? (Don't show your work.)
1 2 4 6 8
 Using Prim's algorithm, in what order would the nodes be added to
a minimumcost spanning tree, assuming that you start from node
A
?
(Don't show your work.)
A B F D C E
 Using Prim's algorithm, in what order would the nodes be added to
a minimumcost spanning tree, assuming that you start from node
C
?
(Don't show your work.)
C B F D A E
 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}
 Represent (draw) the above graph as an adjacency matrix.



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




*


*


*


*


*

*


*

*

*



*

*


*




*

*


*



*


*

*

*

*




 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.
 Consider an array containing the following numbers:
15 10 12 4 8 9 6 1 3 8
 Draw this array as a balanced, leftjustified binary tree, as in Heapsort.
 Is this binary tree a heap? Why or why not?
Yes, it is balanced and leftjustified, and every node has the heap
property.
 Assuming that arrays are 0based (as in Java), give the formula for
finding:
 The index of the left child of node i.
2*i + 1
 The index of the right child of node i.
2*i + 2
 The index of the parent of node i.
(i  1) / 2
 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 }
 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)
 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.
 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.

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:
 If you use a greedy algorithm to pair up couples, what couples do you
form?
CX, BZ, AY
 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.
 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
 Describe (in words, not code) a simple bruteforce algorithm for maximizing
the worst case (as in 9c).
Try each possible set of pairs, and choose the set with the best
worst case.
 What is the running time of your bruteforce 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 N1 choices, for the third there are N2, .... Hence, there
are N! possible pairings.
This is definitely not feasible for 100 couples (100! possible pairings).
 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) 