Suggested Final Project Topics

Succinct Range Minimum Queries

A succinct data structure is one that tries to solve a problem in the theoretically minimum amount of

space, where space is measured in bits rather than machine words. The Fischer-Heun data structure from

lecture is a time-optimal data structure for RMQ, but uses a factor of Θ(log n) more bits than necessary

by storing Θ(n) total machine words. By being extremely clever with the preprocessing logic, it’s possible

to shrink the space usage of an RMQ structure down to just about the theoretical minimum.

Why it’s worth studying: Succinct data structures are an exciting area of research and provide an en-

tirely new perspective on what space efficiency means. In studying this data structure, you’ll both see some

new strategies for solving RMQ and get a taste of just how much redundancy can be removed from a data

structure.

---

 3 / 22