Looking for Master Thesis Topic?

Preparing for today lecture on external memory algorithms, I found a beautiful open problem for the shortest paths in implicit graphs problem. The problem is well-suited for a master thesis project or similar. Hence, if you are looking for interesting new algorithmic stuff to work on, come talk to me or drop me an email.

\Philip

External Memory Algorithms on Monday.

Carsten will not be here next monday. Instead Philip will talk about “External Memory Algorithms”. The references are:

• Erik Demaine, “Cache-Oblivious Algorithms and Data Structures”, Lecture Notes from the EEF Summer School on Massive Data Sets.
• Rezaul Alam Chowdhury and Vijaya Ramachandran, “Cache-oblivious dynamic programming“, SODA 2006.

\Philip

Next Lecture

Even though Carsten might not be able to be here next monday (March 22) we still have a lecture as usual. Indeed, the teachers will probably never run out of cool stuff that they want to teach you about.

Mandatory exercise Optional

In the optional part of the mandatory exercise it should be  O(n log n) space. Sorry!

-Inge