COSC 2123/1285
COSC 2123/1285 Algorithms and Analysis
Workshop 6
Divide and Conquer Algorithmic Paradigm
Tutorial Exercises
Objective
Students who complete this tutorial should:
• Understand the concepts of divide and conquer.
• Be familiar with the way this concept can be applied to sorting problems.
Questions
5.1.6 Apply mergesort to sort the list E, X, A, M, P, L, E in alphabetical order.
5.2.1 Apply quicksort to sort the list E, X, A, M, P, L, E in alphabetical order.
5.1.7 Is mergesort a stable sorting algorithm?
5.2.3 Is quicksort a stable sorting algorithm?
5.1.1
a Write a pseudocode for a divide-and-conquer algorithm for finding a position of the largest element
in an array of n numbers.
b What will be your algorithm’s output for arrays with several elements of the largest value?
c Set up and solve a recurrence relation for the number of key comparisons made by your algorithm.
d How does this algorithm compare with the brute-force algorithm for this problem?
5.2.11 Nuts and bolts You are given a collection of n bolts of different widths and n corresponding nuts.
You are allowed to try a nut and bolt together, from which you can determine whether the nut is larger
than the bolt, smaller than the bolt, or matches the bolt exactly. However, there is no way to compare
two nuts together or two bolts together. The problem is to match each bolt to its nut. Design an algo-
rithm for this problem with average-case efficiency of Θ(n log n).
c©2021 RMIT University 1
COSC 2123/1285
Practical Exercises
1 Objective
Students who complete this lab should learn how to implement binary search trees in Java and gain
greater understanding of them.
2 Binary Search Tree
A binary search tree (bst) is a data structure that facilitates search using a binary tree to store data. A
search for an element X in a bst is successful if there exists a node in the binary tree corresponding to
the value X. Values in a bst are stored to satisfy the following property: Each internal node x stores an
element such that the elements stored in the left subtree of x are less than x and elements stored in the
right subtree of x are greater than x. This is the called binary search tree property.
2.1 Traversal
Tree-traversal refers to the process of recursively visiting (examining and/or updating) each node in a tree
data structure, exactly once, in a systematic way. Such traversals are classified by the order in which the
nodes are visited. Starting at the root of a binary tree, there are three main steps that can be performed
and the order in which they are performed defines the traversal type. These steps are: performing an
action on the current node (referred to as “visiting” the node), traversing to the left child node, and
traversing to the right child node. Although we didn’t go through this in lectures, it is interesting to
know about traversals. Consider the following traversal approaches and example:
54
27
13
1
44
37
89
71
64
92
In preorder traversal, the root is visited before the
left and right subtrees are visited:
1. Visit the root.
2. Traverse the left subtree.
3. Traverse the right subtree.
In inorder traversal, the root is visited after the
left subtree and before the right subtree is visited:
1. Traverse the left subtree.
2. Visit the root.
3. Traverse the right subtree.
In postorder traversal, the root is visited after the
left and right subtrees are visited:
1. Traverse the left subtree.
2. Traverse the right subtree.
3. Visit the root.
Traversal methods
Pre: 54,27,13,1,44,37,89,71,64,92
In: 1,13,27,37,44,54,64,71,89,92
Post: 1,13,37,44,27,64,71,92,89,54
2.2 Implementation
Your task in this laboratory is to experiment with the graph traversals and implement a number of
different operations. Download the provided source code BSTDemo.java and BST.java from Blackboard.
The following methods are provided in BST.java:
• insert() — insert an element into the bst.
c©2021 RMIT University 2
COSC 2123/1285
• inorder() — traverse the bst in inorder, printing out the element of nodes as we visit them
• preorder() — traverse the bst in preorder, printing out the element of nodes as we visit them
• postorder() — traverse the bst in postorder, printing out the element of nodes as we visit them
You are to implement the following methods for a binary search tree in BST.java:
• search() — search for an element in the bst. Hint: Use insert() as your initial guide on how to
implement search.
• min() — return the minimum element in the bst. Hint: Remember the semantics of a binary
search tree.
• max() — return the maximum element in the bst. Hint: Remember the semantics of a binary
search tree.
• height() — calculate the height of the bst. Hint: height of a node = height of parent + 1.
You can compile the finished program using the command:
javac BSTDemo.java BST.java
2.3 Running your code
The provided skeleton code allows you to dynamically modify the bst using a “mini” command shell:
$ java BSTDemo
i n s e r t 9
i n s e r t 4
i n s e r t 12
i n s e r t 7
i n s e r t 3
i n s e r t 6
i n s e r t 18
i n s e r t 25
p r i n t a s c i i
9
/ \
/ \
4 12
/ \ \
3 7 18
/ \
6 25
end
2.4 Testing your code
The provided skeleton code reads data from stdin and executes operations accordingly. Two test files
test01.in and test02.in the corresponding expected outputs test01.exp and test02.exp are provided
for you to test your program.
First run your program reading the inputs from stdin and write the output to file using the following
command:
java BSTDemo < test01.in > test01.out
Then compare your output to the expected output:
diff test01.exp test01.out
c©2021 RMIT University 3
COSC 2123/1285
3 Challenges
• All recursive functions can be unwound. How would you implement an iterative tree traversal?
c©2021 RMIT University 4