COSC 2123/1285
COSC 2123/1285 Algorithms and Analysis
Workshop 7
Transform and Conquer Algorithmic Paradigm
Tutorial Exercises
Objective
Students who complete this tutorial should:
• Be familiar with the three major variations of transform-and-conquer.
• Be able to apply transform-and-conquer strategies to different problem type
Questions
6.1.5 To sort or not to sort? Design a reasonably efficient algorithm for solving each of the following
problems and determine its efficiency class.
a You are given n telephone bills and m checks sent to pay the bills (n ≥ m). Assuming that telephone
numbers are written on the checks, find out who failed to pay. (For simplicity, you may also assume
that only one check is written for a particular bill and that it covers the bill in full.)
b You have a file of n student records indicating each student’s number, name, home address, and
date of birth. Find out the number of students from each of the 50 U.S. states.
6.3.1 Which of the following binary tress are AVL trees?
(a) (b) (c)
6.3.4 Construct an AVL tree for the list 3, 6, 5, 1, 2, 4.
6.3.7a Construct a 2–3 tree for the list C, O, M, P, U, T, I, N, G (Use the alphabetical order of the
letters and insert them successively starting with the empty tree.)
6.4.1 Construct a heap for the list 1, 8, 6, 5, 3, 7, 4 using the algorithm described in the lecture
notes.
c©2021 RMIT University 1
COSC 2123/1285
Practical Exercises
1 Objective
Students who complete this lab should:
• Improve their understanding of rotations and rebalancing in AVL trees.
2 Introduction
In lectures, we have studied AVL trees and how to do insertion and rotations to maintain the balance
of the tree. To help you gain a greater understanding, in this laboratory exercise, you will implement
two of these rotations to rebalance the tree, then test your implementation on sample input to convince
yourselves that the rotations do maintain tree balance.
3 Provided Code
Similar to the previous laboratory on BST, AVLDemo.java is an interactive command line program that
can execute commands to build and print an AVL tree.
The following files are provided:
file description
AVLTree.java Skeleton code that implements much of the expected functionality of an AVL tree. You are
to implement two of the four rotations and complete the insert functionality.
AVLDemo.java Implements an interactive command line program to build and print an AVL tree.
Compile the program using the following command:
javac *.java
c©2021 RMIT University 2
COSC 2123/1285
3.1 Running your code
The provided skeleton code allows you to dynamically modify the AVL tree using a interactive command
shell. The following commands are available:
• insert ¡element¿ – if element is not a duplicate, then creates a node containing the element and
insert into the tree. This may cause the tree to rebalance.
• height – prints out the height of the tree.
• print ascii – prints out tree in ascii.
• quit/end – terminates the program.
As an example, here is a sample output from typing in the insert, print ascii and height commands:
$ java AVLDemo
i n s e r t 10
i n s e r t 4
i n s e r t 3
i n s e r t 15
i n s e r t 12
i n s e r t 20
i n s e r t 7
i n s e r t 8
i n s e r t 14
i n s e r t 11
p r i n t a s c i i
12
/ \
/ \
/ \
/ \
8 15
/ \ / \
/ \ / \
4 10 14 20
/ \ \
3 7 11
he ight
Height = 3
end
4 Task
In AVLDemo.java, we have implemented two rotations, left (method leftRotation()) and right-left
(method rightLeftRotation() rotations and when they are used (method insert()). Study these, and
use them to help you implement the remaining two rotations, in addition to completing the implemen-
tation of the insert method() to rebalance the tree when the inserted element was inserted into the left
subtree.
• Right rotation (method rightRotation()).
• Left-right rotation (method leftRightRotation()).
• Implement the case where insert key is less than current root node’s key (see method insert()).
c©2021 RMIT University 3
COSC 2123/1285
4.1 Testing your code
Use the interactive shell to insert different values into an AVL tree, to convince yourself that the AVL tree
is working and help you study how it works. We have provided you with one sample test file test01.in
and the corresponding expected output test01.exp to test your program.
First run your program reading the inputs from stdin and write the output to file using the following
command:
java AVLDemo < test01.in > test01.out
Then compare your output to the expected output:
diff test01.exp test01.out
c©2021 RMIT University 4