The group Theoretical Computer Science (TCS) focuses on the development, analysis and teaching of efficient algorithms and data structures. In the light of the ever-increasing speed of computer processors and size of computer memories, one might be tempted to conclude that the number of CPU cycles and memory words needed for a particular computation would fade into irrelevance, but in fact the opposite turns out to be true. Data gathering is usually easier than data processing, and recent technical advances in computer science and other scientific fields have made it feasible to collect data sets of sizes that were hard to imagine just a few years ago. The data can be, e.g., of a geographical, meteorological or biological nature, deal with internet-related phenomena or result from observations of outer space. The desire to make as much sense as possible of these enormous amounts of information poses daunting challenges and calls for ever more sophisticated algorithmic techniques.
Graph theory furnishes a universal language in which much of the research of the TCS group can be phrased. Real-world objects that are routinely modeled through graphs include electrical circuits, traffic networks and the internet. Recent and ongoing research by the TCS group is concerned with
- the discovery of disjoint paths between specified vertices in a graph,
- the efficient computation of parameters of embeddings of a graph in the plane,
- the labeling of points in a map according to certain rules, e.g., so that labels do not overlap and
- the dynamic maintenance of a list of items so that an initially unknown sequence of accesses to the list items can be processed almost as fast as with full prior knowledge.
In teaching, the TCS group is frequently responsible for the undergraduate courses Informatik III (introduction to algorithms and data structures) and Einführung in die theoretische Informatik (introduction to formal languages). It teaches both theoretical and hands-on graduate courses in areas such as
- graph algorithms
- data structures
- network flow
- approximation algorithms
- complexity theory
- computational geometry
- online algorithms.
The TCS group meets at irregular intervals to discuss technical topics of shared interest. A meeting is usually sparked off by an informal presentation by a member of the TCS group, a student associated with the group or an outside guest and ends with an open brain-storming.