The off-line minimum problem maintains a dynamic set T of elements from the domain {1, 2,...,n} under the operations INSERT and EXTRACT-MIN. A sequence S of n INSERT and m EXTRACT- MIN calls are given, where each key in {1, 2,...,n} is inserted exactly once. Let a sequence S be represented by I1 , E, I2, E, ... , E, Im+1 , where each Ij stands for a subsequence (possibly empty) of INSERT and each E stands for a single EXTRACT-MIN. Let Kj be the set of keys initially obtained from insertions in Ij. The algorithm to build an array extracted[1..m], where for i = 1, 2, ..., m, extracted[i] is the key returned by the ith EXTRACT-MIN call is given below: Off-Line-Minimum(m, n) for i = 1 to n determine j such that i ∈ Kj if j ≠ m + 1 extracted[j] = i let L be the smallest value greater than j for which KL exists KL = KL U Kj, destoying Kj return extracted Given the operation sequence 9, 4, E, 6, 2, E, E, 5, 8, E, 1, 7, E, E, 3; where each number stands for its insertion. Draw a table showing the building process of extracted[1..6]. You have to show all Kj from Ij in the table and how they change (e.g. some have more elements due to merge and some disappeared due to merge). Use the attached table for the operation sequence 4, 8, E, 3, E, 9, 2, 6, E, E, E, 1, 7, E, 5 as a guide
The off-line minimum problem maintains a dynamic set T of elements from the domain {1, 2,...,n} under the operations INSERT and EXTRACT-MIN. A sequence S of n INSERT and m EXTRACT- MIN calls are given, where each key in {1, 2,...,n} is inserted exactly once. Let a sequence S be represented by I1 , E, I2, E, ... , E, Im+1 , where each Ij stands for a subsequence (possibly empty) of INSERT and each E stands for a single EXTRACT-MIN. Let Kj be the set of keys initially obtained from insertions in Ij. The algorithm to build an array extracted[1..m], where for i = 1, 2, ..., m, extracted[i] is the key returned by the ith EXTRACT-MIN call is given below: Off-Line-Minimum(m, n) for i = 1 to n determine j such that i ∈ Kj if j ≠ m + 1 extracted[j] = i let L be the smallest value greater than j for which KL exists KL = KL U Kj, destoying Kj return extracted Given the operation sequence 9, 4, E, 6, 2, E, E, 5, 8, E, 1, 7, E, E, 3; where each number stands for its insertion. Draw a table showing the building process of extracted[1..6]. You have to show all Kj from Ij in the table and how they change (e.g. some have more elements due to merge and some disappeared due to merge). Use the attached table for the operation sequence 4, 8, E, 3, E, 9, 2, 6, E, E, E, 1, 7, E, 5 as a guide
Chapter5: Data Storage Technology
Section: Chapter Questions
Problem 14VE
Related questions
Question
The off-line minimum problem maintains a dynamic set T of elements from the domain {1, 2,...,n}
under the operations INSERT and EXTRACT-MIN. A sequence S of n INSERT and m EXTRACT-
MIN calls are given, where each key in {1, 2,...,n} is inserted exactly once. Let a sequence S be
represented by I1 , E, I2, E, ... , E, Im+1 , where each Ij stands for a subsequence (possibly empty) of
INSERT and each E stands for a single EXTRACT-MIN. Let Kj be the set of keys initially obtained
from insertions in Ij. Thealgorithm to build an array extracted[1..m], where for i = 1, 2, ..., m,
extracted[i] is the key returned by the ith EXTRACT-MIN call is given below:
under the operations INSERT and EXTRACT-MIN. A sequence S of n INSERT and m EXTRACT-
MIN calls are given, where each key in {1, 2,...,n} is inserted exactly once. Let a sequence S be
represented by I1 , E, I2, E, ... , E, Im+1 , where each Ij stands for a subsequence (possibly empty) of
INSERT and each E stands for a single EXTRACT-MIN. Let Kj be the set of keys initially obtained
from insertions in Ij. The
extracted[i] is the key returned by the ith EXTRACT-MIN call is given below:
Off-Line-Minimum(m, n)
for i = 1 to n
determine j such that i ∈ Kj
if j ≠ m + 1
extracted[j] = i
let L be the smallest value greater than j for which KL exists
KL = KL U Kj, destoying Kj
return extracted
KL = KL U Kj, destoying Kj
return extracted
Given the operation sequence 9, 4, E, 6, 2, E, E, 5, 8, E, 1, 7, E, E, 3; where each
number stands for its insertion. Draw a table showing the building process of extracted[1..6].
number stands for its insertion. Draw a table showing the building process of extracted[1..6].
You have to show all Kj from Ij in the table and how they change (e.g. some have more elements due to merge
and some disappeared due to merge).
and some disappeared due to merge).
Use the attached table for the operation sequence 4, 8, E, 3, E, 9, 2, 6, E, E, E, 1, 7, E, 5 as a guide
Transcribed Image Text:K₁ K₂ K3
0 (4,8) (3) (9,2, 6)
1 (4,8) (3) (9,2, 6)
2 (4,8) (3)
3
(4,8)
i
K4
0}
0
(9,2,6)
(9,2,6,3)
(9,2, 6, 3, 4, 8)
(9, 2, 6, 3, 4, 8)
Ks
0
0
(9,2, 6, 3, 4, 8)
(9,2, 6, 3, 4, 8)
K6
|{1,7}
K₁
(5)
(5, 1,7)
(5, 1,7)
(5, 1,7)
(5,1,7)
(5,1,7)
(5.1.7)
(5,1,7)
(5, 1, 7, 9, 2, 6, 3, 4, 8)
extracted
1|2|3|4|5|6
32
432
432
4326
4
32 6
43 26 8
TITL
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
Step by step
Solved in 3 steps
Knowledge Booster
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.Recommended textbooks for you
Systems Architecture
Computer Science
ISBN:
9781305080195
Author:
Stephen D. Burd
Publisher:
Cengage Learning
Systems Architecture
Computer Science
ISBN:
9781305080195
Author:
Stephen D. Burd
Publisher:
Cengage Learning