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




0. (5 points) Write your name on each page of this exam.

NAME:





1. (12 points) Match up each sorting algorithm below with a number on the right that is closest to the average number of times the standard implementation in the book compares two items when sorting a randomly ordered file of 1 million distinct items. 

  _______ insertion sort                          A.  20 million


  _______ selection sort                          B.  125 billion


  _______ mergesort                               C.  30 million


  _______ quicksort                               D.  250 billion


  _______ heapsort                                E.  40 million






2. (13 points) Match each of the given search data structures with one or more of the given characteristics, where N is the number of keys and L is the maximum number of digits in a key. Write as many letters (in alphabetical order) as apply in the blank to the left of the name of the data structure. 


  _______ 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)



NAME:



3. (12 points) Consider the undirected graph on eight nodes, labelled A through H, with 12 edges 
   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-H
where the number above each edge is its weight. Give an MST for this graph and its weight. 

  MST:





  weight:


4. (12 points) Consider the set of edges in question 3 as specifying an directed graph. Give the shortest path tree from A that is computed by Dijkstra's algorithm for the digraph, assuming that edges in all adjacency lists are accessed in alphabetical order.














5. (12 points) Suppose that the weight of edge DE in the graph of the previous question is -5 instead of 2 and suppose that you use Dijstra's algorithm (under the same assumptions in the previous question) to find shortest paths. Give a path that is computed by Dijkstra's algorithm but is not a shortest path.








NAME:



6. (5 points) Consider the digraph on eight nodes, labelled 0 through 7, with the 13 directed edges 
  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.

















7. (5 points) Consider the undirected graph on seven nodes, labelled A through G, with 11 directed edges 
  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.

















NAME:



8. (15 points) Match each of the given graph processing algorithms with one of its most important features. Write the letter corresponding to your answer in the blank to the left of the name of the algorithm. In some cases, more than one answer might be argued, but you must put only one letter per algorithm. If you pick the best matches, you will use all the letters. 

  ___ 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 _____






NAME:



10. (15 points) Draw a Huffman encoding trie for the string BBBAAAAAAAAAAAAAAAACCCDDDEEE.










NAME:



11. (10 points)

(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.

  1. An FSA-based search algorithm that allows users to specify a richer set of patterns than does grep

  2. A linear-time maxflow algorithm

  3. An algorithm that compresses any given file by ten percent

  4. A linear-time algorithm for finding the MST of a set of points in the plane that can only compare the distances between two points (not know their coordinate values)

  5. A linear-time algorithm for finding the MST of a graph with positive edge weights

  6. A linear-time algorithm for sorting a set of numbers that can only compare two numbers (not know their values)

  7. An algorithm that finds the longest path connecting two vertices in a network with positive edge weights

  8. An algorithm that finds the shortest path connecting two vertices in a network with positive edge weights

  9. An algorithm that finds the longest path connecting two vertices in a weighted digraph with edge weights that could be negative

  10. An algorithm that finds the shortest path connecting two vertices in a network with edge weights that could be negative

  11. An algorithm that finds the smallest k such that a graph can be disconnected by removing k edges.








NAME:



12. (12 points) Consider the flow network on eight nodes, labelled A through H, with 12 edges 
   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-H
where 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:


13. (5 points) Define the capacity of a node as the maximum incoming flow it can have. Briefly show how to reduce the problem of finding the maxflow in a network with capacity limits on the nodes to the usual maxflow problem. Answer in one or two sentences.







NAME:



14. (5 points) Suppose that the Graham scan is used to find the convex hull of the points 
   (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.
















15. (5 points) Draw an NFA that recognizes the language ab*c | a | c .
















16. (5 points) Match up each algorithm with a data structure that is critical for implementing it. 

_____ 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
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.