[Mittagsseminar TI] Fwd: Einladung zur Verteidigung meiner Masterarbeit

[Wolfgang Mulzer <mulzer@inf.fu-berlin.de>]

-------- Forwarded Message --------
Subject: Einladung zur Verteidigung meiner Masterarbeit
Date: Mon, 19 Oct 2015 13:29:29 +0200
From: Marcel Ehrhardt <marehr@zedat.fu-berlin.de>
To: i-studi@inf.fu-berlin.de, i-wimis@inf.fu-berlin.de,
i-profs@inf.fu-berlin.de
CC: renee.zentiks@fu-berlin.de

Sehr geehrte Damen und Herren,

hiermit lade ich Sie herzlich zur Verteidigung meiner Masterarbeit mit
dem Titel „An In-Depth Analysis of Data Structures Derived from
van-Emde-Boas-Trees” ein.

Die Verteidigung findet am Donnerstag, dem 22.10.2015, um 12:00 Uhr in
Raum 055 in der Takustr. 9 statt.

Die Arbeit wurde von Prof. Dr. Wolfgang Mulzer betreut.
Zweitgutachter ist Dr. Klaus Kriegel.

Zusammenfassung:
IP-packet routing is one of the most practical solved problems in
computer science with millions of routed packets per second. The
algorithmic problem behind it is the so-called predecessor problem.
Assuming a universe U, in this problem one can query a set S ⊆ U for the
*predecessor* of an element q within the set S, i.e. max{x ∈ S | x < q}.
If the set S can be manipulated, the problem is called the *dynamic*
predecessor problem, otherwise it is called the *static* predecessor
problem.

I give an overview of several different data structures for the w-bit
word RAM on *bounded integer universes*, i.e. U = {0, ..., 2^w − 1}.
Those data structures are based on the van-Emde-Boas-Tree [BKZ76]. For
each data structure I work out the details of the algorithms by giving
pseudo-code and for some of them I present new techniques, which give an
easier and clearer presentation of the data structure and the
algorithms. Last but not least, I answer an open problem concerning the
space usage stated by Bose et al [Bos+13].

Mit freundlichen Grüßen
Marcel Ehrhardt

-----------------------

[BKZ76]
P. van Emde Boas, R. Kaas, and E. Zijlstra. “Design and implementation
of an efficient priority queue”. In: Mathematical systems theory 10.1
(1976), pp. 99–127. issn: 0025-5661. doi: 10.1007/BF01683268. url:
10.1007/BF01683268.

[Bos+13]
Prosenjit Bose, Karim Douïeb, Vida Dujmović, John Howat, and Pat Morin.
“Fast Local Searches and Updates in Bounded Universes”. In: Comput.
Geom. Theory Appl. 46.2 (Feb. 2013), pp. 181–189. issn: 0925-7721. doi:
10 . 1016 / j . comgeo . 2012.01.002.

Attachment: smime.p7s
Description: S/MIME Cryptographic Signature