In this assignment, you will learn about the famous Lempel-Ziv-Welch (LZW) compression algorithm. Most compression algorithms including UNIX compress are based on the LZW algorithm. The LZW algorithm compresses a given text by figuring out patterns which appear very often in the text. The basic idea is to replace (perhaps very long) patterns which appear many times by a much shorter code. Read about this algorithm here .

Your assignment is to implement the LZW algorithm. You can assume that the input text contains english characters (capital and small), space, and full stop. You need to write two programs - one for compressing an input text, and the other to uncompress the compressed text to the original text. To implement the dictionary of code and key, you will use a hash table. Use your own hash function, but you must use quadratic probing to resolve collisions.