CSCI 4041 Algorithms and Data Structures - Spring 2025
Homework 4 - Trees and Optimization
Due Date: Friday, April 11, 2025 by 11:59pm.
Instructions: This is an individual homework assignment. You may work together to discuss con-cepts, but the solutions must be your own work. Submit your answers on Canvas, which is linked to Gradescope (be sure to correctly map the page for each problem). We will not grade *Practice Problems*, however, you are responsible for knowing how to solve them in order to prepare for quizzes and exams.
Problem H4.1: BSTs and Rotations (20 points)
Consider the following algorithm.
SUCCESSIVE-RIGHT-ROTATES(z)
1 if z != NIL
2 while z.left != NIL
3 RIGHT-ROTATE(T, z)
4 z = z.p
5 return z
(a) Draw the tree that results from applying SUCCESSIVE-RIGHT-ROTATES where the input z is the root of the tree below.
(b) Let T be any BST, and n the number of nodes. What is best case asymptotic runtime of SUCCESSIVE-RIGHT-ROTATES over all BSTs of size n? What is the worst case? (Hints: (i) the runtime will be related to the number of right rotations. (ii) Note another way to think about this question is what type of BST with n nodes will result in the fewest rotations, and what type will will result in the most rotations?)
(c) Consider the algorithm below.
ALG-HW4(T)
1 z = T.root
2 while z != NIL
3 z = SUCCESSIVE-RIGHT-ROTATES(z)
4 z = z.right
Draw the tree that results from applying ALG-HW4 to the (original) BST is part (a).
(d) What is worst case asymptotic number of right rotations (over all BSTs of size n) done by ALG-HW4? State the runtime and provide a brief justification, although you do not need to provide a rigorous proof.
Problem H4.2: AVL Trees (20 points)
Recall that to handle the LR case in an AVL tree tree for a node x with ∣balance factor∣ > 1, we first LEFT-ROTATE(T, x.left) and then RIGHT-ROTATE(T, x). We call two successive rotations like this a double rotation.
For each of the double rotation algorithms described below, do the following:
1. Draw the the double rotation in a figure similar to Figure 13.2. Your diagrams should (i) show the relationship changes between nodes x, y, z and the parent; (ii) include subtrees α, β, γ, and ω; (iii) show how the height of the nodes x, y, and z have changed from their previous heights (since for an AVL tree we will need to calculate the balance factor at each node).
2. In pseudocode or another language of your choice, write the following double rotation functions as direct changes to the pointers and any other needed information, e.g., the height at each node (x.height). Do this directly, that is, do not call other rotation functions.
(a) RL-ROTATE(T, x):
Let y = x.right and z = y.left
Double Rotation: RIGHT-ROTATE(T,y) and then LEFT-ROTATE(T,x)
(b) DOUBLE-RIGHT-ROTATE(T, x):
Let y = x.left and z = y.left
Double Rotation: RIGHT-ROTATE(T,x) and then RIGHT-ROTATE(T,y)
(c) REVERT-LR(T, x) (*Practice Problem*):
Let x = y.right and z = y.left
Double Rotation: LEFT-ROTATE(T,y) and then RIGHT-ROTATE(T,y)
Problems H4.3: Red-Black Trees (20 points)
Let T be a red-black tree and define
Φ(T) = (number of black nodes with no red children)
+2 (number of black nodes with two red children).
What is the change in Φ(T) in each of the following cases? For each case give a justification of your answer.
[Note: for all parts below there might not be a single answer. That is, Φ might change by different amounts depending upon the whether certain nodes involved are red or black. In such cases list all possible potential changes that might result (e.g., change = 1, 0, −1) and explain when each such change will occur.]
(a) After inserting a new node, but before applying RB-INSERT-FIXUP (regardless of whether the fixup would be needed after the insertion or not). Note: RB-INSERT-FIXUP, described in Section 13.3, fixes the tree if any of the red-black properties are violated after insert.
(b) After case 3 of RB-INSERT-FIXUP.
(c) After case 1 of RB-INSERT-FIXUP. (*Practice Problem*)
Problems H4.4: B-Trees (20 points)
Consider the 2-3-4 tree below
(a) Show the resulting tree after A is inserted using B-TREE-INSERT.
(b) Show the resulting tree after B is inserted using B-TREE-INSERT (into the tree from (a)).
(c) Show the resulting tree after Q is inserted using B-TREE-INSERT (into the tree from (b)).
(d) Show the resulting tree after D is inserted using B-TREE-INSERT (into the tree from (c)).
Problems H4.5: Dynamic Programming (20 points)
Consider the subsequence matching problem. Suppose that X and Y are both sequences of n char-acters. Suppose further than sometimes a character in one sequence will be replaced by a single character in the other sequence, but sometimes it will be replaced by a couple of characters in the other sequence (e.g., the letter ‘f’ may be replaced by ‘ph’ in a misspelling). Moreover, suppose that for each character α in X you have a probability function πα which can take either 1 or 2 arguments.
More specifically,
πα(β) = the probability that α in X is replaced by β in Y
πα(β, γ) = the probability that α in X is replaced by the pair of consecutive characters β, γ in Y .
As an example, consider
with the subsequences consisting of the underlined terms and the matches given by the arrows. The total matching score in this case would be
πb(b) + πc(c, c) + πd(b) + πa(d, a) + πb(b).
Note if a character in X matches a pair in Y those characters must be consecutive in Y — it is not sufficient for them to be consecutive only in the subsequence.
Write down a recurrence for computing the largest possible matching score in O(n
2
) time. Justify the recurrence and the O(n
2
) time. Your justification does not need to be rigorous, but should include enough detail that it is clear what your recurrence measures, how you derived it, and why computing the largest matching score takes O(n
2
) time. Note here you just need to write the recurrence and the justifications. You do not need to actually write the algorithm, nor do you need to be concerned with storing or printing the optimal subsequences.