Range Minimum Query

Description

Range Minimum Query
msladey
Flashcards by msladey, updated more than 1 year ago
msladey
Created by msladey over 9 years ago
18
0

Resource summary

Question Answer
Define the Range Minimum Query Problem i.e what does an RMQ return? The Range Minimum Query is the location of the smallest element in A[i,j]
Describe the preprocessing for the Block Decomposition Algorithm for RMQs (Solution One) Store Ak (Where Ak is an array of length n/k so that for all i, Ak[i] = (x,v) where v is the minimum in A[ik, (i+1)k] and x is its location in A.) for all k = 1,2,4,8 ... <= n.
Describe how a query is performed for the Block Decomposition Algorithm for RMQs. Find the largest block which is completely contained within the query interval, but doesn't overlap a block you have chosen before. The minimum is the smallest in these blocks.
With the Block Decomposition algorithm, describe why the query time is O(logn) We pick at most 2 blocks of each size. There are O(logn) sizes. Picking the next block takes O(1) time. Therefore, we have O(logn).
What is the time and space complexity for the Block Decomposition algorithm? O(n)
Explain the preprocessing stage of the 'Solution 2' algorithm for RMQs. We build Rk for k = 2,4,8,16... <= n. Rk stores RMQ(i, i + k - 1) for all i. We build R2k from Rk in O(n) time. We build R2 from A in O(n) time. Therefore, preprocessing takes O(nlogn) time (logn R arrays).
How much total space is used by the 'solution two' algorithm for RMQs? O(nlogn)
How do we compute RMQ(i , j) if the interval length l = (j - i + 1) is not a power of two? Find the k such that k <= l <= 2k. Compute the minimum of RMQ(i, i+k-l) and RMQ(j-k+1, j).
Using the 'Low Resolution RMQ' algorithm for RMQs. What time complexities can we expect? O(nloglogn) space and prep. O(1) query.
Show full summary Hide full summary

Similar

Mathematical Preliminaries
msladey
Suffix Arrays
msladey
Hamming Distance
msladey
Suffix Trees
msladey
Data Structures & Algorithms
Reuben Caruana
Computer science unit 2
Somto Ibeme
Algorithms ♡
lauren ♥
Computational Thinking ♡
lauren ♥
Searching and Sorting Algorithms
Josh Calvert
Systems Software Revision
cocacolai
Grafy I.
Michal Roch