Kingdom of Saudi Arabia ‫المملكة العربية السعودية‬

Ministry of Education ‫وزارة التعليم‬

Northern Border University ‫جامعة الحدود الشمالية‬
Faculty of Computing and Information Technology ‫كلية الحاسبات و تقنية المعلومات‬

Analysis & Design of Algorithms ( CPCS223) November 2020

Assignment 4
Question A

1. Apply quicksort to sort the list

E, X, A, M, P, L, E

in alphabetical order. Draw the tree of the recursive calls made.

Solution:
Kingdom of Saudi Arabia ‫المملكة العربية السعودية‬
Ministry of Education ‫وزارة التعليم‬
Northern Border University ‫جامعة الحدود الشمالية‬
Faculty of Computing and Information Technology ‫كلية الحاسبات و تقنية المعلومات‬

2. Is quicksort a stable sorting algorithm?

Quicksort is not stable. As a counterexample, consider its performance on a two-element

array of equal values.

Question B:

1. Which of the following binary trees are AVL trees?

Only (a) is an AVL tree; (b) has a node (in fact, there are two of them: 4 and 6) that violates the
balance requirement; (c) is not a binary search tree because 2 is in the right subtree of 3 (and 7 is in
the left subtree of 6).

2. a. For n = 1, 2, 3, 4, and 5, draw all the binary trees with n nodes that satisfy the balance
requirement of AVL trees.
Kingdom of Saudi Arabia ‫المملكة العربية السعودية‬
Ministry of Education ‫وزارة التعليم‬
Northern Border University ‫جامعة الحدود الشمالية‬
Faculty of Computing and Information Technology ‫كلية الحاسبات و تقنية المعلومات‬

b. Draw a binary tree of height 4 that can be an AVL tree and has the smallest number of nodes
among all such trees.
Kingdom of Saudi Arabia ‫المملكة العربية السعودية‬
Ministry of Education ‫وزارة التعليم‬
Northern Border University ‫جامعة الحدود الشمالية‬
Faculty of Computing and Information Technology ‫كلية الحاسبات و تقنية المعلومات‬
Kingdom of Saudi Arabia ‫المملكة العربية السعودية‬
Ministry of Education ‫وزارة التعليم‬
Northern Border University ‫جامعة الحدود الشمالية‬
Faculty of Computing and Information Technology ‫كلية الحاسبات و تقنية المعلومات‬

3. Draw diagrams of the single L-rotation and of the double RL-rotation in their general form.

4. For each of the following lists, construct an AVL tree by inserting their elements successively,
starting with the empty tree.

a. 1, 2, 3, 4, 5, 6

b. 6, 5, 4, 3, 2, 1

c. 3, 6, 5, 1, 2, 4
Kingdom of Saudi Arabia ‫المملكة العربية السعودية‬
Ministry of Education ‫وزارة التعليم‬
Northern Border University ‫جامعة الحدود الشمالية‬
Faculty of Computing and Information Technology ‫كلية الحاسبات و تقنية المعلومات‬
Kingdom of Saudi Arabia ‫المملكة العربية السعودية‬
Ministry of Education ‫وزارة التعليم‬
Northern Border University ‫جامعة الحدود الشمالية‬
Faculty of Computing and Information Technology ‫كلية الحاسبات و تقنية المعلومات‬

5. True or false: The smallest and the largest keys in an AVL tree can always be found on either the
last level or the next-to-last level?

False

Question C:

1. 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.)
Kingdom of Saudi Arabia ‫المملكة العربية السعودية‬
Ministry of Education ‫وزارة التعليم‬
Northern Border University ‫جامعة الحدود الشمالية‬
Faculty of Computing and Information Technology ‫كلية الحاسبات و تقنية المعلومات‬

2. Assuming that the probabilities of searching for each of the keys (i.e., the letters) are the same,
find the largest number and the average number of key comparisons for successful searches in this
tree.