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.


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:
  1. instruction scheduling model of computation
  2. cache-oblivious data structures
  3. cache efficiency of geometric algorithms
  4. external-memory graph algorithms
  5. applications of parallel algorithms in sequential computing
  6. asyncronous PRAM
  7. 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:
  1. testing tools
  2. translation of C++ programs into pure C
  3. software development groupware
  4. cross-platform benchmarking
  5. cache profilers

This page was last modified by Jyrki Katajainen on 2017-08-05.