NAME:

Final Exam		 May 17, 1999

Computer Science 226

This test is 16 questions for a total of 100 points, 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. You have three hours to complete the test.

``I pledge my honor that I have not violated the Honor Code during this examination.'' 






         1.   ___/10

         2.   ___/5

         3.   ___/5

         4.   ___/5

         5.   ___/5

         6.   ___/10

         7.   ___/5

         8.   ___/5

         9.   ___/5

        10.   ___/5

        11.   ___/5

        12.   ___/10

        13.   ___/5

        14.   ___/5

        15.   ___/5

        16.   ___/10


     TOTAL:   ___/100


NAME:



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

  ___ Floyd                B. general graph-searching scheme

  ___ Kosaraju             C. optimal MST algorithm for dense graphs

  ___ Prim                 D. fundamental recursive method

  ___ Warshall             E. for single-source shortest paths in unweighted graphs

  ___ DFS                  F. for reachability in dense digraphs

  ___ BFS                  G. reduces MST computation to sorting

  ___ PFS                  H. for all-pairs shortest paths in dense graphs
2. (5 points) The following table gives the KMP state transitions for the string 10100110, except for one state transition, labelled X in the table. What should the value of X be? 
                 0  1  2  3  4  5  6  7
               ------------------------
            0 |  0  2  0  4  5  0  2  8
            1 |  1  1  3  1  X  6  7  1


















NAME:



3. (5 points) It is easy to build a nondeterministic FSA corresponding to a regular expression, and a basic theorem from automata theory says that we can convert every nondeterministic FSA to a deterministic one. Why do we not do so to implement RE pattern matching? Circle one of the following choices. 
    A. The deterministic FSA might have an exponential number of states.

    B. There might exist a string that the deterministic FSA 
       recognizes but the nondeterministic FSA does not.           

    C. There might exist a string that the nondeterministic FSA 
       recognizes but the deterministic FSA does not.           

    D. The nondeterministic FSA might loop.

    E. The proof of the theorem is not constructive (does not
       tell us how to construct the deterministic FSA).






4. (5 points) Fill in the following table with dictionary entries that could be produced for a Huffman encoding of the string accctggccccccg. 
        a ____

        c ____
 
        g ____

        t ____














NAME:



5. (5 points) What is the last digit of the decimal representation of 13 raised to the 1000th power?



















6. (10 points) Which of the following best describes the asymptotic growth (within a constant factor) of the length of the code produced by the two versions of Lempel-Ziv encoding for a string of 8N characters made up of copies of the string abcdefgh ? Give two answers, one for the pure version (LZ) and the other for the dictionary-based version (LZW). 
        A.  log N

        B.  (log N)*(log N)

        C.  square root of N

        D.  N * log N

        E.  N


  LZ  _____

 LZW  _____







NAME:



7. (5 points) Draw the subdivision of the plane that corresponds to inserting the following points into an initially empty 2D tree, in the order given. 
        (10, 15)  (2, 3)  (5, 6)  (8, 9)


















8. (5 points) What is the maximum number of line segments that can appear in the Voronoi diagram of four points? Draw a small diagram to justify your answer.



















NAME:



9. (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 .
List the strongly connected components of this digraph.
















10. (5 points) Match each of the given recurrences with the asymptotic growth (to within a constant factor) of the corresponding quantity, assuming in each case that division by 2 is rounded down to the nearest integer and that the recurrence is valid for N > 1 with T(0) = T(1) = 1. Write the letter corresponding to your answer in the blank to the left of the recurrence. If you pick the best matches, you will use all the letters. 

  ___  T(N) = 2 T (N/2) + 1             A. N log N

  ___  T(N) = T (N/2) + 1               B. linear

  ___  T(N) = 3 T (N/2) + N             C. log N

  ___  T(N) = 4 T (N/2) + 1             D. quadratic

  ___  T(N) = 2 T (N/2) + N             E. none of the above










NAME:



11. (5 points) Give the average node depth in the DFS and the BFS trees for a complete graph of N nodes. (Count the root as being at depth 0.) 

 DFS  __________



 BFS  __________













12. (10 points) Classify each of the following graph-processing problems as easy or intractable, by writing E or I, respectively, in the space provided. 

  ___  Find the largest complete subgraph. 

  ___  Find a set of edges that separates the graph.

  ___  Find a path that uses each vertex exactly once, or report that none exists.

  ___  Find a path that uses each edge exactly twice, or report that none exists.

  ___  Find the smallest set of edges that connects all the vertices.

  ___  Find the vertices in a digraph that are not on a directed cycle.










NAME:



13. (5 points) Consider the following undirected graph (edge weights are in parentheses) 
     0-1 (.4)   0-2 (.5)   0-3 (.9)   1-2 (.3)   2-3 (.2) 
     2-4 (.4)   3-5 (.8)   3-6 (.6)   4-6 (.5)   5-6 (.4)
Give the parent-link representation of the MST computed by Prim's algorithm, using the standard adjacency-matrix representation.















14. (5 points) Give the parent-link representation of the shortest-paths tree from node 0 that is computed by the PFS implementation of Dijkstra's algorithm for the graph of the previous question, using the standard adjacency-lists representation.
















NAME:



15. (5 points) Consider the edges given in question 13 to be directed edges and the weights to be capacities. What is the value of the maximum flow from 0 to 6?
















16. (10 points) Match each of the given algorithm-analysis activities with one of its most important goals. Write the letter corresponding to your answer in the blank to the left of the name of the method. In some cases, more than one answer might be argued, but you must put only one letter per algorithm. You will use two of the letters twice. 

  ___ empirical study         A. know to stop seeking a better algorithm

  ___ linear programming      B. cope with NP-completeness

  ___ NP-completeness proof   C. guarantee performance

  ___ average-case analysis   D. predict performance

  ___ optimality proof        E. find a polynomial-time solution

  ___ worst-case analysis     

  ___ approximation algorithm