Chapter 21, Problem 1P

(a)

Program Plan Intro

To finds the correct values in the extracted array of sequence $4,8,E,3,E,9,2,6,E,E,E,1,7,E,5$ for off-line minimum problem.

Explanation of Solution

The EXTRACT-MIN algorithm is used to extract the minimum values from the cluster of number.

The INSERT algorithm is used to insert the value after the minimum value in the off-line minimum problem.

The algorithm takes the sequence of number and generates the corresponding values. The correct values in the extracted array are given in table below:

INDEX	VALUE
1	4
2	3
3	2
4	6
5	8
6	1

The algorithm picks the minimum from the sequence by considering the sequence and then it remove that value then add to the extracted array and the remaining keys are added to the old sequence by using insert algorithm.

(b)

Program Plan Intro

To argue the array extracted returned by OFF-LINE-MINIMUM is correct.

Explanation of Solution

The OFF-LINE-MINIMUM algorithm find the minimum number from the available sequence by using the extract min and then it add the remaining number to the sequence using insert operation.

The algorithm pick the smallest element from the available element then removed it from the sequence then it checks that the extracted value is minimum or not and combine the set of elements that needs to inserted in the sequence that is remaining elements other than min is combined to the original sequence.

Every iteration of the algorithm is extracted the minimum one by one and added to the extracted array until the last is extracted and stored to the array.

Therefore, the output returns from the algorithm is correct and have finite sequence.

(c)

Program Plan Intro

To describe the implementation of OFF-LINE-MINIMUM algorithm for disjoint set data structure and also gives a tight bound of the implementation.

Explanation of Solution

The algorithm pick the smallest element from the available element then removed it from the sequence then it checks that the extracted value is minimum or not and combine the set of elements that needs to inserted in the sequence that is remaining elements other than min is combined to the original sequence.

The implementation of the disjoint set of data structure through OFF-LINE-MINIMUM algorithm is given below:

Step 1: Select the disjoint sets.

Step 2: Check that $l$ is the smallest value greater than $j$ for $Kl$ exists.

Step 3: Then add all the values of $l$ for iterations of for loop into a linked list.

Step 4: Find the appropriate value of $j$ using FIND-SET( i ).

Step 5: For every $l$ there exist $Kl$ so combine all the values of $Kl$ with $Kj$ and remove each $l$ from the linked list whose $Kl$ is already combined.

After removing $l$ from the linked list it maintain the elements in $O(1)$ time. The algorithm consists of for loop that runs n time and each time it takes constant amount of time that is $O(n)$ .

For the every value of $i$ the function finds the $j$ using FIND-SET that takes times of total sequence, suppose the sequence need total $\eta$ time to find the $j$ having size $n$ so it takes $\mu (n)$ time to find $j$ .

Therefore, the total running time of the implementation of algorithm for disjoint set is $O(n\mu (n))$