5. Recall the median-of-medians quickselect algorithm presented in class: algorithm MoMSELECT(k, S, 1, h): if h 25 then use brute force else m← - (h − 1)/5 - for i = 1 to m do M; ← MEDIANOFFIVE(S1+5i-4...1+5i) mom (a) (b) S1 MOMSELECT(m/2, M, 1,m) Smom p← PARTITION(S,1,h) if k = p then return Sk else if k < p then MOMSELECT(k, S, 1, p − 1) else MOMSELECT(k, S, p + 1, h) Refine the lines (a) and (b) of the algorithm so that the array M or medians does not require additional storage space. Explain how your modifications maintain the correctness and running time of the algorithm.
5. Recall the median-of-medians quickselect algorithm presented in class: algorithm MoMSELECT(k, S, 1, h): if h 25 then use brute force else m← - (h − 1)/5 - for i = 1 to m do M; ← MEDIANOFFIVE(S1+5i-4...1+5i) mom (a) (b) S1 MOMSELECT(m/2, M, 1,m) Smom p← PARTITION(S,1,h) if k = p then return Sk else if k < p then MOMSELECT(k, S, 1, p − 1) else MOMSELECT(k, S, p + 1, h) Refine the lines (a) and (b) of the algorithm so that the array M or medians does not require additional storage space. Explain how your modifications maintain the correctness and running time of the algorithm.
Related questions
Question
Question 5
Transcribed Image Text:5. Recall the median-of-medians quickselect algorithm presented in class:
algorithm MoMSELECT(k, S, 1, h):
if h 25 then use brute force
else
m← - (h − 1)/5
-
for i = 1 to m do M; ← MEDIANOFFIVE(S1+5i-4...1+5i)
mom
(a)
(b)
S1
MOMSELECT(m/2, M, 1,m)
Smom
p← PARTITION(S,1,h)
if k = p then return Sk
else if k < p then MOMSELECT(k, S, 1, p − 1)
else MOMSELECT(k, S, p + 1, h)
Refine the lines (a) and (b) of the algorithm so that the array M or medians does not require
additional storage space. Explain how your modifications maintain the correctness and
running time of the algorithm.
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 2 steps
