NAME: Final Exam COS 226 Solutions, Spring 2011

4A and 6B are UNDER CONSTRUCTION
1. MST
```A. 1 2 3 4 5 7 9

B. 2 1 3 4 7 5 9

```
2. KMP
```  0 1 2 3 4 5 6 7 8
Z X X X Z X Z X X
X 0 2 3 4 0 6 3 8 9
Y 0 0 0 0 0 0 0 0 0
Z 1 1 1 1 5 1 7 1 1

```
3. Match the algorithms
```F H A C I D G E B J
```
4. DFS Trace

```B. 0: 3, 2, 1
1: 3, 2, 0
2: 1, 0
3: 0, 1

C. dfs(3)
dfs(0)
dfs(1)
check 0
dfs(2)
check 1
2 done
check 3
1 done
check 3
0 done
check 1
3 done
```
5. LZW compression
```in:   A  A A  A A A  B  A A A  A A  B
out: 41   81     82 42     82   81 42 80

key value
AA   81
AAA  82
AAAB 83
BA   84
AAAA 85
AAB  86
```
6. TST
```A.
aac (4)
aat (2)
ac  (1)
ct  (0)
g   (3)
ta  (5)
ca  (missing index) <=== +1

```
7. String sorts
```

stable
inplace
sublinear

Quicksort
N
Y
Y
Mergesort
Y
N
Y
LSD string sort
Y
N
N
MSD String sort
Y
N
Y
3-way string quicksort
N
Y
Y

```
8. Regular Expressions
1. ```0->11 0->1
1->5 1->9 1->2
4->8
5->6
6->7 6->5
8->9
9->1 9->10
10->13
11->12
12->11 12->13
```
2. ```0, 1, 5
2, 6
2, 6, 7, 8, 9
3, 7
3, 6, 7, 8, 9
7
6, 7, 8, 9
```
9. Bellman-Ford
 successful relax A B C D phase 1 A->C X 1 A->B X 0 phase 2 C->D X 0 phase 3 D->B X -1
10. Prefix-free codes
```code 1 none
code 2 A B C
code 3 A
code 4 A C
```
11. 3-way partitioning
```A A A H H U M U N U K U N U K U M P U U M U
Number of exchanges: 20
```
12. Linear Programming
```Maximize Xbt + Xct subject to constraints
0 <= Xsa <= 7
0 <= Xsb <= 4
0 <= Xac <= 5
0 <= Xba <= 1
0 <= Xbc <= 2
0 <= Xbt <= 6
0 <= Xct <= 3

Xsa + Xba = Xac
Xsb = Xba + Xbc + Xbt
Xac + Xbc = Xct

```
13. Subsequence
1. st.put(next, new Queue());
2. Queue q = st.get(next);
3. st.delete(next);
4. st.put(next+d, q);
5. N log Q
6. N

14. Maxflow
1. i, iii, v,
2. i, ii, iii, vi, viii

15. Intractibility
 P NP NP-complete linear equation satisfiability Y Y N linear inequality satisfiability Y Y N 0-1 integer linear inequality satisfiability ? or N* Y Y boolean satisfiability ? or N* Y Y integer factoring ? Y N or ?
16. What is the shortest distance between 2 jokes?
``` a straight line
```