Exercises B#

Note

You must complete these exercises by Wednesday of W11.

Exercise 5.2.1#

In Huffman coding compression, it is necessary to include a header in the compressed file containing the information needed to decode the file. In your implementation, the header is likely a serialized version of the trie (the result of a preorder traversal), as proposed in the textbook. Do you think it would be more or less efficient in terms of memory to store the binary encoding of each symbol directly rather than the serialized trie?

Exercise 5.2.2#

Can we achieve an even better compression ratio if we reapply Huffman’s compression algorithm to a file that has already been 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 to a file with a single string consisting of the character “a” repeated a million times (\(\approx 2^{20}\)), followed by the character b occurring 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 that achieves higher compression than Huffman coding in this particular case?

Can the Huffman compression algorithm be used for inputs other than text files (for instance, an image)? What would the algorithm count in this case?

Exercise 5.2.4 (INGInious: Linked Heap)#

Imagine a heap implementation of a priority queue using a linked 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 and delMax. What are their time complexities? Is it necessary to specify a maximum capacity \(N\) in the constructor? How do you add a new node to the heap or remove the last node? Can this be determined from the current heap size?

Implement the min priority queue using a linked structure for representing the heap: MinPQLinked

Exercise 5.2.5 (INGInious: Min-Max Heap)#

Propose a data structure that supports the following operations in logarithmic time: insert, remove maximum, remove minimum; and the following operations in constant time: find maximum and find minimum. For this, we consider the min-max heap data structure. The even levels are: 0 (root), 2, 4, etc. These even levels are called the \(\min\) levels. The odd levels are 1, 3, 5, etc. These odd levels are called the \(\max\) levels. For any element \(x\) in the min-max heap, the following property holds:

  • If \(x\) is at a \(\min\) level, all descendants of \(x\) are greater than or equal to \(x\).

  • If \(x\) is at a \(\max\) level, all descendants of \(x\) are less than or equal to \(x\).

Questions related to this min-max heap:

  • Where is the smallest element of the heap located?

  • Where is the largest element of the heap located?

  • 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 pseudocode.

Implement the MinMax Heap.

Exercise 5.2.6 (INGInious: MedianHeap)#

Imagine a data structure that supports:

  1. insertion in logarithmic time

  2. find median in constant time

  3. deleting the median in logarithmic time.

Hint: There is a solution that uses two internal heaps.

Before starting your implementation, think about the class invariant or property that you want to maintain between the two heaps after each operation.

Implement the MedianHeap.

Exercise 5.2.7 (INGInious: Ternary Heap)#

Implement a ternary heap where each node has up to three children rather than two. Be careful here: we store the values starting at index 0 rather than index 1 as in the binary heap, because the formulas \(2k\) and \(2k+1\) do not apply to the ternary case. What is the time complexity for the insert and delMax operations?

Implement the TernaryHeap.