Sebastian Bauer's Homepage

Studies

Here you will find some stuff I have done for my computer science studies. Some things were required to be written and other things just for expierence. Note that most of the documents here are currently german only.

Advanced seminar: IP Prefix Lookup

In the following you will find the presentation file of my first so called Hauptseminar. The goal was to introduce datastructures and methods to solve the raw ip prefix problem effeciently. The contents is based upon the script "Algorithmen für Kommunikationsnetze" from Prof. Dr. Thomas Erlebach at the ETH Zürich. Note that the language of this OpenOffice presentation is german only. If time allows I will try to write a complete script in english and maybe further enhance the contents.
Download: ipprefixlookup.sxi (70.0 KB)

Advanced seminar: Shortest Superstrings

This is my work for the second Hauptseminar I attended (german only). It covers the problem of finding a so called shortest superstring of a given set of strings. It includes a NP-complete proof and two approximation algorithms.
Download: superstrings-print.pdf (279.7 KB) superstrings-screen.pdf (321.7 KB)

Student research project: RNA-Sekundärstruktur (RNA secondary structure)

This work describes the prediction of the RNA secondary structure. It first shows the basics of the well known Zucker algorithm which is based on dynamical programming. However, this algorithm cannot predict structures which contains so called pseudoknots. It then introduces the approach by Brinkmeier to generate the secondary structure with help of a graph grammer. This also includes pseudoknots.
The goal of this work was to examine a subset of known pseudoknotted RNA and to find the possible sequence of their generation (including the minimal subset of basic structures which are needed to generate them). For this purpose, a small tool with a core algorithm based on dynamical programming has been developed.
Download: rna-print.pdf (566.2 KB)

Diploma thesis: Sortieren von Zeichenketten (sorting of text strings)

This diploma thesis covers different string sorting algorithms including their analysis. One of them is Burstsort, an algorithm developed by Sinha and Zobel.
It also features the description of ideal cache model introduced by Frigo et al. This model can be used to develop cache friendly algorithms throughout multiple memory layers. Such are known as cache oblivious, as they don't depend on the cache's properties. It is showed, that some problems which are trivial within the RAM model are harder in this model.
Later, the skew algorithm of Kärkkainen and Sanders which sorts all suffixes of text strings is described. It is then showed that this algorithm can be turned into an cache oblivious with optimal cache complexity one assuming a comparison model.
Download: strings-print.pdf (1095.7 KB)

Select in O(n) (worst case)

This the java implementation of a O(n) time bound algorithm which returns the i'th smallest element of a given unordered array. The algorithmn is taken from the book "Introduction to algorithmns".
Download: select.zip (3200 bytes)