Computer Science 269
Introduction to Data Structures
Spring 2000
Assignment 7 (Completed.)
Due Wednesday, April 26, 2000.

-
Goals of this assignment:
-
To gain an initial understanding of data compression.
-
To gain skill in the use of data structures to work problems.
-
To appreciate the issue of time complexity.
-
To gain skill in documentation.
-
It is expected that students will discuss the assignments. But do
not turn in code written by another person. If that happens, both
persons are violating the ethics of this course. Representing the
work of another person as your own is plagiarism, and may result in
a disciplinary "F" in the course.
It is permissable (in this course, as this is up to the instructor)
for you to obtain ideas from other students or from other persons.
But you must type in the code yourself.
It is unadvisable for you to allow another student to have an electronic
copy of your work, as then you would unwittingly be a party to a breach
of these rules. Showing the other student a hard copy is less dangerous.
The above rule does not apply to copying files that I have made publicly
available. I expect that you will use those in their original form or
with appropriate modifications (made by just you, of course).
If you utilize code that you obtain from other sources, be sure to give
credit in a comment, such as:
// this code from website www.mit.edu/help/x13
-
Find the optimal Huffman code for an alphabet, where the symbols are
given in sorted order, and use that code to encode and decode a message.
-
A Huffman code is a mapping from a source alphabet to binary strings such
that no code string is a prefix of any other code string.
A string of symbols from the source alphabet which is encoded as a binary
string using a Huffman code can be uniquely decoded.
A simple Huffman code on the alphabet {A,B,C} encodes A as 0, B as 10, C as 11.
Then the encoding of the source string CABBA is 11010100.
Exercise. Find the source string if the code string
is 1001011011100111100.
(There is exactly one correct answer.)
-
Here is a suggested outline of your work.
-
Read the list of symbols and frequencies into an array. (It will already
be sorted by frequency.)
-
Create an optimal Huffman tree. (This can be done in O(n) time.)
-
Read the source file and use the Huffman code you created to write an
encoded file.
-
Read that encoded file to re-create the source file.
-
It is required that your code run in O(n) time, where
n is the size of the source alphabet.
Partial credit will be given if your code runs in O(n log n) time.
-
Input files needed.
For each run, you need two input files. One file contains a list of symbols
and their frequencies in sorted order. The file has one line for every
symbol. In that line are two numbers. The first number is the integer
code for that symbol, and the second number is its frequency in the
source message.
The second file you need is the source file itself, which will be simply
a text file. Don't forget that the end-of-line symbol is a symbol.
(Its code is 10.) Do not count the end-of-file symbol.
First, a small example, so that you can test-run your program:
A much larger instance:
-
List of symbols and their
frequencies in sorted order.
-
Message to encode
-
For your information (not part of the assignment) here is the
Original Source.
And here it is in three other languages:
-
Documentation will be a requirement for this assignment:
-
A design document.
-
Loop invariants, written as comments, for any tricky loop.
It is a judgment call whether a particular loop needs to
have its loop invariant written. Use the ``reasonable'' test.
Would a ``reasonably competent'' CSC major be helped, in understanding
your code, by seeing a comment explicitly stating this loop invariant?
-
Input and Output conditions for functions, again using the ``reasonable''
test.
-
Comments explaning variables and functions whose purpose is not obvious.
-
Other comments, as appropriate. But code that is overcommented looks
silly.
There are some students who want to write every conceivable comment,
"Just to be sure." Don't do that. I will instruct the grader to
take off points for ridiculous overcommenting. You are supposed to
use your judgment, and you are to be graded on how good your judgment
is.
-
As always, the programs must be executed on our system. You should
use the command: g++ -fhandle-exceptions
If you cannot get your program to run on our system, even though
it works on some other computer, that will be graded the same as
non-working code, in other words,
partial credit might be given.
-
Turn in all files. The binary (code) string will be all one line.
If you need to break it, be sure to document how you broke it.
Be sure to turn in a file giving the actual Huffman code, showing
the binary string which is the encoding of each symbol.
All files must be turned in electronically to the teaching assisant.
His email address is schj. The deadline for electronic submission
is Wednesday, April 5. The submission must be timestamped
before midnight.
Here is how that is done.
Be sure to include the string "CSC 269 001 Hw7" in the subject field
of your email.
