Data Structures and Algorithms
1. Traversals of BSTs. [5 marks total; 1 mark each]
Suppose that we have numbers between 1 and 1000 in a binary search tree (BST), and we want to search
for the number 363. For each of the following sequences, is it a valid sequence of nodes examined?
How can you tell?
(a) 2, 252, 401, 398, 330, 344, 397, 363.
(b) 924, 220, 911, 244, 898, 258, 362, 363.
(c) 925, 202, 911, 240, 912, 245, 363.
(d) 2, 399, 387, 219, 266, 382, 381, 278, 363.
(e) 935, 278, 347, 621, 299, 392, 358, 363.
2. Operations on BSTs. [10 marks total; 5 marks each]
(a) Write a recursive function that returns the minimum key value in a binary search tree of distinct
(positive) integers. Return -1 in case the tree is empty.
(b) Write a recursive function that returns the predecessor of the key value k in a binary search tree
of distinct (positive) integers. This is the key value that precedes k in an inorder traversal of the
tree. If k does not exist, or if k has no predecessor, your function should return -1.
3. Properties of BSTs. [10 marks total; 5 marks each]
(a) Professor Paul thinks he has discovered a remarkable property of BSTs. Suppose that the
search for key value k in a BST ends up in a leaf. Consider three sets: A, the keys to the left of
the search path; B, the keys on the search path; and C, the keys to the right of the search path.
Professor Paul claims that any three keys a 2 A, b 2 B, and c 2 C must satisfy a ? b ? c.
Give a smallest possible counterexample to the professor’s claim.
(b) Show that if a node in a BST has two children, then its successor has no left child, and its
predecessor has no right child.
4. AVL Trees. [10 marks total; 5 marks each]
An AVL tree is a BST in which the balance factor of every node, which is defined as the di?erence
between the heights of the node’s left and right subtrees, is either 0, or +1, or -1. In Figure 1, only
the tree in part (a) is an AVL tree; (b) has two nodes (4 and 6) that violate 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.
(a) For a n = 1, 2, 3, 4, and 5, draw all the binary trees with n nodes that satisfy the balance requirement
of AVL trees.
(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.
5. Red-Black Trees. [15 marks total]
Show the red-black trees that result after successively inserting the keys 41, 38, 31, 12, 19, 8 into an
initially empty red-black tree. Show your work!
1
(a smallest BST and its search)
(It needs to be a BST.)
i.e., Show your tree after each insertion.
Exercises 6.3
1. Which of the following binary trees are AVL trees?
5
3
2
6
8
5
4
2
6
8
5
3
1 2
6
7 9
( a )
1 3 7 9
( b ) ( c )
2. a. For q = 1> 2> 3> 4> and 5, draw all the binary trees with q nodes that
satisfy the balance requirement of AVL trees.
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.
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
5. a. For an AVL tree containing real numbers, design an algorithm for
computing the range (i.e., the difference between the largest and smallest
numbers in the tree) and determine its worst-case efficiency.
b.B 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?
6. Write a program for constructing an AVL tree for a given list of q distinct
integers.
7. a. 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.
b. 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.
23
Figure 1: Only the tree in (a) is an AVL tree.
6. B+-Trees. [10 marks; 5 marks each]
In the B+-tree we consider here, all keys are stored at the leaves, in increasing order of key value. The
intermediate nodes are used for indexing. Specifically, each interior node contains m # 1 ordered keys
k1 <…< km!1 assumed for simplicity to be distinct. The keys are interposed with m pointers to the
node’s children so that all the keys in subtree T0 are smaller than k1, all the keys in subtree T1 are
greater than or equal to k1 and smaller than k2 (with k1 being equal to the smallest key in T1), and
so on through the last subtree Tm!1 whose keys are greater than or equal to km!1 with km!1 being
equal to the smallest key in Tm!1.
A B+-tree of order m $ 2 satisfies the following structural properties:
• The root is either a leaf or has between 2 and m children.
• Each node, except for the root and the leaves, has between dm/2e and m children (and hence
between dm/2e # 1 and m # 1 keys).
• The tree is (perfectly) balanced; i.e., all its leaves are at the same level.
Figure 2 shows an example of a B+-tree of order 4.
3. If the tree’s root is stored in main memory, the number of disk accesses
will be equal to the number of the levels minus 1, which is exactly the
height of the tree. So, we need to find the smallest value of the order
p so that the height of the B-tree with q = 108 keys does not exceed
3. Using the upper bound of the B-tree’s height, we obtain the following
inequality
[email protected]
q + 1
4 c + 1 = 3 or [email protected]
q + 1
4 c = 2=
By “trial and error,” we can find that the smallest value of p that satisfies
this inequality is 585.
4. Since there is enough room for 30 in the leaf for it, the resulting B-tree
will look as follows
11 15
4, 7,10 11, 14 15, 16, 19
25 34 40.
20, 24 25, 28, 30 34, 38
60
40, 43, 46 51, 55 60, 68, 80
20 51
Inserting 31 will require the leaf’s split and then its parent’s split:
11 15
4, 7,10 11, 14 15, 16, 19
25 30
20, 24 25, 28 34, 38
60
40, 43, 46 51, 55 60, 68, 80
20 34 51
30, 31
34 40
5. Starting at the root, follow the chain of the rightmost pointers to the
(rightmost) leaf. The largest key is the last key in that leaf.
6. a. Constructing a top-down 2-3-4 tree by inserting the following list of
keys in the initially empty tree:
10, 6, 15, 31, 20, 27, 50, 44, 18.
24
Figure 2: A B+-tree of order 4.
(a) State two major di?erences of B-trees compared to other balanced BSTs.
(b) An upper bounds on the height h of a B+-tree of order m with n nodes is: h ? blogdm/2e n+1
4 c+ 1.
Use this to find the minimum order of the B+-tree that guarantees that the number of disk accesses
in searching a file of 100 million records does not exceed 3. Assume that the root’s page is stored
in main memory.
7. Binomial Coe!cients. [15 marks; 5 marks each]
You may recall that the binomial coe!cient, denoted C(n, k) or !n
k
”
, is the number of combinations
2
(subsets) of k elements from an n-element set (0 ? k ? n). The name “binomial coe”cients” comes
from the participation of these numbers in the binomial formula:
(a + b)
n = C(n, 0)an + … + C(n, k)an!kbk + … + C(n, n)bn.
Of the numerous properties of binomial coe”cients, we focus on two:
C(n, k) = C(n # 1, k # 1) + C(n # 1, k) for n>k> 0
C(n, 0) = C(n, n)=1
(a) Give pseudocode for a dynamic programming algorithm to compute C(n, k) that uses only additions.
[5 marks]
(b) What is the time and space e”ciency of your algorithm? [5 marks]
(c) Find the exact number of additions made by your algorithm, i.e., set up an expression A(n, k)
counting the total number of additions made by your algorithm in computing C(n, k) and solve
it exactly. [5 marks]
8. The Coin Collection Problem. [25 marks]
In the coin collection problem, coins are placed in cells of an n ? m board, with no more than one coin
per cell. A robot, located in the upper left cell, position (1, 1), of the board, needs to collect as many
of the coins as possible and bring them to the bottom right cell (position (n, m)). In each step, the
robot can move either one cell to the right or one cell down from its current location. When the robot
visits a cell with a coin, it always picks up the coin located there.
(a) Give pseudocode for a dynamic programming algorithm to find the maximum number of coins
the robot can collect and a path it needs to follow in solving the coin collection problem. Analyze
the time and space requirements of your algorithm. [10 marks]
(b) Now, modify the dynamic programming algorithm in part (a) for the case where some cells on
the board are inaccessible to the robot. Are there any changes to the time or space requirements
of your algorithm? [5 marks]
(c) Apply your algorithm to the board in Figure 3, where the inaccessible cells are marked by X’s.
[5 marks]
(d) How many optimal paths are there for the board in Figure 3? [5 marks]
This file contains the exercises, hints, and solutions for Chapter 8 of the
book ”Introduction to the Design and Analysis of Algorithms,” 3rd edition, by
A. Levitin. The problems that might be challenging for at least some students
are marked by B; those that might be difficult for a majority of students are
marked by I =
Exercises 8.1
1. What does dynamic programming have in common with divide-and-conquer?
What is a principal difference between them?
2. Solve the instance 5, 1, 2, 10, 6 of the coin-row problem.
3. a. Show that the time efficiency of solving the coin-row problem by
straightforward application of recurrence (8.3) is exponential.
b. Show that the time efficiency of solving the coin-row problem by exhaustive
search is at least exponential.
4. Apply the dynamic programming algorithm to find all the solutions to
the change-making problem for the denominations 1, 3, 5 and the amount
q = 9=
5. How would you modify the dynamic programming algorithm for the coincollecting
problem if some cells on the board are inaccessible for the robot?
Apply your algorithm to the board below, where the inaccessible cells are
shown by X’s. How many optimal paths are there for this board?
6. B Rod-cutting problem Design a dynamic programming algorithm for
the following problem. Find the maximum total sale price that can be
obtained by cutting a rod of q units long into integer-length pieces if the
sale price of a piece l units long is sl for l = 1> 2> ===> q= What are the time
and space efficiencies of your algorithm?
1
Figure 3: An 5 ? 6 board for the coin collection problem, Question 8, parts (c) and (d).
PLACE THIS ORDER OR A SIMILAR ORDER WITH US TODAY AND GET A GOOD DISCOUNT
