COS 226 PROBLEM SET 6

1. Give the KMP FSA for the string 100011000100010.







2. Draw an FSA that will efficiently recognize one of the set of patterns 00000, 1000, 111, and 001 in a given binary text string.







3. Give a Huffman code for the string a man a plan a canal panama.







4. Give the pure adaptive (LZ) code for the string a man a plan a canal panama.







5. Give the dictionary-based adaptive (LZW) code for the string a man a plan a canal panama.







Due: in precept on April 6 or 7.

Do your work on this page (use the back if you must)