{"ad_unit_id":"App_Resource_Sidebar_Upper","resource":{"id":2807536,"author_id":1458821,"title":"Range Minimum Query","created_at":"2015-05-25T16:16:39Z","updated_at":"2016-02-19T08:09:29Z","sample":false,"description":"Range Minimum Query\r\n","alerts_enabled":true,"cached_tag_list":"rmq, algorithms, revision2015","deleted_at":null,"hidden":false,"average_rating":null,"demote":false,"private":false,"copyable":true,"score":16,"artificial_base_score":0,"recalculate_score":true,"profane":false,"hide_summary":false,"tag_list":["rmq","algorithms","revision2015"],"admin_tag_list":[],"study_aid_type":"FlashCardDeck","show_path":"/flash_card_decks/2807536","folder_id":2208432,"public_author":{"id":1458821,"profile":{"name":"msladey","about":null,"avatar_service":"gravatar","locale":"en-GB","google_author_link":null,"user_type_id":null,"escaped_name":"msladey","full_name":"msladey","badge_classes":""}}},"width":300,"height":250,"rtype":"FlashCardDeck","rmode":"canonical","sizes":"[[[0, 0], [[300, 250]]]]","custom":[{"key":"rsubject","value":"Algorithms"},{"key":"rlevel","value":"University"},{"key":"env","value":"production"},{"key":"rtype","value":"FlashCardDeck"},{"key":"rmode","value":"canonical"},{"key":"uauth","value":"f"},{"key":"uadmin","value":"f"},{"key":"ulang","value":"en_us"},{"key":"ucurrency","value":"usd"}]}

{"ad_unit_id":"App_Resource_Sidebar_Lower","resource":{"id":2807536,"author_id":1458821,"title":"Range Minimum Query","created_at":"2015-05-25T16:16:39Z","updated_at":"2016-02-19T08:09:29Z","sample":false,"description":"Range Minimum Query\r\n","alerts_enabled":true,"cached_tag_list":"rmq, algorithms, revision2015","deleted_at":null,"hidden":false,"average_rating":null,"demote":false,"private":false,"copyable":true,"score":16,"artificial_base_score":0,"recalculate_score":true,"profane":false,"hide_summary":false,"tag_list":["rmq","algorithms","revision2015"],"admin_tag_list":[],"study_aid_type":"FlashCardDeck","show_path":"/flash_card_decks/2807536","folder_id":2208432,"public_author":{"id":1458821,"profile":{"name":"msladey","about":null,"avatar_service":"gravatar","locale":"en-GB","google_author_link":null,"user_type_id":null,"escaped_name":"msladey","full_name":"msladey","badge_classes":""}}},"width":300,"height":250,"rtype":"FlashCardDeck","rmode":"canonical","sizes":"[[[0, 0], [[300, 250]]]]","custom":[{"key":"rsubject","value":"Algorithms"},{"key":"rlevel","value":"University"},{"key":"env","value":"production"},{"key":"rtype","value":"FlashCardDeck"},{"key":"rmode","value":"canonical"},{"key":"uauth","value":"f"},{"key":"uadmin","value":"f"},{"key":"ulang","value":"en_us"},{"key":"ucurrency","value":"usd"}]}

2807536

No tags specified

{"ad_unit_id":"App_Resource_Leaderboard","width":728,"height":90,"rtype":"FlashCardDeck","rmode":"canonical","placement":1,"sizes":"[[[1200, 0], [[728, 90]]], [[0, 0], [[468, 60], [234, 60], [336, 280], [300, 250]]]]","custom":[{"key":"env","value":"production"},{"key":"rtype","value":"FlashCardDeck"},{"key":"rmode","value":"canonical"},{"key":"placement","value":1},{"key":"uauth","value":"f"},{"key":"uadmin","value":"f"},{"key":"ulang","value":"en_us"},{"key":"ucurrency","value":"usd"}]}

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. |

{"ad_unit_id":"App_Resource_Leaderboard","width":728,"height":90,"rtype":"FlashCardDeck","rmode":"canonical","placement":2,"sizes":"[[[0, 0], [[970, 250], [970, 90], [728, 90]]]]","custom":[{"key":"env","value":"production"},{"key":"rtype","value":"FlashCardDeck"},{"key":"rmode","value":"canonical"},{"key":"placement","value":2},{"key":"uauth","value":"f"},{"key":"uadmin","value":"f"},{"key":"ulang","value":"en_us"},{"key":"ucurrency","value":"usd"}]}