off-line minimum problem

Problems 21-1: Off-line minimum(Page 517 of CLRS)
The off-line minimum problem asks us to maintain a dynamic set $T$ of elements from the domain $\{1,2,\ldots,n\}$ under the operations INSERT and EXTRACT-MIN. We are given a sequence S of n INSERT and m EXTRACT-MIN calls, where each key in $\{1,2,\ldots,n\}$ is inserted exactly once. We wish to determine which key is returned by each EXTRACT-MIN call. Specifically, we wish to fill in an array $extracted[1\ldots\,m]$ , where for $i=1,2,\twodots,m$ $,extracted[i]$ is the key returned by the $i$ th EXTRACT-MIN call. The problem is "off-line" in the sense that we are allowed to process the entire sequence $S$ before determining any of the returned keys.

$\alpha.$ In the following instance of the off-line minimum problem, each INSERT is represented by a number and each EXTRACT-MIN is represented by the letter $E$ :

$4, 8, E, 3, E, 9, 2, 6, E, E, E, 1, 7, E, 5.$

Fill in the correct values in the extracted array.

To develop an algorithm for this problem, we break the sequence $S$ into homogeneous subsequences. That is, we represent $S$ by

$I_{1},E,I_{2},E,I_{3},\ldots,I_{m},E,I_{m+1}$

where each $E$ represents a single EXTRACT-MIN call and each $I_{j}$ represents a (possibly empty) sequence of INSERT calls. For each subsequence $I_{j}$ , we initially place the keys inserted by these operations into a set $K_{j}$ , which is empty if $I_{j}$ is empty. We then do the following.

chap21_1

$b.$ Argue that the array $extracted$ returned by OFF-LINE-MINIMUM is correct.

$c.$ Describe how to implement OFF-LINE-MINIMUM efficiently with a disjoint-set data structure. Give a tight bound on the worst-case running time of your implementation.

Solutions:

a) the $extracted$ array will hold $4, 3, 2, 6, 8, 1$ .

b)We will show that the extracted array is correct by contradiction. Assume that the extracted array is not correct. Let $x$ = $extracted[j]$ be the smallest value for which the extracted array is incorrect. Let the correct solution reside in the array correct. Call $y$ the value of $correct[j]$ . We have two cases, one where $x>y$ and one where $x<y$ We will prove that neither case can occur.

Assume that $x>y$ . Then the element $y$ can’t appear in the extracted array, or it would have been the smallest value for which the extracted array was incorrect.Since we’ve already processed $y$ before processing $x$ , it must have had a set value of $m+1$ . But, if $correct[j]$ was set to $y$ , then $y$ must initially have been in some $K_{i}$ with $i \leq j$ . Since $extracted[j]$ had no value yet when we processed $y$ , then we couldn’t have put $y$ in set $K_{m+1}$ since we only union with the set above us and we haven’t unioned $K_{j}$ yet. Therefore, we can’t have $x>y$ .

Assume that $x<y$ . We argue that the element $x$ must appear in the correct array. Obviously $x$ must appear before the $j$ th extraction in the original sequence since the OFF-LINE-MINIMUM algorithm never moves sets of elements backwards, it only unions with sets later than it. If we hadn’t extracted $x$ by the $j$ th extraction,then the optimal solutions should have chosen $x$ instead of $y$ for the $j$ th extraction since $x$ is smaller. Therefore, the optimal solution must have extracted $x$ for some $i < j$ . But, that means that $extracted[i]$ holds some $z>x$ . By similar reasoning as above, we couldn’t have moved $x$ past set $K_{i}$ since would have been empty at the time $x$ was chosen. So, since we only union with sets above us and $K_{i}$ hasn’t been unioned yet, we can’t put $x$ in $extracted[j]$ before $extracted[i]$ . Therefore, we can’t have $x<y$ .

Since we have shown that we must have $extracted[j]$ = $correct[j]$ for all $j$ , the OFF-LINE-MINIMUM algorithm returns the correct array.

c)We can efficiently implement OFF-LINE-MINIMUM using a disjoint-set forest. We begin by creating $n$ sets, one for each number, using the MAKE-SET operation. Then, we call UNION $n-m$ times to create the $K_{j}$ sets, the sequences of insertions between extractions. For each set $K_{j}$ , we will also maintain 3 additional pieces of information, number, prev, and next in the representative element of the set (actually this information will be at all the elements, but it will only be maintained for the representative). number will correspond to $j$ and can easily be set with the initial creating of the sets. prev will point to the representative element of $K_{j-1}$ and next will point to the representative element of $K_{j+1}$ . We can maintain these three properties through unions as follows: when we union two sets $j$ and $l$ where $l$ is the next set that still exists after $j$ , we set number of the new representative equal to the maximum of the two representative numbers, in this case, $l$ . We set prev of the new set equal to prev of set $j$ and we set next of prev of $j$ equal to the new representative element. Similarly, we set next of the new set equal to next of set $l$ and we set prev of next of $l$ equal to the new representative element.

In the OFF-LINE-MINIMUM algorithm, each iteration of the for loop ( $n$ iterations) will first call FIND-SET on $i$ (line 2). We use the number field of the returned representative as $j$ . Then, in line 5, to determine the smallest $l$ greater than $j$ for which set $K_{l}$ exists, we can simply follow the next pointer from $j$ , which takes constant time. In line 6, we call UNION again, at most $m$ times throughout the $n$ iterations. For each UNION call, we follow the procedure above for updating the number, prev and next, all of which take constant time. Therefore, we have a total of $n$ MAKE-SET operations, $n$ FIND-SET operations, and $n$ UNION operations. Since we have $3n$ total operations and $n$ MAKE-SET operations, we know that the worst-case running time is $O(3n\alpha(n))=O(n\alpha(n))$ .

llhuii's Blog

Happy coding

off-line minimum problem

llhuii

分类

最新评论

最新留言

链接

功能