NAME:

Final Exam		 May 24, 2001

Computer Science 226

This test is 20 questions, each worth 5 points, for a total of 100 points. 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.   ___/5

         2.   ___/5

         3.   ___/5

         4.   ___/5

         5.   ___/5

         6.   ___/5

         7.   ___/5

         8.   ___/5

         9.   ___/5

        10.   ___/5

        11.   ___/5

        12.   ___/5

        13.   ___/5

        14.   ___/5

        15.   ___/5

        16.   ___/5

        17.   ___/5

        18.   ___/5

        19.   ___/5

        20.   ___/5


     TOTAL:   ___/100

NAME:



1. (5 points) The following table describes a pattern-matching automaton with start state 0 and accept state 3. Describe the language recognized by this automaton. 
                    0  1  2  3 
                  -------------
               0 |  0  2  0  3 
               1 |  1  1  3  3
















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 ____

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



6. (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. 
   (2, 1)  (4, 4)  (5, 2)  (10, 2)  (7, 5)  (1, 6)  (8, 4)

















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
















NAME:



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









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 .
Draw the DFS tree for the standard adjacency-matrix representation. List the edges of each type in the space provided below. 










  Tree edges:


  Back edges:


  Down edges:


  Cross edges:

10. (5 points) List the strongly connected components of the digraph of Problem 9.







NAME:



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




12. (5 points) Match each of the given graph-processing algorithms with the problem that it solves. 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. 

  ___ Bellman-Ford           A. MST for dense graphs

  ___ Ford-Fulkerson         B. maxflow

  ___ Kruskal                C. transitive closure

  ___ network simplex        D. MST for sparse graphs 

  ___ Floyd                  E. negative-cycle detection

  ___ Prim                   F. strong components

  ___ Warshall               G. all-pairs shortest paths in dense graphs

  ___ Dijkstra               H. mincost maxflow

  ___ Kosaraju               I. single-source shortest paths





NAME:



13. (5 points) Consider the following undirected graph 
     (0-1, 1)  (0-4, 4)  (0-6, 1)  (0-5, 2)  (1-2, 1)  (1-4, 2) 
     (1-6, 3)  (2-3, 2)  (2-5, 3)  (3-4, 1)  (4-5, 1)  (5-6, 3)
where (i-j, w) means that the edge that connects node i to node j has weight w. Give the parent-link representation of the MST computed by Prim's algorithm, using the standard adjacency-matrix representation.
















14. (5 points) Consider the edges given in question 13 to be directed edges. 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) Prove the following statement or give a counterexample: "For any weighted graph G there is node v in G such that a Shortest Path Tree with v as source is identical to a Minimum Spanning Tree of G."


















16. (5 points) Consider the edges in question 13 to be directed edges and the weights on the edges to be capacities. Show a sequence of augmenting paths that could result from the maximum-capacity augmenting-path algorithm in computing a maximum flow from 0 to 6.





















NAME:



17. (5 points) Consider the following network 
     (0-1, 6, 1)  (0-2, 4, 3)  (0-3, 4, 4)  (1-2, 3, 1)  (1-3, 3, 1)
     (2-4, 4, 1)  (3-4, 4, 1)  (2-5, 3, 5)  (3-5, 3, 6)  (4-5, 5, 2)
where (i-j, w, c) means that there is an edge from node i to node j with capacity w and cost c. Add a dummy edge (5-0, 11, -9) and give a sequence of augmenting cycles that yield a mincost maxflow.



















18. (5 points) The following array is a parent-link representation of a tree: 
    0  1  2  3  4  5  6  7  8  9
    ----------------------------
    0  2  0  8  2  6  7  4  4  4
Give the parent-link representation of the tree that results from adding the edge 5-1 and removing the edge 2-4.












NAME:



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
















20. (5 points) Match each of the given problems with its known worst-case complexity. Write the letter corresponding to your answer in the blank to the left of the name of the method. You must put only one letter per problem. 

  ___ graph coloring             A. linear-time algorithm known

  ___ linear programming         B. polynomial-time (superlinear) algorithm known

  ___ convex hull                C. NP-hard

  ___ graph planarity            D. unknown

  ___ maximum flow           

  ___ minimum spanning tree

  ___ graph isomorphism

  ___ string matching