The Australian National University Semester 2, 2020 Research School of Computer Science Tutorial 6
COMP3600/6466 – Algorithms
This tutorial is compiled by:
Cormac Kikkert, William Cashman, and Hanna Kurniawati
Problems with a ! denote tougher optional challenges that you should use to extend yourself. Only work on these after solving and understanding all the other problems and don’t worry if you can’t solve them.
Update 30 Sep 2020:
1. Ex.1.1.: O(klogn+n) is supposed to be O(nlogk+n). 2. Ex.2.1.: (1,2,3,4,5,6) is supposed to be (1,2,3,4,5,6,7).
Exercise 1 Heaps
1. Please devise a O(n log k + n) algorithm of merging k sorted lists with a total of n elements.
2. Mr PQ said that he had created extremely efficient Extract-Max and Build-Heap operations for Max-Heap data structures that rely on comparison operation (i.e., the heap data structure as discussed in class). In particular, he claimed the following worst time complexity for his algorithms:
• Extract-Max runs in Θ(1) time (Recall: Extract-Max includes retrieving an element from the heap and fixing the heap) AND
• Build-Heap runs in Θ(n) time
Could Mr PQ’s claim be True? Please explain why or why not.
Exercise 2 Red-Black Trees
1. Given the numbers (1,2,3,4,5,6,7). Create a valid Red-Black tree that stores these numbers as keys using:
(a) Whatever method you like (try guessing what it will look like and see if you can label the nodes to make a valid Red-Black tree!)
(b) By starting with an empty tree and calling the Insert procedure on every node element to build the tree.
(c) By only using black nodes.
2. What is the maximum number of red nodes in a Red-Black tree with n nodes?
3. What will a Red-Black tree with no red nodes look like? What will the shortest distance between a leaf node and the root be?
4. Draw a Red-Black tree with 15 elements that has height 6
Exercise 3 Hash Tables
1. Demonstrate what happens when we insert the keys 5; 28; 19; 15; 20; 33; 12; 17; 10 into a hash table with collisions resolved by chaining. Let the table have 9 slots, and let the hash function be h(k) = kmod9. [CLRS 11.2-2].
1
2. Suppose we have stored data in a hashing with chaining data structure, and suppose the hash function used is a simple uniform hash function. Will there be benefit in time complexity of search if the linked list were sorted based on keys? Will there be a benefit if you are allowed to change what each slot in the hash table stores? Please explain. [CLRS 11.2-3].
3. Suppose we have the following collection of hash functions {h1, h2, h3}, that maps {a, b, c, d} of keys into the range {0, 1, 2} as follows:
• h1(a) = 1,h1(b) = 0,h1(c) = 0,h1(d) = 1 • h2(a) = 0,h2(b) = 2,h2(c) = 1,h2(d) = 0 • h3(a) = 2,h3(b) = 1,h3(c) = 0,h3(d) = 0
If m = 5, would the above set of hash functions be a family of universal hash functions? Please explain why or why not. Hint: Recall the definition.
4. Considerinsertingthekeys10;22;31;4;15;28;17;88;59intoahashtableoflengthm=11 using open addressing with double hashing, where h1(k) = k and h2(k) = 1 + (k mod(m − 1)). Please illustrate this insertion [CLRS 11.4-1].
Exercise 4 Tree Applications
1. Let A[1···n] be an array of n numbers, where n is a power of 2. Come up with a data structure that can perform the following operations in O(log n) time.
• Set(i, y) – Set A[i] to y
• Sum(i) – Return the sum of the first i numbers
Hint: Make a tree with n leaves, with each leaf corresponding to an element of A.
2. ! Explain how you can use the previous idea on an AVL/RB tree to handle the following additional
query, also in O(log n) time:
• Push(y) – Append the value y to the end of A, increasing the length by 1
Hint: After changing the tree how many nodes do you have to recalculate information for?
2