Suggested Final Project Topics

Why they're worth studying: Cache-oblivious data structures are a recent area of research that has gar-

nered some attention as cache effects become more pronounced in larger systems. If you're interested in

seeing a theoretically elegant approach to combatting caches – and if you're interested in testing them to

see how well they work in practice – this would be a great place to start. 

R-Trees

R-trees are a variation on B-trees that store information about rectangles in 2D or 3D space. They're used

extensively in practice in mapping systems, yet are simple enough to understand with a little bit of study.