Due by: December 3, 2003
Submit: by e-mail to TA at bdrew@cs.gmu.edu
(In the subject specify: CS483-002 HW4)
1. (5 points) (See exercise 12.3-6) Rewrite a BST Tree-Delete algorithm to implement a fair strategy in which splicing out a predecessor or a successor have equal priority. Think of the most concise way to write such algorithm.
2. (5 points) (See exercise 15.4-5) Write an O(n2)-time algorithm to find the longest monotonically increasing subsequence of a sequence of n numbers.
3. (Bonus 1 point) (See exercise 13.2-1) Write pseudocode for the Right-Rotate procedure on a red-black tree.