School of Computing and Information Systems
COMP90038 Algorithms and Complexity Tutorial Week 9
17–21 September 2018
Plan
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: 1 < 8 > 3 < 4 < 6 .
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.
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?