Exercises A#

Note

You must complete these exercises by Wednesday of W10.

Exercise 5.1.1#

Give the array id[] that results from the following sequence of 6 union operations on an initial set of 10 items using the quick-find algorithm: 3-8, 1-7, 1-8, 9-4, 6-4, 2-0. Your answer must be a sequence of 10 integers. Reminder: the quick-find convention for the union operation p-q is to change id[p] (and all other entries with value id[p]) to id[q].

Exercise 5.1.2#

Give the array id[] that results from the following sequence of 9 union operations on an initial set of 10 items using the weighted quick-union algorithm:

4-6, 3-6, 8-9, 7-0, 1-2, 8-4, 6-5, 1-7, 6-0.

Your answer must be a sequence of 10 integers. Reminder: When merging two trees of the same size, the weighted quick-union algorithm uses the convention to point the root of the second tree to the root of the first tree. Our algorithm uses union by size (number of nodes) and not union by height, nor the path compression technique.

Exercise 5.1.3#

Which of the following id[] array(s) could result from applying the weighted quick-union algorithm on an initial set of 10 items? Reminder: we use union by size (number of nodes), not union by height.

  • 0 8 2 3 4 7 6 8 8 9

  • 4 2 6 6 2 6 6 2 4 2

  • 7 0 0 0 0 1 0 5 1 0

  • 3 3 0 3 0 3 3 3 5 2

  • 1 3 3 6 4 1 6 0 6 8

Exercise 5.1.4#

Give the sequence of keys in the array that results from inserting the sequence of 3 keys 48, 30, and 84 into the following max-oriented heap of size 10:

97, 93, 89, 83, 38, 32, 40, 12, 26, 24.

Your answer should be a sequence of 13 integers.

Exercise 5.1.5#

Give the sequence of keys in the array that results from performing 3 successive delete-the-maximum operations on the following max-oriented heap of size 10:

98, 96, 84, 34, 62, 31, 72, 13, 27, 33.

Your answer should be a sequence of 7 integers.

Exercise 5.1.6#

What are the possible advantages and disadvantages of implementing a priority queue with a heap rather than a list?

Exercise 5.1.7#

Can you find an example of a valid heap \(T\) storing 7 distinct elements such that an inorder traversal of \(T\) visits the elements in decreasing order? What about a preorder or postorder traversal?

Exercise 5.1.8#

Which of the following statements are true for a priority queue implemented as a binary heap? Assume heaps are max-oriented and 1-indexed.

  • In the worst case, inserting a key into a binary heap containing \(N\) keys requires \(\sim \log N\) comparisons.

  • Let \(a[]\) be an array such that \(a[1] > a[2] > \dots > a[N]\) (and \(a[0]\) is empty). Then \(a[]\) satisfies the properties of a binary heap.

  • The internal array of a binary (max-)heap is always sorted in non-increasing order.

  • Given a binary heap of \(N\) distinct keys, deleting the maximum key and then immediately re-inserting it leaves the heap array unchanged (ignoring any array resizing).

Exercise 5.1.9#

Prove that the bottom-up « sink-based » heap construction for heapsort (page 323) runs in \(\mathcal{O}(n)\) time. Hint: Count the number of nodes at level \(h\) of the heap. What is the cost of a sink operation at this level? Sum the costs over all levels. Useful formula: \(\sum_{k=0}^\infty k x^k = \frac{x}{(1-x)^2}\) for \(|x| < 1\).

Exercise 5.1.10#

Is using a priority queue essential to build a Huffman code? Can you design an alternative solution that uses a sorting algorithm? Would its time complexity be better than the original algorithm? Why or why not?

Exercise 5.1.11#

  • What are the different steps in a text compression algorithm that takes a text as input and provides a compressed version of that text as output using Huffman coding? Be specific in your description by isolating each step of the problem. Specify for each step the useful data structures and the time complexity of the operations performed.

  • What are the different steps of a text decompression algorithm that takes as input a compressed version of a text using Huffman coding and provides as output the original text? Be precise in your description by isolating each step of the problem. Specify for each step the useful data structures and the time complexity of the operations performed.

Exercise 5.1.12 (INGInious: Heap)#

Implement the push operation of a binary heap.

Exercise 5.1.13 (INGInious: Global Warming)#

Implement the Global Warming exercise to compute the number of islands using union-find: GlobalWarming

Exercise 5.1.14 (INGInious: Huffman)#

Implement the Huffman tree reconstruction: Huffman

Exercise 5.1.15 (INGInious: Manual Exercise on Union-Find)#

Small manual exercise on Union-Find

Exercise 5.1.16 (INGInious: Manual Exercise on Heaps)#

Small manual exercise on Heaps