NAME:



Final Exam
COS 226 Solutions, Spring 2010

  1. MST
    A. 65 42 39 36 34 33 30 22 
    B. 22 36 42 65 39 34 33 30  
    
  2. KMP
        0 1 2 3 4 5 6 7 8
    A   0 0 3 0 0 0 3 0 9
    E   0 2 0 4 0 6 0 8 0
    T   1 1 1 1 5 1 7 1 1
        T E A E T E T E A
    
  3. DFS trace

    1. Adjacency lists
      0: 1 2 
      1: 2 0 
      2: 3 1 
      3: 0 1 
      
    2.  dfs(3) 
         dfs(0) 
           dfs(1) 
            dfs(2) 
              check 3 
              check 1 
            2 done  
          check 0 
          1 done  
        check 2
        0 done  
      check 1 
      3 done 
      
  4. Acronyms
    Abstract machine, basis for KMP algorithm. DFA
    Data structure for implementing symbol tables. BST
    Substring-search algorithm. KMP
    Fundamental recursive method. DFS
    For single-source shortest paths in unweighted graphs. BFS
    Symbol table-based compression algorithm. LZW
    Fundamental search problem, from logic. SAT
    Abstract machine, basis for grep NFA

  5. LZW compression
    in:   B   A   N   D   A   N   A   B   A   N   A   N   A    
    out:  42  41  4E  44   82     41   81     4E     85      80 
    
     
    key    value 
    BA       81 
     
    AN       82 
     
    ND       83 
     
    DA       84 
     
    ANA      85 
     
    AB       86 
     
    BAN      87 
     
    NA       88
    
  6. Suffix TST
  7. String symbol table - optional answers in brackets
     CD     R-ary trie 
     A[BE]  BST 
     A[DE]	TST 
     A[BE]	red-black tree
    

  8. RE pattern matching I

  9. RE pattern matching II
    E
    

  10. 7 sorting algorithms
    G A B F C D E
    

  11. Graph algorithms
    F, DE, A, C, E, B, AF
    
  12. Graph space usage.
    At start of Graph constructor = 16,  
    after Graph constructor = 32 + 16V 
    Total memory usage for graph with V vertices and E edges  = 32 + 16V + 52E
    

  13. Analysis
    ~N and ~N 
    ~N and ~N/2 
    ~N and 0 
    ~2N and ~N/4 
    ~2N and ~3N/8 
    ~2N and 0
    

  14. Tree encoding

    A.

    B.

    For all i from 1 to N-1  the number of 0s must be greater than the number of 1s. 
    At the end the number of 1s must be one greater than the number of 0s.
    

  15. Burrows-Wheeler
    1. sIndex[c+1] - sIndex[c]
    2.tCount[c, last] - tCount[c, first-1]
    3.sIndex[c] - tCount[c, first-1]
    4.sIndex[c] - tCount[c, last]-1
    5.Calculate sIndex and tCount. Make s the last character of the query string.
    Set first and last equal to the first and last index of this character using
    sIndex. Iteratively work from back to front of query string updating first 
    and last using answers from C and D.
    

  16. Hard problem identification
     A B C G H