2807536
| 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. |
Want to create your own Flashcards for free with GoConqr? Learn more.