Sebastian Wild Algorithms Group · Universität Marburg

main page  —  COMP 526 Efficient Algorithms

Unit 9: Range-Minimum Queries

This is an archived version of this module from Spring 2022.
 Click here for the current iteration.

This unit covers the range-minimum query (RMQ) problem:

  • trivial solutions, sparse table
  • longest common extensions in strings and RMQ
  • linear-time preprocessing via exhaustive tabulation

Learning outcomes

  1. Know the RMQ problem and its connection to longest common extensions in strings.
  2. Know and understand trivial RMQ solutions and sparse tables.
  3. Know and understand the Cartesian trees data structure.
  4. Know and understand the exhaustive-tabulation technique for RMQ with linear-time preprocessing.

Material

  • slides

  • lecture notes

  • Video 9-1 (2022-04-25, 11:50): §9.1 RMQ introduction
    Chapters0:41 Learning Outcomes
    1:49 Range-minimum queries (RMQ)
    3:43 Clicker Question
    5:52 Rules of the Game
  • Video 9-2 (2022-04-25, 12:43): §9.2 LCE using RMQ
  • Video 9-3 (2022-04-25, 16:09): §9.3 Primitive RMQ & Sparse Tables
    Chapters7:26 Improvements
    9:54 Trick
  • Video 9-4 (2022-04-25, 28:24): §9.4 Cartesian trees
    Chapters0:23 RMQ & LCA
    13:50 Cartesian Tree - Larger Example
    15:35 Counting binary trees
    23:23 Clicker Question
  • Video 9-5 (2022-04-28, 21:56): §9.5 Exhaustive tabulation
    Chapters2:00 Exhaustive Tabulation Trick
    3:52 Bootstrapping
    13:48 Exhaustive Tabulation

Further reading and sources

The presentation is based on own work. It takes inspiration from the following paper on the related level-ancestor problem:

A more detailed exposition (with slightly different codes for the lookup table) appears here:

Unit 8  ⋅  Syllabus