Range Minimum Query

Flashcards by msladey, updated more than 1 year ago
Created by msladey almost 6 years ago


Range Minimum Query

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


Mathematical Preliminaries
Hamming Distance
Suffix Arrays
Suffix Trees
Data Structures & Algorithms
Reuben Caruana
Data Structures & Algorithms
Martyn Haigh
Computer science unit 2
Somto Ibeme
Algorithms ♡
lauren ♥
Computational Thinking ♡
lauren ♥
Searching and Sorting Algorithms
Josh Calvert
Systems Software Revision