CS252- Winter 2003- Assignment 4

Fourth assignment--CS252--Winter 2003

Date: March 20, 2003.
Due: March 27, 2003, 2:30pm.

Question 1	Tournament trees. Consider the LLT (linked list of tournaments) data structure, in which the atomic operation is the "merge" of two LLTs. Start with an empty LLT, and insert n items, one by one. Show that the total time after n insertions is O(n).
Question 2	Augmented data structures. Show how to maintain a dynamic set Q of positive integers that supports the operation min-ratio, which gives the magnitude of the smallest ratio of two consecutive numbers in Q. For example, if Q = {1,5,9,15,18,22}, then min-ratio (Q) returns 18/15. Make the operations insert, delete, search and min-ratio as efficient as possible, and analyze their running times.
Question 3	Algorithms. Given are n line segments in the plane in no particular order. Assume that no endpoints coincide. Give an O(n log n) time algorithm for determining whether there exists a pair of intersecting line segments.
Question 4	Least common ancestor. Consider a red black tree which we would like to modify so that it supports the operation least common ancestor (LCA), which takes as input x (a pointer to a node in the tree), y (a pointer to another node in the tree) and returns z, a pointer to the LCA of x and y. The modification (augmentation) should be such that if there are k keys between key[x] and key[y], then the worst-case time is O( log (k+2) ), while insert, delete and search must remain O(log n) in the worst case, and n is the size of the tree. [Note: LCA is easy to perform in O(log n) time, but the O( log (k+2) ) requirement makes this question particularly challenging.]