The exercises
School of Computing and Information Systems COMP90038 Algorithms and Complexity
Tutorial Week 9 Sample Answers
(Solutions to 56–59 were provided earlier.)
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 .
Answer: At first it is not clear that this is always possible. However, here is an algorithm. First sort the sequence. Now fill in the boxes from left to right, as follows. If there is a < after the box, remove the smallest element from the list and place it in the box. If there is a > after the box, remove the largest element from the list and place it in the box. Finally place the only remaining element in the last box. Note that some problem instances will have many solutions, but this algorithm is guaranteed to produce one solution.
To see why the algorithm works, think recursively. We want to be able to produce a solution for n boxes, assuming we already have a solution for the last n − 1. We can always do that if we have reserved the first box for the appropriate extreme element (the smallest if there is a < after the box, otherwise the largest).
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.
Answer:
17
13 19
14 18 26 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.
Answer:
L GR AI OT
HM
Copyright © University of Melbourne 2021
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?
Answer: Without loss of generality, assume the set of keys is {1, 2, 3, 4, 5}. After the first three keys are inserted to make an AVL tree, that tree must be perfectly balanced. Hence the first three keys inserted must cause the ⟨ zigzag path that requires an LR-rotation. After that, insertion of the two remaining keys must cause the ⟩ zigzag path that requires an RL-rotation. The only permutations that will achieve this are 3, 1, 2, 5, 4 and 5, 1, 4, 3, 2.
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.
Answer:
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?
Answer: Inserting 1, 2, 3, 4, 5, in that order, we produce this 2–3 tree: 24
135 Inserting 2, 3, 4, 5, 1, in that order, we produce this 2–3 tree:
3
12 45
These are the only possible 2–3 trees with the five given keys.
I GO
AHLMRT
Copyright © University of Melbourne 2021