\$30.00

Category:

Description

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 different arrays.

a. (4 marks) Draw two instances of this data structure: one for set I = {3, 5, 1, 17, 10} and one for set

I = {17, 8, 3, 10, 1, 12, 6}.

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

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:

(a) create a new array of size 1 containing x

(b) insert this new array at the beginning of the linked list

(c) 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)