COS 226: Final Exam

NAME:

Final Exam

COS 226 Solutions, Spring 2010

MST

A. 65 42 39 36 34 33 30 22 
B. 22 36 42 65 39 34 33 30

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

DFS trace

Adjacency lists
```
0: 1 2 
1: 2 0 
2: 3 1 
3: 0 1 
```

 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

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

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

Suffix TST

String symbol table - optional answers in brackets

 CD     R-ary trie 
 A[BE]  BST 
 A[DE]	TST 
 A[BE]	red-black tree

RE pattern matching I
RE pattern matching II
```
D
```
7 sorting algorithms
```
G A B F C D E
```
Graph algorithms
```
F, DE, A, C, E, B, AF
```

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 + 56E

Node: 28 bytes (8 bytes overhead, 4 bytes Item pointer, 4 bytes Node pointer, 12 bytes Integer).
Nodes: 56E (2 nodes per edge)

Analysis

~N and ~N 
~N and ~N/2 
~N and 0 
~2N and ~N/4 
~2N and ~3N/8 
~2N and 0

Tree encoding

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.

Burrows-Wheeler

A. sIndex[c+1] - sIndex[c]
B. tCount[c, last] - tCount[c, first-1]
C. sIndex[c] + tCount[c, first-1]
D. sIndex[c] + tCount[c, last] - 1
E. 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.

Hard problem identification
```
 A B C G H
```