School of Computing and Information Systems
COMP90038 Algorithms and Complexity Tutorial Week 9
Sample Answers
The exercises
(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
14
19
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
G
A I
H
R
O
M
T
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: I
G
A H
O
L M R T
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:
2 4
1 3 5
Inserting 2, 3, 4, 5, 1, in that order, we produce this 2–3 tree:
3
1 2 4 5
These are the only possible 2–3 trees with the five given keys.