Homework Assignment #5 Solution

Question 1. (20 marks) Consider the forest implementation of the disjoint-sets abstract data type, with an initial forest of n distinct elements (each one in a one-node tree). Let be any sequence of k UNIONs followed by k0 FINDs; so all UNIONs occur before the FINDs. Prove that the algorithm using Path Compression only (it does not use the Weighted-Union rule) executes in O(k + k0 ) time, i.e., in time proportional to the length of , in the worst-case.




Do not make assumptions on k or k0 (for example, do not assume that k = n 1 or that k0 k). As we did in class, assume that the parameters of each UNION are two set representatives, i.e., two tree roots (so there are no FINDs \inside" each UNION).




Hint: To compute the \cost" of executing all the FINDs use an amortization-like charging scheme.




Question 2. (36 marks) Consider the following data structure for representing a set I of integers. The elements of the set are stored in a doubly linked list of arrays such that: (1) Each element of I occurs in exactly one of the arrays in this list, (2) each array is sorted in increasing order, (3) the number of elements in each array is a power of 2, (4) no two arrays in the list have the same size, and (5) the arrays in the linked list are kept in order of increasing size. Note that although each array is sorted, there is no particular relationship between the elements in di erent arrays.




a. (4 marks) Draw two instances of this data structure: one for set I = f3; 5; 1; 17; 10g and one for set




= f17; 8; 3; 10; 1; 12; 6g.



b. (6 marks) To do a Search(x) for an integer x in this data structure, one performs a binary search separately on each array in the list until either x is found in some array, or all arrays have been considered and x is not found.




Give a good upper bound on the worst-case time complexity of this Search algorithm (using the O notation) and justify your answer.




c. (6 marks) To do Insert(x), i.e, to insert a new integer x into I (assume that x is not already in I), one performs following algorithm:




create a new array of size 1 containing x



insert this new array at the beginning of the linked list



while the linked list contains 2 arrays of the same size:



merge the 2 sorted arrays into one sorted array of twice the size.




To do each merging use a procedure similar to the one used in Mergesort.




Give a good upper bound on the worst-case time complexity of this Insert algorithm (using the O notation) and justify your answer.




d. (12 marks) Suppose we execute a sequence of n Inserts starting from an empty set I. Determine a good upper bound on the amortized time of an Insert (i.e., the worst-case total time to execute these n Inserts divided by n). Justify your answer in two di erent ways, i.e., give two separate proofs, each proof using a di erent argument (e.g., use aggregate analysis and the accounting method).




e. (8 marks) Describe an algorithm to perform a Delete(x) operation (i.e., given a pointer to integer x in one of the arrays of the list, remove x) in O(n) time in the worst case. There is no need to use pseudocode, a clear and concise description of the algorithm in English is su cient. Explain why the worst-case time complexity of your algorithm is O(n).