Plan
School of Computing and Information Systems COMP90038 Algorithms and Complexity Tutorial Week 9
17–21 September 2018
Questions 56–59 are carried over, in case you missed some of those last week. If you missed other questions, you may have time to make up for that this week.
The exercises
56. Make a max-heap out of the keys A, L, G, O, R, I, T, H, M, using the linear-time bottom-up algorithm.
57. Construct a max-heap from the empty heap by inserting the keys A, L, G, O, R, I, T, H, M, one by one, in that order. Is the result the same as the heap from the previous question?
58. Give an algorithm for deciding whether an array A[1]..A[n] is a heap.
59. Apply the heapsort algorithm to A, L, G, O, R, I, T, H, M.
60. Given a list of n distinct integers and a sequence of n boxes with fixed inequality signs between them, design an algorithm to place the numbers into the boxes while satisfying each inequality. For example, given 4, 6, 3, 1, 8 and the boxes < > < < , we can place the numbers as follows: < > < < .
61. Construct a binary search tree (BST) by starting from an empty tree and inserting these keys, in the given order: 17, 19, 13, 26, 14, 18, 21, 24.
1
8
3
4
6
62. Construct an AVL tree from the empty tree by inserting the following keys in the given order: A, L, G, O, R, I, T, H, M.
63. Consider the set of five keys (let us say they are positive integers) {k1, k2, k3, k4, k5}, satisfying k1 < k2 < k3 < k4 < k5. There are 120 different permutations of these five keys. For exactly two of the 120 permutations, the following happens, when the keys are inserted one by one, in the order given by the permutation, into an initially empty AVL tree: First an LR-rotation takes place, then an RL-rotation takes place. Which two permutations generate that behaviour?
64. Construct a 2–3 tree from the empty tree by inserting the following keys in the given order: A, L, G, O, R, I, T, H, M.
65. Construct a 2–3 tree by inserting keys 1, 2, 3, 4, 5, in that order. Repeat the exercise, but this time insert the keys in this order: 2, 3, 4, 5, 1. Are the trees identical? Considering all possible orderings of the set {1, 2, 3, 4, 5}, how many different 2–3 trees can be produced?
66. (An extra puzzle for the teaching-free week.) Mr. Smith and his wife invited four other couples. When everyone arrived, some of the people shook hands with some of the others. (Of course, nobody shook hands with their spouse, or themselves, and nobody shook hands with the same person twice.) After that, Mr. Smith asked everyone how many times they shook somebody’s hand. He received different answers from all nine! How many times did Mrs. Smith shake hands?