One of the tasks for an operating system is the job of scheduling computations to be performed

Question:

One of the tasks for an operating system is the job of scheduling computations to be performed by the processor(s) that are part of that system. A subtask that comes up in some processor scheduling problems is to solve a sequence σ of O(n) priority queue operations, where each operation in σ is either an insert(i) or removeMin(), such that i is a distinct integer in the range from 1 to n. This problem is known as the offline-min problem, since the entire sequence, σ, is given in advance. Interestingly, the offline nature of this problem gives us a faster way of answering the operations in σ than using a heap. Namely, if k is the smallest integer inserted somewhere in σ, then we know the very next removeMin() in σ will return k. Likewise, after we have matched up k and this removeMin(), and deleted both from σ, then we can repeat this argument on the operations that remain. Use this observation to design an algorithm for answering all the operations in σ in O(nα(n)) time, and thereby solve the offlinemin problem.

Fantastic news! We've Found the answer you've been seeking!

Step by Step Answer:

Related Book For  book-img-for-question

Algorithm Design And Applications

ISBN: 9781118335918

1st Edition

Authors: Michael T. Goodrich, Roberto Tamassia

Question Posted: