Assignment 8 - COP 3530, Fall 2007

Please read the assignment submission rules and the academic dishonesty page before you start work on this assignment. Failure to comply by these rules will cost a significant percentage of your assignment grade.

• Have your name, UF ID, and discussion session number as comments at the top of your code.
• ONLY SOFT copy is REQUIRED.
• For pen-paper questions, we only accept the following format file: Plain TEXT, PDF and DOC.
• Please download and check your jar file after your submission. Make sure the submission is correct.
• Jar your files.

---

Note: There is no coding involved in this assignment.

1.  LZW Compression

(If you find it too troublesome to put the colored characters in the txt file, you can use the comma expression. For example, " cbacbbacbbac " can be written like " c,bacbbacbbac ". If you feel that the frame box of (code, key) is hard to draw in your txt file, you can omit it, but you need to align the code and key in a neat way.)

Start with an LZW compression dictionary that has the entries (a,0), (b,1)and (c,2)

(a) Compress the string sequence " cbacbbacbbac ". For each character encountered, draw the code table following the encoding of each character. The code tables after the first 'a' is compressed are shown below. Complete the remaining process.

(a) Initial Configuration
code	0	1	2
key	a	b	c
cbacbbacbbac
Compressed string = null
(b) c has been compressed
Code	0	1	2	3
Key	a	b	c	cb
cbacbbacbbac
Compressed string = 2

(b) Decompress the code sequence "12340248". For each code encountered, draw the decode table following the decoding of each code. The decode tables after "0" is decompressed are shown below. Complete the remaining process.

(a) Initial Configuration
code	0	1	2
key	a	b	c
12340248
Decompressed string = null
(b) 0 has been decompressed
Code	0	1	2	3
Key	a	b	c	bc
12340248
Decompressed string = b

2. Consider a binary tree T, whose every non-leaf node has non-empty left and right sub-trees. Assuming T has n leaf nodes, how many nodes in total does it have? Justify your answer.

Hint: Note that if we remove two leaf nodes, both of which share the same parent node, every non-leaf node of the new tree will still have non-empty left and right sub-trees. How does this change the number of leaf (and non-leaf) nodes?