Jyrki Katajainen: Possible topics for M.Sc. and Ph.D. theses
(September 2001)
If you feel inspired by these lines, do not hesitate to contact me
personally.
Algorithmics
The complexity results derived for an algorithm under the unit-cost
RAM (resp. PRAM) do not necessarily give the right picture about the actual
running times of the corresponding programs when run on contemporary
(resp. parallel) computers. I call these the sequential computation crisis
and the parallel computation crisis, respectively.
Below I list some research directions aiming at resolving the crises:
instruction scheduling model of computation
cache-oblivious data structures
cache efficiency of geometric algorithms
external-memory graph algorithms
applications of parallel algorithms in sequential computing
asyncronous PRAM
algorithmic problems in distributed computing
Software development
The CPH STL
provides an interesting repository of programs; any
tool that could help one to understand this collection better would be
useful.
Below I list some of the needs we have in our library project: