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 a starting set of 10 items with 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 p-q union is to change id[p] (and possibly other inputs) but not id[q].
Exercise 5.1.2¶
Give the array id[] that results from the following sequence of 9 union operations on a 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 a set of 10 items at the beginning? Reminder: we use union by size (number of nodes) and not union by height.
0 8 2 3 4 7 6 8 8 94 2 6 6 2 6 6 2 4 27 0 0 0 0 1 0 5 1 03 3 0 3 0 3 3 3 5 21 3 3 6 4 1 6 0 6 8
Exercise 5.1.4¶
Give the sequence of keys in the table that results from inserting the sequence of the 3 keys 48, 30 and 84 in the following heap (oriented to the maximum) 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 adding 3 successive deletion operations from the maximum in the following heap (oriented to the maximum) 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 infix traversal of T visists the elements in decreasing order? What about an prefix or postfix traversal?
Exercise 5.1.8¶
Which of the following statements are true about a priority queue implemented by a heap? By default heaps are maximum oriented and use an index base starting at 1.
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] > a[N]\) (and \(a[0]\) is empty). Then \(a[]\) satisfies the properties of a binary heap.
The inernal array of a binary (max-)heap is always an array sorted in non increasing order.
Given a binary heap of N distinct keys, deleting the maximum key and then inserting it directly leaves the array of the heap unchanged (we ignore the possible resizing of the array).
Exercise 5.1.9¶
Prove that the bottom-up « sink » construction of a heap for the Heapsort (p323) is done in \(\mathcal{O}(n)\). Hint: count the number of nodes at the \(h\) level of the heap. What is the complexity of a sink at this level. Do the sum for all levels. Useful formula: \(\sum_{k=0}^\infty k x^k = x/(1-x)^2\) for \(|x| < 1\).
Exercise 5.1.10¶
Is the use of a priority queue essential to be able to build a Huffman code? Can you imagine another solution using a sorting algorithm? Would the computational 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 of a binary Heap
Exercise 5.1.13 (Inginious, Global Warming)¶
Implement the Global Warming to compute the number of islands using union-find GlobalWarmming
