Problem 3. The oracle and the mysterious answer.

In the search for the meaning of life, you set off for a dangerous trip to visit a mysterious oracle living in a temple at the heart of the Great Victoria Desert. Barely escaping a terrible sand storm, you’ve finally found the oasis at a great cost: all the supplies have been buried under the sand and the only camel has run away. To make it worse, there is no sign of any source of water and all the plants surrounding the temple are dead. Apparently the oasis has been drying up for quite some time.

Staggering into the temple, surprisingly, you find the oracle, who seems to be waiting for you. “Speak, human! You can ask me one question.” What a hoarse and emotionless voice! Is it because she has not had water for a long time? “Oracle, I... ”, You hesitate. Before going, you had a list of all deep-meaning questions prepared. But now, what the heck! Licking your chapped lips, you ask “Oracle... where can I find water?” The oracle regards you for almost five seconds, and then asks “Computer scientist, yes?” “Y... yes,” you reply, clearing your throat. She’s an oracle after all. But you suddenly have this strange thought: what did the oracle do for a living before taking this... job? But surely you cannot ask a second question. The oracle immediately pulls out a piece of paper and a pen, writes something down and hands it to you eagerly as if she has been waiting to do this for a long time. Although it is rather dim in the temple, you can still feel her intense gaze under the veil. “The answer is in the solution,” said the oracle, still with her emotionless voice. You turn toward the door to get some more light. It is a vaguely familiar problem about a compression algorithm. Not again!!! You groan and turn back to face the oracle, ready to shoot another question or at least, a complaint. But there is nobody there... But the unbearable thirst reminds you that you should not worry about the oracle’s whereabouts. The answer for where to find the water is in the solution, and you need to crack the problem first. Is the oracle helpful? Or does she just want to play? There’s only one way to find out...

Oracle’s problem. There are ten letters whose frequencies are given in Table 2.

a) Construct a min-heap (tree) using the bottom-up heap construction to represent the frequencies in Table 2 (using the given order). Please use (label:frequency), for example, “H:1”, for nodes in the heap. Describe (draw) all the steps required (use two-head arrows to indicate an exchange between two nodes). Note that a min-heap is the same as a max-heap, except that the key stored at a parent node is required to be smaller than the keys stored at its two children nodes.

b) Illustrate (draw) the process of dequeuing the two letters of smallest frequencies from the heap one by one (dequeue -> repair -> dequeue -> repair).

c) Illustrate (draw) the process of enqueuing the new element (i.e. enqueue -> repair), which results from the combination of frequencies of the two dequeued elements earlier. For example, if ‘H:1’ and ‘Y:2’ were dequeued, then the new element ‘HY:3’ would be enqueued.

d) Provide a complete construction of the Huffman tree (3 marks) together with the codes for all letters (1 mark). Only the complete final tree needs to be given. However, each intermediate node must be labelled with both frequencies, e.g. “3”, and the step in which it is constructed, e.g. “Step 1”. When constructing the trees, the following rule applies: for every node from the root, the frequency of its left child must be smaller than or equal to that of its right child.