off-line minimum problem

llhuii posted @ 2011年12月03日 20:08 in programming with tags CLRS disjoint-set , 18344 阅读

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))$ .

[回复]

Eva Herrod 说:
2019年2月18日 15:41

The chance of the ruling is done for the individuals. The chapter of the satisfaction and https://www.resumesservicesreview.com/resumewritinglab-com-review/ is followed for the prospective challenges. The manner is done for the parents of the field for the children.

[回复]

Gwendolyn Torbett 说:
2023年4月23日 19:43

crediblebh

[回复]

whatsminer 说:
2025年2月03日 18:58

I found you're this post Roof replacement while searching for some related information on blog search...It's a good post..keep posting and update the information.

[回复]

information 说:
2025年2月04日 18:34

Hello! This is my 1st comment here so I just wanted to give a quick shout out and say I genuinely enjoy reading through your posts. Can you suggest any other blogs/websites/forums that deal with the same subjects? Appreciate it!

[回复]

Learn more 说:
2025年2月04日 18:50

I like what you guys are up too. Such clever work and reporting! Carry on the superb works guys I have incorporated you guys to my blogroll. I think it’ll improve the value of my website

[回复]

here 说:
2025年2月04日 18:54

Awesome blog. I enjoyed reading your articles. This is truly a great read for me. I have bookmarked it and I am looking forward to reading new articles. Keep up the good work!

[回复]

here 说:
2025年2月04日 18:55

Your post was so encouraging and insightful! I really appreciate how you combine motivation with actionable advice, making it easy to connect with your message. The way you break things down into simple steps makes everything feel possible. I can already see how I can apply your tips in my own life. Thank you for sharing such valuable content that’s both inspiring and practical. I’m excited to put your advice into action and see where it takes me. Can’t wait to read your next post and see what else you have in store for us!

[回复]

get more info 说:
2025年2月04日 18:55

What an excellent post! You’ve explained everything so clearly and with such engaging detail. The practical tips and examples make it so easy to apply what you’ve shared. I really appreciate content that both educates and inspires, and this post does just that. I’ll definitely refer back to it when needed. Keep up the great work, and thank you for sharing your insights. I look forward to reading more from you!

[回复]

meoghyugo 说:
2025年2月04日 18:56

I really enjoyed this post! The tips are straightforward and practical, which makes them easy to follow. I love how you explain everything so clearly, making it easy for readers to grasp the concepts. I’ll definitely be checking out more of your posts in the future. Thanks for sharing this valuable content, and I’m excited to see what you’ll post next

[回复]

Find out 说:
2025年2月04日 18:56

What an outstanding post! The insights are both unique and stimulating. It’s evident that a lot of effort went into creating such valuable content. I admire how you simplified complex topics for easier understanding. It’s not just informative but also very encouraging. Keep it up! I can’t wait for your next article and to see what you’ll explore next. Thank you for sharing your expertise!

[回复]

good data 说:
2025年2月04日 18:56

Thank you for the sensible critique. Me and my neighbor were just preparing to do some research about this. We got a grab a book from our area library but I think I learned more clear from this post. I’m very glad to see such magnificent info being shared freely out there.

[回复]

토토수비대 说:
2025年2月04日 18:57

Reading your blog post felt like having a meaningful conversation with a friend. Your insights were thoughtful, and the way you presented them was so authentic and relatable. I also loved how you included actionable steps?it’s always great to walk away from a post feeling inspired and equipped to make changes. Fantastic job.

[回复]

here 说:
2025年2月04日 18:57

Thank you so much for giving everyone an exceptionally superb possiblity to read critical reviews from here. It is always so terrific plus stuffed with a great time for me personally and my office friends to search your website at the least 3 times per week to read through the fresh issues you have. And of course, we’re usually satisfied with the outstanding points you give. Selected 4 facts on this page are basically the most impressive we have all had.

[回复]

website 说:
2025年2月04日 19:07

This blog post is excellent! The ideas are easy to understand, and the personal examples make it relatable. Thank you for sharing your knowledge in such a thoughtful way. I can’t wait to see what you write next!

[回复]

마사지매거진 说:
2025年2月04日 19:29

[回复]

토토지식백과 说:
2025年2月04日 19:43

Thank you again for all the knowledge you distribute,Good post. I was very interested in the article, it's quite inspiring I should admit. I like visiting you site since I always come across interesting articles like this one.Great Job, I greatly appreciate that.Do Keep sharing! Regards

[回复]

gendersite 说:
2025年2月04日 20:00

It is a good site post without fail. Not too many people would actually, the way you just did. I am impressed that there is so much information about this subject that has been uncovered and you’ve defeated yourself this time, with so much quality. Good Works!

[回复]

good contents 说:
2025年2月04日 20:21

Great post but I was wondering if you could write a little more on this subject? I’d be very thankful if you could elaborate a little bit further. Thanks in advance

[回复]

llhuii's Blog

Happy coding

off-line minimum problem

llhuii

分类

最新评论

最新留言

链接

功能