Suggested Final Project Topics

Why they’re worth studying: The Fischer-Heun structure for RMQ was motivated by converting a

problem on arrays to a problem on trees and then using the Method of Four Russians on smaller

problem instances to solve the overall problem efficiently. Both the LCA and LAQ problems involve

creative uses of similar techniques, which might be a great way to get a better sense of how these

techniques can be more broadly applied.

---

 2 / 22

Tarjan’s Offline LCA Algorithm

The discovery that LCA can be solved in time ⟨O(n), O(1)⟩ is relatively recent. Prior to its discovery, it

was known that if all of the pairs of nodes to be queried were to be specified in advance, then it was pos-

sible to solve LCA with O(n) preprocessing and O(1) time per query made.

Why it's worth studying: Tarjan's algorithm looks quite different from the ultimate techniques devel-

oped by Fischer and Heun. If you're interested in seeing how different algorithms for the online and off-

line cases can look, check this one out!