FU Logo
  • Startseite
  • Kontakt
  • Impressum
  • Home
  • Listenauswahl
  • Anleitungen

[Mittagsseminar TI] thesis defense

<-- thread -->
<-- date -->
  • From: László Kozma <laszlo.kozma@fu-berlin.de>
  • To: agti-Mittagsseminar@lists.fu-berlin.de
  • Date: Thu, 20 Apr 2023 11:57:21 +0200
  • Subject: [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


<-- thread -->
<-- date -->
  • agti-Mittagsseminar - Second quarter 2023 - Archives indexes sorted by:
    [ thread ] [ subject ] [ author ] [ date ]
  • Complete archive of the agti-Mittagsseminar mailing list
  • More info on this list...

Hilfe

  • FAQ
  • Dienstbeschreibung
  • ZEDAT Beratung
  • postmaster@lists.fu-berlin.de

Service-Navigation

  • Startseite
  • Listenauswahl

Einrichtung Mailingliste

  • ZEDAT-Portal
  • Mailinglisten Portal