Transcript Document

Project 2
Task 1: Design, analyze and implement the algorithm of computing Huffman code .
Input: 26 English characters (your can add some other characters, such as space, “,”, “.”)
and their frequencies (the sum of the frequencies is 100).
Output: Huffman codeword of each character.
Task 2: First encoding, and then, decoding a text file using the Huffman codeword (the
output of the Task 1).
Input: a text file consists of the characters in Task 1
Output: Encoded the text file and decoded it back.
Requirements
• Design the algorithms for Task 1 and Task 2.
• Two data structures have to be used in the algorithm for Task 1. One is a priority queue Q.
Each node in Q is the root of a binary tree which keeps Huffman codeword.
• Analyze the time complexity of each algorithm using O-notation. Note that the time
complexity depends on the implementation of the data structures.
• Implement the algorithms using C or C++, or any other language.
• A simple user interface has to be contained. That is, the user can input the set of characters
and their frequencies, and output the Huffman code of each character. Also, they can
encode and decode a text file.
Submission
Project description, Algorithms, Algorithm analysis, Experiment output, Code.