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.
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.)
 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.)
 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.)
 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.
 Represent (draw) the above graph as an adjacency matrix.
 Define the "heap property" for a node (as used in Heapsort).
 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?
 Assuming that arrays are 0based (as in Java), give the formula for
finding:
 The index of the left child of node i.
 The index of the right child of node i.
 The index of the parent of node i.
 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
}
 What would you add to this algorithm to print out a successful path
(reverse order is okay)?
 How would you modify this algorithm so that it works on a directed
graph, instead of just a tree?
 Assuming you have correctly modified the algorithm to work on a directed
graph, what additional change could you make for an undirected
graph?

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?
 Does your greedy algorithm maximize the average (arithmetic mean) happiness
of couples? Why or why not?
 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?
 Describe (in words, not code) a simple bruteforce algorithm for maximizing
the worst case (as in 9c).
 What is the running time of your bruteforce algorithm? Is it fast enough
to be feasible for, say, 100 couples?
 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 = 