[Mittagsseminar TI] thesis defense
today in the noon seminar, talk starting in a few minutes..
-------- Forwarded Message --------
Subject: [i-prof] Invitation to the defense of my Bachelor's thesis
Date: Mon, 17 Apr 2023 18:05:34 +0200
From: Johannes Jakob Voderholzer <voderhoj00@zedat.fu-berlin.de>
To: maria.koekenhoff@fu-berlin.de
Dear all,
I hereby invite you to the defense of my Bachelor's thesis with the title:
"Algorithms for optimal search trees on trees".
The defense will take place on Thursday, 20.04.2023 at 12:00 in room
T9/053(Takustr. 9). The defense presentation will be held in English.
First examiner: Prof. Dr. László Kozma
Second examiner: Prof. Dr. Wolfgang Mulzer
Supervisor: Prof. Dr. László Kozma
Best regards,
Johannes Voderholzer
Abstract:
Finding optimal binary search trees in terms of minimal search cost for a
sequence of key queries is a well studied problem in computer science. An
important theorem over the combinatorial structure of the problem found by
Knuth in 1971 can be used to speed up a dynamic program for the problem to
O(n^2) time, where n is the number of keys. Recently, Berendsohn and Kozma
gave a 2-approximation algorithm for a generalization of optimal binary
search trees to search trees on trees, which runs in O(n^3) time. We show,
that Knuth theorem also holds in this setting and use it to improve the
running time of the algorithm to O(min(D^2*L^2, n^3)), where D denotes
the diameter and L the number of leaves of the search space tree. We give
a full implementation of both algorithms and verify the correctness and
running time on randomly generated trees of different types. Further, we
show that a bound given by Mehlhorn for binary search trees can be
generalized to search trees on trees.
_______________________________________________
Automatischer Mailverteiler an Gruppe 'ml-i-prof-mi'.
Hinweise dazu siehe Hilfeseite:
https://www.mi.fu-berlin.de/w/Tec/AnkuendigungsVerteiler
