Suggested Final Project Topics

Why it’s worth studying: This particular data structure combines together a number of powerful ideas

from Theoryland. It’s partially based on succinct data structures, data structures designed to use close to

the information-theoretic minimum number of bits for solving a problem. It uses several reductions: one

from approximate membership query to exact membership query, and one from storing sets to storing

multisets. And it touches on data structure lower bounds – how do they know they can’t push the space us-

age down further? This would be a great way to explore the theory behind advanced data structures and to

see how all these ideas come together in one place.

---

 19 / 22