Project 1

Last modified: October 17 2008 05:30:08 PM

For this project, you must work individually - that is, group work or working with a partner is not allowed.

Description

You will write a program to see just how good Huffman codes really are. You will also integrate the use of a heap into this project.

Your program will read in a file specified by the user and create the following entities: a max heap that holds onto the words in the file and their frequencies, a max heap that holds onto the characters in a file and their frequencies, a Huffman tree for encoding the file based on character frequencies, and a Huffman tree for encoding the file based on word frequencies.

I do not expect that you will create the code for the Huffman Tree or the Max Heap yourself, you should look to the textbook (the code for the book is available online) or other sources for the implementation of these two structures.

You may also want to employ the use of other structures from the standard template library. If a structure you would like to use is available in the libary, you most certainly should use it - DO NOT recreate the implemenation yourself.

The file you will get will be formatted in the following way. Each line will contain a word/frequency pair. The word will be first on the line followed by a space, followed by the frequency count of the word.

Example file:

for 12
not 150
cat 45
raccoon 567

You can assume that words do not have spaces in them. Each word/frequency pair will be listed on its own line. Even though it is not good practice, you can assume well formatted files (no mal-formatted files will be run through your program for grading).

Other functionality is dictated in the user interface section.

User Interface

The user interface to your program must provide the following functionality:

• Load a file (with word/frequency lines as explained above)
• Print out a list of the words and frequencies in order of decreasing frequency.
• Print out a list of the characters contained in the words and their frequencies in the file in order of decreasing frequency.
• List the Huffman codes for the words in the file.
• List the Huffman codes for the characters in the file.
• An analysis of the two encoding schemes compared to ASCII enoding. This analysis should include the number of bits used in the two types of Huffman encoding (i.e. count the total number of 0's and 1's) as well as the number of bits used if the file was encoded using standard ASCII (7 bits per character).

Testing

You should test your program with various inputs. You can create the test files yourself.

You should create a test plan for this program. It is perhaps highly advisable to create a base test plan before you begin coding so that you can use it to form a strategy for implementation.

You should write up your test plan and your test cases in a file named testing.txt that you will submit with your project. You should make note in this file if there are any bugs found in your testing that you were not able to fix for the final submission.

What to submit

You should put all of your files in a directory named project1 and zip them creating a project1.zip file. You should submit this file using the electronic submission command.

Your zip should contain all of your .cpp and .h files, a description of the testing of your program in a file named testing.txt, as well as a makefile. You should also include a file named README that gives the name of the executable that is created when make is run as well as any pertinent user interface issues that the grader should be aware of when grading your submission. Failure for the grader to be able to use and grade your program will result in an automatic grade of 0 on this assignment.

Note also that your program MUST compile and run on our systems using your makefile or your grade on the project will be an automatic 0.

Due Date

All files for this assignment need to be submitted by 11:59:59pm on Sunday, October 26th Tuesday, October 28th.