CPSC 212-302 Name: ______
Test #3, Part B April 20, 2010
Closed books. Closed Notes. Calculators OK. 11 questions, 2 bonus questions, 110 points. 110 minutes. The weight of each question is indicated in parentheses. Please use a pencil. If you need more space, use the back of the sheet.
1. (10) Apply Dijkstra’s algorithm to graph G1. Put the final values produced by the algorithm in the table below. Start with node 3.
dv pv G1:
0 ______
1 ______
2 ______
3 ______
4 ______
5 ______
2. (10) Complete the following tables which refer to properties of graph G1 above.
0 1 2 3 4 5
indegree: ______
outdegree: ______
adjacency matrix M1 (if entry is 0, leave it blank):
0 1 2 3 4 5
0 ______
1 ______
2 ______
3 ______
4 ______
5 ______
3. (10) How many edges does an undirected complete graph with N nodes have? Be precise. Your answer should be expressed in terms of N. The graph is undirected so edge (u,v) = (v,u) is counted only once. Explain clearly how you arrived at your answer (you will get at most one point credit if all you give me is your final answer).
4. (a) (7) Consider the following frequency table. Draw the Huffman Tree. Recall that when merging two subtrees, the root with the smaller frequency should go on the left.
sp 12
d 7
g 3
o 10
e 11
j 6
a 4
b 2
(b) (3) Use your tree to decode the message: 110111111111010110011111010 ______
5. (10) (a) (5) Apply Prim’s algorithm to graph G5 below starting with node 1. Draw the final table in the space below. What is the cost of the MST? (b) (5) Apply Kruskal’s algorithm to the same graph. Draw the final spanning tree produced by the algorithm in the space beside and below below the graph. What is the cost of the MST?
dv pv
0 ______
1 ______
2 ______
3 ______
4 ______
5 ______
6 ______
6. (a) (5) Consider graph G6 below. In what order are the nodes of the graph visited in a depth-first postorder (visit when you pop) traversal of the graph? Start with node H. When given a choice of nodes to visit, visit the nodes in alphabetical order. (b) (5) In what order are the nodes of the graph visited in a breadth-first search of the graph? Start with node B. When given a choice of nodes to visit, visit the nodes in alphabetical order. Show the data structure that you use to produce the traversal.
Data structure required for depth-first traversal: ______
Depth First Postorder traversal starting with node H:
______
Data structure required for breadth-first traversal: ______
Breadth-first search traversal starting with node B:
______
7. (10) 5-city Traveling Salesman Problem. Assume that the cities are numbered from 0 through 4 and that the matrix below describes the weighted undirected graph. Because the graph is undirected, only the upper half of the matrix has been specified. Edge (u,v) = (v,u). (a) Draw the graph using the nodes shown below and the information from the matrix. (b) Eyeball the graph and determine a minimum cost tour starting and ending at node 0. Put your answer in the space provided.
0 1 2 3 4
0 . 8 3 5 9 Minimum cost tour (start and end at 0):
1 . 6 8 2
2 . 9 4 0 ______0
3 . 2
4 .
8. (10) Insert the following values into an initially empty binomial min queue. Note that “D” means delete. When you encounter an asterisk (*), you should show the intermediate binomial queue. Label the intermediate binomial queues (a), (b), and (final).
15 23 89 59 41 25 * D D 21 59 D * 44 11 25 23 *
9. (5) Convert the following binary tree into one (or more) k-ary trees. Draw your tree(s) in the space on the right.
10. (10) Sorting: Your friend does not believe that HeapSort has order of complexity O(N log N). How would you argue that it is? Your answer should include answers to questions such as: (a) What are you counting when you conduct your analysis? (b) What are the major steps in HeapSort? (c) What is the order of complexity of each major step? Be precise.
11. (5) Consider the 3x3 “chessboard” below left. On the right, draw the graph induced by a knight’s move. The graph has been started for you.
Bonus Questions (5 points each)
(5) Bonus A. Consider the following set of values (5) Bonus A. NP-Complete problems.
which are to be sorted in increasing order. Show (a) Clearly define the minimum vertex cover
the result of the first two passes of radix sort over problem (b) Find a minimum vertex cover
the values. Put your answers in the space proved. for the graph shown below.
972 ______Define minimum vertex cover:
158 ______
952 ______
489 ______
249 ______
489 ______
941 ______
552 ______
490 ______
418 ______
401 ______
326 ______Minimum vertex cover: ______