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

```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
```D
```

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

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

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

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