COS 226 Final: COS 226 Princeton Final Fall 12 Solution

• School: Princeton University
• Department: Computer Science
• Course: COS 226
• Professor: All

Document Summary

2 6: maximum ow. (a) 25 (b) a g b c h i j (c) 25 + 3 = 28 (d) {a, b, c, f, g} (e) 28, string sorting algorithms. 0 3 4 4 2 3 2 2 1: ternary search tries. (a) a (7), caa (5), cga (4), cgca (11), ta (8), tgt (12), tt (9) (b) I d o f t h e: regular expressions. The edges 8 9, 9 10, and 10 11 are the remaining -transitions edges. 3: hu man codes. (a) char freq encoding. 255 run-length coding with 8-bit counts for best case inputs of n bits. The best case is an alternating sequence of 255 0s and 255 1s. Each sequence of 255 0s (or 255 1s) is encoded with 8 bits (11111111). 1 run-length coding with 8-bit counts for worst-case inputs of n bits. The worst case is an alternating sequence of 0s and 1s.