Suggested Final Project Topics

---

CS166

Handout 10

Spring 2019

April 25, 2019

Suggested Final Project Topics

Here is a list of data structures and families of data structures we think you might find interesting

topics for a final project. You're by no means limited to what's contained here; if you have another

data structure you'd like to explore, feel free to do so!

If You Liked Range Minimum Queries, Check Out…

Range Semigroup Queries

In the range minimum query problem, we wanted to preprocess an array so that we could quickly

find the minimum element in that range. Imagine that instead of computing the minimum of the

value in the range, we instead want to compute A[i] ★ A[i+1] ★ … ★ A[j] for some associative op-

eration ★. If we know nothing about ★ other than the fact that it's associative, how would we go

about solving this problem efficiently? Turns out there are some very clever solutions whose run-

times involve the magical Ackermann inverse function.