Description
Question1)
Mark 1:
Suppose that the following declarations are in effect:
struct point { int x, y; };
struct rectangle { struct point upper_left , lower_right; };
struct rectangle *p;
Assume that we want p to point to a rectangle structure, whose upper left corner is at (10,25) and whose lower right corner is at
(20,15). Write a series of statements (in a .txt file) that allocate such a structure and initialize it as indicated.
Question2)
Mark 9:
In this question, your program will compress data using a technique called Huffman coding. Your program will build Huffman
trees as seen above, uses these trees to assign codes to each character, and then use these codes to compress some text.
Huffman Coding
Huffman coding is a method of assigning codes to each symbol in a document based on the symbol’s frequency (how many
times it appears in the document). The more frequent the symbol, the lesser the length of its code. The main idea is to assign a
code for each character that requires less than the 8 bits needed by the ASCII encoding. In this assignment, the documents will
be plain ASCII text and the symbols will be ASCII characters but in general the symbols could be part of any alphabet whose
size is |A|.
The algorithm works in several steps:
1. Read through the input data, tabulating the frequency (number of occurrences), cf , of each character in the input, and
counting the total number of characters, ctotal. For each character, calculate the probability of the character as
cp =
cf
ctotal
For example, if the input were the string hello world without a newline character, then the frequency of l would be
3, and its probability would be 3
11 whereas the frequency of h would be 1 and its probability would be 1
11 .
2. For every unique character in the document, construct a Huffman Tree node and insert it into a heap-based priority queue.
The Huffman Tree node contains a unique character from the input and the probability of the character (cp). Insert the
node into the priority queue with priority 1 − cp. In other words, the less (likely/frequent) the character is, the higher
priority it has in the queue1
. The nodes added here will form the leaf nodes of the Huffman tree.
3. Construct the Huffman Tree. While there are two or more nodes in the priority queue, repeat the following:
(a) Remove the two nodes with highest priorities (lowest probabilities) from the priority queue: denote these n1 and
n2, with character probabilities cp1
and cp2
.
(b) Create an internal Huffman tree node n
0 with probability equal to the sum of the probabilities of each of these two
nodes, c
0
p = cp1 + cp2
. Modify your data structures to represent that n1 and n2 are children of n
0
.
(c) Insert n
0
into the priority queue with priority 1 − c
0
p
.
4. The last node to remove from the priority queue is the root of the Huffman tree.
5. Assign the codes to each character. The code is a bit string of variable length which depends on the character’s location
in the tree. First note that the Huffman Tree is a binary tree, so each internal node has 2 children. The code is obtained by
the path taken to get to the leaf corresponding to the character it is representing: for instance, if the path is: { follow the
left child, follow the left child, follow the right child, follow the left child } then its code would be 0010. Starting with
an empty code: every time a left child is followed, concatenate 0 to the code and every time the right child is followed,
concatenate 1 to the code. Look at the diagram on the first page to see an example of the codes assigned to each letter
(e.g. the code for H is 001 and the code for E is 10).
6. Pass through the input document again. For each character, in sequence: print its Huffman Code.
The output produced is a Huffman-compressed version of the input. For example, the Huffman Tree depicted on the front page
of the assignment could be one constructed from the input SEASHELLS (without a newline). The Huffman-compressed phrase
is just the codes for each character in the input, in sequence:
01100000100110111101
The size of this compressed text is 20 bits as opposed to 9 · 8 = 72 bits using ASCII encoding, resulting in a 72.222% compression
rate. The Huffman Tree is needed to uncompress the data, so if this type of compression were used in practice the Huffman
Tree and other meta-data would also have to be encoded along with the compressed output to form a fully compressed file. For
this assignment, your program only prints out the Huffman-compressed bit sequence as seen above. Note that due to ties in
character frequencies and the arbitrary order that children nodes assigned to internal nodes, the Huffman Tree for a particular
input is not necessarily unique.
The input will be read using file I/O. The input file name will be sent as the only command-line argument to your program. If
your executable is named huffman then your program will be run like so:
./huffman file.txt
In C the way to access a command-line argument is by defining main this way:
int main(int argc, char * argv[]) {
// argc is the size of the argv array
// argv[0] is the command that was executed
// argv[1] is the first command-line argument
// argv[2] is the second command-line argument
return 0;
}
1Note: in practice, one could use simply use the ctotal − cf as the priority to avoid problems with numerical precision. Later steps would have to be
modified accordingly.
The input file will contain valid ASCII characters (in the range {0, 1, · · · , 127}), i.e. they will be arbitrary text files, possibly
containing special characters. Your program will never be tested on invalid input and you can assume that the input will always
have length n ≥ 1 and the number of unique characters k ≥ 2. You can be certain that the input received will be much larger
than simple phrases, so you should test your solution on larger test files. The output, sent to the standard output stream, should
be a sequence of bits using characters 1 and 0 as shown in the example in the previous paragraph (in particular, do not pack
the bits back into bytes!). You may include any amount of whitespace in your output to help visualize the data as it will all be
ignored by the verifier. However, any output other than characters 1, 0, tabs, spaces, or newlines will be considered incorrect.
Efficiency
It is important that your solution be efficient as outlined here in order to recieve full credit
Important note: the efficiency requirements below assume that k is unbounded, e.g. that the algorithm must handle a maximum
number of unique symbols which is not known in advance. This will not be true in practice for this assignment since your
program will be run on ASCII input (therefore the number of unique characters k ≤ 127) but your program should be easy to
extend to the general case of an unbounded alphabet size and the use of a hash table for storing the codes without affecting the
asymptotic time complexity of the algorithm.
Following these efficiency requirements means implementing a heap-based priority queue and a Huffman Tree data structure
and then implementing the algorithm above which use these data structures.
(Note: A tree is heap-ordered if the key in each node is larger
than or equal to the keys in all of that node’s children(if any).
You did this in Assignment3)
Assuming that the size of the input (number of characters) is n and the number of unique characters is k ≤ n:
• Note: an array of size |A| = 128 is acceptable for this assignment. Since the alphabet size is bounded by a constant (127)
then for this assignment the space required is constant. In the general case, this array could be very easily replaced by a
hash table or other map-based data structure depending on whether space savings or time savings is more important.
• Step 1 of the algorithm should run in O(n) time.
• Step 2 of the algorithm should run in O(k log k) time.
• Step 3 of the algorithm should run in O(k log k) time.
• Step 4 of the algorithm should run in O(1) time.
• Step 5 of the algorithm should run in O(k) time.
• Step 6 of the algorithm should run in O(n) time.
Design and Advice
You are free to design your data structures however you wish as long as your solution respects the efficiency requirements
detailed above. Justify all of your design choices in your documentation.
Design and test your data structures before attempting to implement the Huffman compression algorithm. Practice good programming
style by structuring and organizing your code appropriately.
It will help if you think of your heap based priority queue having the following minimum functions:
void initializePriorityQueue(int sizeOfQueue);
//after this function is called, your heap based priority queue condition must be satisfied.
//see above note for the condition
void insertInPriorityQueue(int v);
//after this function is called, your heap based priority queue condition must be satisfied.
//see above note for the condition
int getMaximumPriorityItem();
Optional: Huffman Compression Quality
Just how good is Huffman compression? Suppose the original number of bits required to represent the input was borg and the
number of bits in the compressed output is bcomp then the compression rate is:
r =
borg − bcomp
borg
You can compute these values in case you are curious about how well this compression technique does in practice, but it is not
required for the assignment. Remember that one ASCII character takes up 8 bits.
Calculate the value of r for an assortment of random text files. Do you notice a relationship between n, k, and r?
What about using Huffman codes for substrings (words) rather than characters? Would that work better or worse in general?
What kind of documents would it work better on and what kind of documents would it do worse on? Would it be harder or
easier to implement than character-based Huffman compression?
For more information on the properties of Huffman encoding, see http://en.wikipedia.org/wiki/Huffman_
coding.
What to submit for this assignment?
1) For question1, q1.txt
2) For question2:
— huffman.c
— your test cases (input files)
— and a 1 page document (pdf) that explains how your code satisfies the
requirements for efficiency.