Suggested Final Project Topics

Why they're worth studying: If you really enjoyed the RMQ coverage from earlier in the quarter,

this might be a great way to look back at those topics from a different perspective. You'll get a much

more nuanced understanding of why our solutions work so quickly and how to adapt those tech-

niques into novel settings.

Lowest Common Ancestor and Level Ancestor Queries

Range minimum queries can be used to solve the lowest common ancestors problem: given a tree,

preprocess the tree so that queries of the form “what node in the tree is as deep as possible and has

nodes u and v as descendants?” LCA queries have a ton of applications in suffix trees and other al-

gorithmic domains, and there’s a beautiful connection between LCA and RMQ that gave rise to the

first ⟨O(n), O(1)⟩ solution to both LCA and RMQ. The level ancestor query problem asks to prepro-

cess a tree so that queries of the form “which node is k levels above node v in this tree” can be an-

swered as efficiently as possible, and it also, surprisingly, admits a ⟨O(n), O(1)⟩ solution.