Suggested Final Project Topics

Why they’re worth studying: Radix heaps are interesting in that it’s possible to start off with a fairly

straightforward set of observations about how Dijkstra’s algorithm operates to get an O(m + nC)-time im-

plementation, and then refine that first to O(m + n log C) and from there to O(m + n (log C)

1/2

) through

more and more creative observations. In that sense, this is a fairly accessible data structure that goes

pretty deep into Dijkstra’s algorithm. Later algorithms and data structures have improved upon the run-

time even further, and this could also be a great launching point for further exploration.

---

 20 / 22