NAME: Final Exam |
January 14, 2004 Computer Science 226 |
This test is X questions, weighted as indicated. Do all of your work on these pages (use the back for scratch space), giving the answer in the space provided. Put your name on every page (now), and write out and sign the Honor Code pledge before turning in the test.
``I pledge my honor that I have not violated the Honor Code during
this examination.''
0 _____/ 5 1 _____/12 2 _____/ 8 3 _____/10 4 _____/10 5 _____/10 6 _____/10 7 _____/13 8 _____/12 9 _____/10 10 _____/10 11 _____/10 12 _____/10 13 _____/10 14 _____/10 15 _____/10 16 _____/10 TOTAL _____/100
_______ insertion sort A. 20 million _______ selection sort B. 125 billion _______ mergesort C. 30 million _______ quicksort D. 250 billion _______ heapsort E. 40 million
_______ M-ary trie A. tree/trie shape not dependent on the order in which keys are inserted _______ BST B. worst-case search time = O(L) _______ Separate chaining C. key values in nodes not dependent on the order in which keys are inserted _______ TST D. inorder traversal gives sorted order _______ red-black tree E. worst-case search time = O(log N)
3 1 4 1 5 9 2 6 2 5 3 7 A-B E-B A-E A-C C-D G-D D-E E-F F-G B-C F-A A-Hwhere the number above each edge is its weight. Give an MST for this graph and its weight.
MST:
weight:
0-7 0-1 1-4 1-6 2-3 3-4 4-2 5-2 6-0 6-3 6-5 7-1 7-3 .Show the DFS forests computed when Kosarju's algorithm is used to find the strong components of that graph and list the strong components.
A-B E-B A-E A-C C-D G-D D-C E-F F-G B-C F-C .Give the maximum and minimum possible values for the maximum depth of the recursion when this graph is searched with depth-first search, starting at A, over all possible adjacency-list orderings.
___ Kruskal A. finds strong components in linear time ___ Bellman-Ford B. general graph-searching scheme ___ Kosaraju C. optimal MST algorithm for dense graphs ___ Prim D. fundamental recursive method ___ DFS E. for single-source shortest paths in unweighted graphs ___ BFS F. reduces MST computation to sorting ___ PFS G. for single-source shortest paths in weighted graphs ___ Dijkstra H. for single-source shortest paths in weighted graphs, when weights could be negative.9. (5 points) The following table gives the KMP state transitions for the string 1011011010, except for three state transition, labelled X, Y, and Z in the table. Fill in the three missing values
0 1 2 3 4 5 6 7 8 9 10 ------------------------------------------- 0 | 0 2 0 2 5 0 2 8 0 10 10 1 | 1 1 3 4 X 6 Y 1 9 Z 10
X _____
Y _____
Z _____
(8 points) This question is in regard to your new job working for a software technology company. Your boss (having been told by you on the basis on your 126 knowledge that the company had better not bet its future on developing an application that finds an optimal tour connecting a set of cities) is still looking for a challenging project for you. Your boss is willing to invest in things that might be difficult, but not things that we know to be impossible or that we believe to be intractable. On the basis of your 226 knowledge, which of the following ideas can you tell your boss to forget about? Circle all that apply.
3 1 4 1 5 9 2 6 2 5 3 7 A-B E-B A-E A-C C-D G-D D-E E-F F-G B-C F-A A-Hwhere the number above each directed edge is its capacity. Give a sequence of augmenting paths that yield a maxflow and then give a mincut for this network.
augmenting paths:
mincut:
(1, 1) (4, 5) (3, 3) (5, 3) (6, 1) (7, 3) (4, 0) (3, 2)Assume that the scan is counter-clockwise, starting from the point with smallest y-coordinate. Give the order of points being scanned, and, for each point that is not on the convex hull, the point most recently added to the hull when is it eliminated in the scan.
17. (12 points) Suppose that you have a huge array with N 64-bit words, and only a tiny amount of extra memory available. Describe an algorithm for determining whether or not all the values are different. Estimate the running time of your algorithm, as a function of N._____ BFS A. 2D tree _____ DFS B. DFS forest _____ Kosaraju C. Binary trie _____ Kruskal D. Priority queue _____ LZW E. Parent-link tree _____ Maxflow F. Queue _____ PFS G. Stack _____ Range searching H. Union-find