Exercises B¶
Note
You must complete these exercises by Wednesday of W11.
Exercise 5.2.1¶
In the Huffman coding compression technique, it is useful to to include in the compressed file a header containing the information necessary to decode of the file. In your implementation, the header is probably a serialized version of the tree (result of a prefix parse) as proposed in the book. Do you think it would be more or less interesting from a memory point of view to store for each symbol its binary encoding rather than the serialized tree?
Exercise 5.2.2¶
Can we gain even more compression ratio if we reapply Huffman’s compression algorithm Huffman’s compression algorithm on a file already compressed once? What happens in this case? Does this open the door to a recursive and optimal compression algorithm?
Exercise 5.2.3¶
What is, approximately, the compression ratio obtained if we apply the Huffman compression algorithm
on a file with a single string consisting of the character “a” repeated a million times (:math:approx 2^{20}), followed by the character b present only once?
Does the resulting compression ratio vary with the length of the file (for example, if the a character is repeated two million times)?
What is the minimum number of bits needed to represent this file in compressed form?
Can we use another compression scheme, compressing more than Huffman compression in this particular case?
Can Huffman compression algorithm be used for other input than text files (say for instance a picture)? What would the algorithm count in this case?
Exercise 5.2.4 (Linked Heap, Inginious)¶
Imagine a heap implementation of a priority queue using a chained structure to represent the essentially complete binary tree corresponding to the heap. How many links are needed in each node? Write the code for the methods insert, delMax. What is the complexity? Is it useful to give the size max N in the constructor? How do you add a new node in the heap or remove the next node? Can this be done from the current heap size?
Implement the min priority queue using a linked structure for representing the heap: MinPQLinked
Exercise 5.2.5 (Inginious)¶
Propose a data structure that would support the following operations in logarithmic time: insert, remove maximum, remove minimum; and the following operations in constant time: find maximum and minimum. For this, we propose to study the following property called min-max heap. The even levels are: 0 (root), 2, 4, etc. These even levels are also called the \(min\) levels. The odd levels are 1, 3, 5, etc. Odd levels are also called \(max\) levels. For any \(x\) element in the min-max heap we have the following property:
If \(x\) is at a \(min\) level, all descendants of \(x\) are greater than \(x\).
If \(x\) is at a level \(max\), all descendants of \(x\) are lower than \(x\).
Questions related to this min-max heap:
Which is the smallest element of the heap?
Which is the largest element of the heap?
Draw a min-max heap that contains the following elements: 10,8,71,31,41,46,51,31,21,11,16,13.
Describe the insertion operation in a min-max heap? Give the pseudo-code.
Implement the MinMax Heap
Exercise 5.2.6¶
Imagine a data structure that supports
insertion in logarithmic time
the find median operation in constant time
deleting the median in logarithmic time.
