Department of Computer Science

Algorithms and Complexity

Christian Schindelhauer



I have moved to Freiburg: My new homepage For more details and further information (or suggestions for topics) ask me.
Topics for Bachelor Theses

refer to current research. Topics cover the following areas.

  • Computational complexity
  • Distributed algorithms
  • Peer to peer networks
  • Sensor networks
  • Ad-hoc-networks
  • On-line algorithms
Here some examples.
Bachelor thesis: Peer to peer networks Network Coding in random networks
Contact Christian Schindelhauer/Peter Mahlmann

By the use of special encoding techniques (so-called network coding) data can be broadcasted in a very efficient, fast and robust way. This technique is used to distribute large files such as music files, video files, and software packages by peer-to-peer networks.

In this bachelor thesis the student implements a download system which combines a random network with a random linear network coding. This work extends an existing random Java based peer-to-peer-network.

Bachelor thesis: On-line algorithms On-line exploration and on-line Routing: Visualization of JITE (Just in time multiple message on-line routing)
Contact Christian Schindelhauer/Stefan Rührup

We consider the problem of routing a message in a mesh network with faulty nodes. The number and positions of faulty nodes is unknown. It is known that a flooding strategy like expanding ring search can route a message linear in the minimum number of steps h while it causes a traffic (i.e. the totalCompetitive Online Routing number of messages) of O(h2). For optimizing traffic a single-path strategy is optimal producing traffic O(h+p), where p is the number of border nodes neighbored to faulty nodes. The JITE protocol is a deterministic multi-path online routing algorithm that delivers a message within O(h) steps causing traffic O((h+p) log3h).

In this bachelor thesis the student implements a Java applet that presents the JITE-algorithm and other algorithms.
Bachelor Thesis Ad-hoc-networks:
Efficiency and Fairness in the medium access layer (MAC)
Contact: Christian Schindelhauer

Mobile ad-hoc-networks are distributed self-organizing wireless communications networks without central control. The frequency band available for such networks is limited and concurrent systems cannot distinguish other networks from static noise. If network protocols simply ignore this fact and increase signal strength then all eventually no communication is possible. So, it is advisable to back off like the AIMD-strategy within TCP.

In this bachelor thises the student examines distributed probabilistic procedures according to their ability to share the transmission medium.
Using simulation models the student investigates fairness and efficiency, i.e. bandwidth utilization.

Topics for Master Theses

also refer to current research. Topics cover the following areas.

  • Computational complexity
  • Distributed algorithms
  • Peer to peer networks
  • Sensor networks
  • Ad-hoc-networks
  • On-line algorithms
Master Thesis: Distributed Algorithms
Distributed data aggregation in the Push and Pull model
Contact: Christian Schindelhauer/Peter Mahlmann

The following game describes that Random call model. In each round each player selects a random communication partner. If the information is transmitted from the calling to the callee, this transfer is called a "push". If the callee transfers an information to the caller this operaiton is called "pull".

Now each player i has a number xi . If player i and j communicate, then they adapt their values and receive (xi+xj)/2 as new value. In this master thesis the student investigates the question how quickly these variables converge against the average value? Do push and pull behave differently (as being observed in the disrete case)?

Master thesis: Peer to peer networks
The mixing time of coincidental Peer ton Peer networks
Contact: Christian Schindelhauer/Peter Mahlmann

Many networks, like for example Gnutella, have no central structures or hierarchies. Thus they are nearly invulnerable and indestructible. Further improvements are possible if Peers exchange regularly neighbors. A possibility is the Plush operation (see illustration).
One can prove, the Plush (also known as Push&Pull) always produces a uniform random graph. However, the speed of convergence is an open problem.

A goal of this master thesis is to enhance our knowledge on this process. This can be done by empirical experiments of via rigorous analysis of the underlying Markov.
Master thesis: Sensor networks Energy efficient protocols for sensor networks
Contact: Christian Schindelhauer

Wireless sensor networks have become a very important research subject due to their potential of providing diverse services to numerous applications. In Paderborn we have developed a protocol called 1QK, enabling an energy efficient wireless multi-hop sensor network. It collects sensor data from sensor nodes and to send application data to sensor nodes. Due to many restrictions concerning hardware and software, both, the use of energyMica2dot from Crossbow efficient components and the development of new protocols and architectures are necessary to satisfy all conditions. Moreover the cost aspect in our application has to be mentioned as an extra critical point, since the industry plans to produce millions of these sensor nodes.

In its latest version 1QK uses only 128 Bytes RAM (1Q = 1 quarter Kilobyte) and utilizes several channels. This is the result of a preceding master thesis and a bachelor thesi

As the next step this protocol may be improved and experimental studies on an implementation.
Master thesis: Ad hoc networks
Analysis and test of a mobile Ad-hoc-network
Contact: Christian Schindelhauer

Ad-hoc-networks are wireless networks without central control and control. They connect laptop with each other and with the Internet. PAMANET (the Paderborn Mobile Ad hoc NETwork) has been developed in cooperation with the research groups of Franz Rammig and Stefan Böttcher within a students' project group. The main advantage of PAMANET is its scalability, i.e. it canPAMANET connect arbitrarily many network nodes.

A goal of this master thesis is the 
theoretical analysis of PAMANET and/or the execution and evaluation of field tests with a large number network nodes (> 100). This master thesis uses the results of a preceding students' project group and a preceding bachelor thesis.
Master thesis: Computational complexity
Expected hard problems
Contact: Christian Schindelhauer

Leonid Levin introduced the theory of Average-NP-compeletenes.  In a nutshell this theory says, that if an Average-NP-complete problem can be solved in average polynomial time, then all NP problems can be solved in polynomial time. For this he considered problem and probability distribution as so-called distributional problem. Furthermore, he used a weaker notion than the expectation measure, which bounds the expectation of a polynomial root of the running time. The reason is that the expectation measure preserves simulation properties.

The goal of this master thesis is to revisit the reasons to choose this weaker (now called Levin's) measure. Is it possible to define Average-NP-completeness based on the expectation? And if not, why?
Topics for Phd Theses

Please contact me. If there are open positions for Phd students in our research group this information will be stated here.
Current and past students
  • Bachelor students
    • Nicolas Heine (current)
    • Thomas Janson (current)
    • Martin Tofall (2005)
  • Master students
    • Birgitta Weber (1999)
    • Kerstin Voß (2005) - master thesis
    • Markus Scherschanski (2005) - PeerNear-master thesis
    • Inés Bebea (current)
    • Maria Ana Ruiz Cañamero (current)
    • Arne Vater (current)
  • Phd students
    • Klaus Volbert (2005)
    • Stefan Rührup (current)
    • Peter Mahlmann (current)

Created 2005-10-02
Last Change 2006-02-09
Copyright Christian Schindelhauer