NAME:

MAKEUP Final Exam		 September 10, 1998

Computer Science 226

This test is 17 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.''





1. (45 points) Fill in the following table. Express running times as a function of the number of items, N, to within a constant factor for large N. Assume that the items in the symbol table are 64-byte records with 64-bit keys. 
                                   insert time              delete time
                            worst    best   average     worst    best   average


  BST


  Key-Indexed Search


  Red-Black Tree


  Splay Tree

  
  Separate Chaining


  Linear Probing


  Binary Trie
2. (5 points) Draw the union-find forests for the edges BC AB AD CE DF EG FH GI HJ IK JL KM, using path compression without weight balancing.







NAME:



3. (5 points) Draw the red-black tree that results when the keys 
          X R A N D O M K E Y S
are inserted in that order into an initially empty tree.


















4. (5 points) Draw the splay tree that results when the keys 
          X R A N D O M K E Y S
are inserted in that order into an initially empty tree.


















NAME:



5. (5 points) Give the KMP FSA for the string 1101111.





















6. (5 points) Draw a NDFSA for the string a((b + c)* + d)*e.





















NAME:



7. (5 points) Show the Patricia trie that results when you insert keys defined by all suffixes of the string 
  10010010
(in decreasing order of their length, or moving left to right) into an initially empty trie. Ignore those suffixes that are prefixes of other suffixes.

















8. (5 points) Show the existence TST that results when you insert keys defined by suffixes of the string 
  randomstring
(in decreasing order of their length, or moving left to right) into an initially empty tree.

















NAME:



9. (5 points) Show the B-tree that results when you insert the octal keys 
  020 000 001 002 003 004 005 006 007 010 011 012 013 014 015 016 017
in that order into an initially empty tree, with M = 4. Use the style of Figures 16.5 through 16.7 in the book.
















10. (5 points) Show the extendible hash table that results when you insert the octal keys 
  020 000 001 002 003 004 005 006 007 010 011 012 013 014 015 016 017
in that order into an initially empty table, with M = 4. Use the style of Figures 16.11 through 16.13 in the book.

















NAME:



11. (5 points) Consider the graph on seven nodes, labelled A through G, with 11 directed edges 
  AB EB AE AC CD GD DC EF FG BC FC.
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.
















12. (10 points) Consider the graph on eight nodes, labelled A through H, with 16 edges 
  AB(3) EB(1) AE(4) AC(1) CD(5) GD(9) DC(2) EF(6) FG(2) BC(5) FA(3) AH(7)
where the numbers in parentheses are edge weights. Give a minimal spanning tree and a shortest path tree from A for the graph.

















NAME:



13. (5 points) Draw the 3D tree that is constructed when the points 
(0, 3, 2) (1, 4, 5) (0, 1, 1) (3, 0, 2) (4, 3, 1) (4, 0, 2)
are inserted in that order into an initially empty tree.


















14. (5 points) Suppose that we have a graph like Figure 1.2 in the book (points on a grid, with connections among adjacent points present with a fixed probability), but with the additional proviso that edges to diagonally adjacent points also allowed. Which minimal spanning tree method would be preferred (PFS, Prim, or Kruskal) for a huge graph of this type? Explain your answer.

















NAME:



15. (5 points) Give an optimal BST for the following keys, with the access frequencies given in parentheses. 
  A(3) B(1) C(4) D(1) E(5) F(2) G(6) H(2) I(4)
What is the average cost of a search hit in your tree?


















16. (5 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 which 64-bit value occurs most often. Estimate the running time of your algorithm, as a function of N and M, the frequency of occurrence of the most popular value.

















NAME:



17. (5 points) Consider the following function takes two arguments, an integer x and a function f that takes an integer as an argument and returns an integer. Assume that f is like a mathematical function (whenever we call it twice with the same argument value, we get the same return value) that is defined for all integers. 
  void loop(int (*f)(int), int x)
    {
      a = x, b = f(x);
      while (a != b)
        { a = f(a); b = f(f(b)); }
    }
Of the following statements, which best describes the behavior of this function?

A. Always gets in an infinite loop
B. Always returns
C. Whether or not it returns depends on f, not x
D. Whether or not it returns depends on x, not f
E. Whether or not it returns depends on both x and f