Unit 9: Range-Minimum Queries

This is an archived version of this module from Spring 2021.
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 “Four-Russian” tables

Material

• slides (preliminary)
• lecture notes
• Video 9-1 (2021-05-04): §9.1 RMQ introduction

• Video 9-2 (2021-05-04): §9.2 LCE using RMQ

• Video 9-3 (2021-05-04): §9.3 Primitive RMQ solutions

• Video 9-4 (2021-05-05): §9.3 Sparse table RMQ

• Video 9-5 (2021-05-05): §9.4 Cartesian trees

• Video 9-6 (2021-05-05): §9.5 Four Russians lookup table

---

Further reading and sources

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

• Bender & Farach-Colton: The Level Ancestor Problem simplified (2004), Theoretical Computer Science, 321(1), 5–12.

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

• Ohlebusch: Bioinformatics algorithms (2013) Oldenbusch Verlag

---

Unit 8  ⋅  Syllabus