Subject: Fwd: [Ml-iwimi-mi] Einladung zur Verteidigung meiner Bachelorarbeit This thesis defense is tomorrow in the noon seminar (the talk will be in German) -------- Weitergeleitete Nachricht -------- Betreff: [Ml-iwimi-mi] Einladung zur Verteidigung meiner Bachelorarbeit Datum: Thu, 14 Dec 2023 16:32:57 +0100 Von: "Yagmur Dönmez" An: i-profs@inf.fu-berlin.de, i-wimis@inf.fu-berlin.de, i-studi@inf.fu-berlin.de, maria.koekenhoff@fu-berlin.de Sehr geehrte Damen und Herren, ich lade Sie hiermit herzlich zu Verteidigung meiner Bachelorarbeit mit dem Titel "Vergleich der Streaming und Online Algorithmen für das Kantenfärbungsproblem" ein. Der Vortrag wird am 21.12.23 um 12:00 Uhr in der Takustraße 9 Raum 051 stattfinden. Erstgutachter: Dr. rer. nat. Katharina Klost Zweitgutachter: Prof. Dr. László Kozma Mit freundlichen Grüßen Yagmur Dönmez Abstract Die Kantenfärbung zählt zu den fundamentalsten Problemen innerhalb der Graphentheorie. Im Streaming Modell werden die Kanten des Eingabegraphen dem Algorithmus einzeln präsentiert. Hierbei ist der zur Verfügung stehende Speicher kleiner als die Größe des Eingabegraphen, weshalb nicht alle Kanten des Graphen gespeichert werden können. Da die Ausgabe genauso groß ist wie die Eingabe selbst, müssen auch die Farben der Kanten als Stream ausgegeben werden, das sogenannte W-Streaming. In der Vergangenheit wurden schon einige Lösungen für dieses Problem in verschiedensten Modellen vorgestellt. In dieser Arbeit werden wir uns die Entwicklung und Fortschritte dieser genauer anschau- en. Zuletzt lieferten zwei randomisierte Algorithmen im gegnerischen Kantenan- kunftsmodell, aus ESA 2019, SOSA 2021 und ESA 2022, die besten Ergebnisse. Hierbei färbt der neueste jeden Graphen mit 2∆t Farben in O(n∆/t) Platz für jedes n ≤ ∆, wobei ∆ der maximale Grad des Graphen ist. Diese Lösung bietet den einzigen bekannten Online-Kantenfärbungsalgorithmus mit sublinearem Platzbedarf. Unser Ziel ist es die verschiedenen Ergebnisse mit einander zu vergleichen, um potenzielle Verbesserungen zu identifizieren. ================================================================== Subject: Mittagsseminar am Dienstag, 19.12.2023 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 19.12.2023, 12:00 Uhr, SR 051, Takustra=C3=9Fe 9 Benjamin Berendsohn zum Thema: Fast and simple unrooted dynamic forests. ================================================================== Subject: Mittagsseminar am Dienstag, 12.12.2023 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am     Dienstag, 05.12.2023, 12:00 Uhr, SR 051, Takustraße 9     Günter Rote     zum Thema: Counting polyominoes up to 70 cells. ================================================================== Subject: Mittagsseminar Donnerstag 07.12.2023 Das Mittagsseminar wird heute bestreikt. ================================================================== Subject: Mittagsseminar am Dienstag, 05.12.2023 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am     Dienstag, 05.12.2023, 12:00 Uhr, SR 051, Takustraße 9     Aruni Choudhary     zum Thema: About Funk and Hilbert geometry. ================================================================== Subject: Mittagsseminar am Donnerstag, 30.11 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am     Donnerstag, 30.11.2023, 12:00 Uhr, SR 051, Takustraße 9     Helena Bergold     zum Thema: Rafla's conjecture for convex drawings ================================================================== Subject: Mittagsseminar am Dienstag, 28.11.2023 Das Mittagsseminar wird heute bestreikt. ================================================================== Subject: Mittagsseminar am Donnerstag, 23.11 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Donnerstag, 23.11.2023, 12:00 Uhr, SR 051, Takustraße 9 Michaela Krüger zum Thema: About Feedback ================================================================== Subject: Mittagsseminar am Dienstag, 21.11. Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 21.11.2023, 12:00 Uhr s.t., SR 051, Takustraße 9 Franz J. Brandenburg (Passau) zum Thema: Defining graphs by geometric objects Zusammenfassung: We consider graphs whose vertices are geometric objects in the plane, such that there is an edge if and only if the objects intersect, touch, are close, or are visible and see one another. We emphasize fundamental results for the respective classes of graphs, e.g., the complexity of the recognition problem, and state open problems, in particular, for object visibility graphs. ================================================================== Subject: Mittagsseminar 16.11.2023 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Donnerstag, 16.11.2023, 12:00 Uhr, SR 051, Takustraße 9 László Kozma zum Thema: Verification through randomness. ================================================================== Subject: Fwd: [i-prof] [i-studi] Invitation Master's thesis defense Reminder: this thesis defense is in today's noon seminar. -------- Forwarded Message -------- Subject: [i-prof] [i-studi] Invitation Master's thesis defense Date: Thu, 9 Nov 2023 12:09:54 +0100 Dear all, I hereby invite you to the upcoming defense of my master's thesis, titled "On Erdős-Szekeres Problem". The defense will be held in room SR051 (Takustraße 9) on Tuesday, November 14th, 2023 at 12:00, and will be held in English. Advisor and first reviewer: Prof. Dr. László Kozma Second reviewer: Dr. rer. nat. Katharina Klost Best regards， Fang Lin Abstract: The Erdős-Szekeres theorem, established in the 1930s, posits that for a sufficiently large set of points in the plane in general position, it is guaranteed to contain n points forming a convex polygon. In other words, there exists a quantity denoted as N(n) such that any set of N(n) points contains a convex n-gon. This problem is colloquially referred to as the "happy ending problem." The exact value of N(n) remains elusive, motivating efforts to establish both lower and upper bounds as accurately as possible. Over the course of more than 90 years, extensive research has been dedicated to refining the bounds. For general n, Erdős and Szekeres demonstrated in 1935that N(n) <= \binom{2n-4}{n-2}+1 = 4^{n-o(n)}, while in 1961, they confirmed that N(n)>= 2^{n-1}+1. Over the course of these 90 years, there have been eight improvements to the original upper bound, albeit the majority of these remain within the limit of 4^{n-o(n)}. A noteworthy development occurred in 2016 when Andrew Suk improved the upper bound to 2^{n +o(n)}. The best upper bound till today is 2^{n +O(\sqrt{nlogn)}}. Recently, a pertinent question has arisen in an article by G.Damasdi et al. concerning the Erdős-Szekeres problem. The question is to determine the smallest value, denoted as S(n), for which a set of S(n) points in general position in the plane does not form a convex n-gon initially, but the addition of any arbitrary point results in the formation of a convex n-gon. This question is of recent origin, with an unestablished upper bound, and it remains unresolved, even in relatively simple cases. This thesis will commence with an introduction to foundational concepts and provide a historical perspective on the problem's evolution. Subsequently, it will survey the existing upper and lower bounds from the literature concerning the core Erdős-Szekeres problem, along with simpler instances. Following this, the thesis will shift its focus to an investigation of the open question, offering explanations for simple cases and formulating a conjecture regarding its bounds. Finally, it will introduce two interactive tools, namely, the saturation game and the extremal game, both rooted in the Erdős-Szekeres theorem and the open question. ================================================================== Subject: Mittagsseminar am Dienstag, 09.11.2023 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am     Donnerstag, 09.11.2023, 12:00 Uhr, SR 051, Takustraße 9     Katharina Klost     zum Thema: Dynamic compressed quadtrees ================================================================== Subject: Mittagsseminar am Dienstag, 07.11.2023 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin sp= richt am Donnerstag, 07.11.2023, 12:00 Uhr, SR 051, Takustra=DFe 9 Mahmoud Elashmawi zum Thema: Translational Packing of Convex Polygons ================================================================== Subject: Mittagsseminar am Donnerstag, 2.11. Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Donnerstag, 2.11.2023, 12:00 Uhr, SR 051, Takustraße 9 Helmut Alt zum Thema: About Space ================================================================== Subject: Fwd: [i-prof] Invitation to my bachelor thesis defence Tomorrow's Mittagsseminar. Please note the unusual time and location. Cheers Wolfgang -------- Forwarded Message -------- Subject: [i-prof] Invitation to my bachelor thesis defence Date: Tue, 24 Oct 2023 20:26:18 +0200 Dear all, I would like to invite you to my bachelor thesis defence, titled "Persistent Binary Search Trees and Their Practical Applications." The defence will be held in room SR053 (Takustraße 9) on Tuesday, October 31st, 2023 at 14:30. English will be the language of the defence. Advisor and first reviewer: Prof. Dr. Wolfgang Mulzer Second reviewer:Prof. Dr. László Kozma Best regards, Chao Zhan Abstract: Ephemeral data structures retain only the most recent version of the data structures, while persistent data structures maintain a full history of the data structures. Fortunately, several methods can be employed to make any pointer-based ephemeral data structure persistent. This thesis aims to clarify and analyse classical approaches and apply them to the implementation of persistent binary search trees. Subsequently, we evaluate the efficiency of these approaches by conducting several benchmark tests. Furthermore, a partially persistent binary search tree is employed to address the traditional planar point location problem. This approach offers a solution with O(n) space cost, O(logn) query time, and O(nlogn) preprocessing time. ================================================================== Subject: Mittagsseminar - 26.10.2023 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Donnerstag, 26.10.2023, 12:00 Uhr, SR 051, Takustraße 9 Max Willert zum Thema: Orthogonal guarding a 1.5d terrain ================================================================== Subject: Mittagsseminar am Dienstag, 24.10.2023 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 24.10.2023, 12:00 Uhr, SR 051, Takustraße 9 Oskar Besler zum Thema: Vergleich von kernbasierten Routing-Algorithmen in Straßennetzwerken (B.Sc.-Verteidigung, auf Deutsch/in German) Hintergrund: Das effiziente Finden eines kürzesten Pfades in einem Straßennetzwerk zwischen zwei Positionen ist eine wichtige Aufgabe für Echtzeitanwendungen wie Navigationssysteme, um flexibel auf dynamische Veränderungen im Straßennetzwerk, wie Änderungen von Start- und Endpositionen, reagieren zu können. In der Literatur gilt der Highway-Hierarchies-Star-Algorithmus als einer der effizientesten Algorithmen zur Ermittlung des kürzesten Pfades zwischen zwei Knoten in einem Straßennetzwerk. Ziele: In dieser Arbeit soll überprüft werden, ob der Highway-Hierarchies-Star-Algorithmus tatsächlich effizienter ist als verschiedene etablierte Algorithmen zum Finden des kürzesten Pfades, wie in der Literatur beschrieben. Methoden: Dafür werden verschiedene Algorithmen zur Berechnung des kürzesten Pfades implementiert und anhand unterschiedlicher Suchanfragen in deutschen Straßennetzwerken bewertet. Ergebnisse: Die Experimente zeigen, dass der Highway-Hierarchies-Star-Algorithmus die besten Ergebnisse bei den Suchanfragen erzielt und dabei auch eine annehmbare Vorverarbeitungszeit aufweist. Schlussfolgerungen: Der Highway-Hierarchies-Star-Algorithmus bietet schnelle Anfragezeiten in statischen Graphen, sodass verschiedene Anfragen mit unterschiedlichen Start- und Endpositionen in Millisekunden berechnet werden können. Dies bestätigt weitgehend die Bewertung in der Literatur. Dennoch sind weitere Tests auf dynamischen Graphen erforderlich, um eine komplette Beurteilung vornehmen zu können. ================================================================== Subject: Re: [Mittagsseminar TI] [ti] Mittagsseminar 19.10.2023 Muss krankheitsbedingt leider ausfallen... > Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin > spricht am > > Donnerstag, 19.10.2023, 12:00 Uhr, SR 055, Takustraße 9 > Max Willert > zum Thema: Orthogonal guarding a 1.5d terrain > > _______________________________________________ > agti-Mittagsseminar mailing list > agti-Mittagsseminar@lists.fu-berlin.de > https://lists.fu-berlin.de/listinfo/agti-mittagsseminar > _______________________________________________ > Automatischer Mailverteiler an Gruppe 'ml-ti-mi'. > Hinweise dazu siehe Hilfeseite: > https://www.mi.fu-berlin.de/w/Tec/AnkuendigungsVerteiler > ================================================================== Subject: Mittagsseminar 19.10.2023 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Donnerstag, 19.10.2023, 12:00 Uhr, SR 055, Takustraße 9 Max Willert zum Thema: Orthogonal guarding a 1.5d terrain ================================================================== Subject: Mittagsseminar am 21.09.2023 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am            Dienstag, 26.09.2023, 12:00 Uhr, SR 055, Takustraße 9            Kristin Knorr            zum Thema: Cops and robbers on 1-planar graphs ================================================================== Subject: Mittagsseminar am 21.09.2023 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am            Donnerstag, 21.09.2023, 12:00 Uhr, SR 055, Takustraße 9            Helena Bergold            zum Thema: Fliples in Signotopes ================================================================== Subject: Mittagsseminar am 19.09.2023 Attention: Note the changed room SR 051 (instead of the usual SR 055)! Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 19.09.2023, 12:00 Uhr, SR 051 (!), Takustraße 9 Jonas Cleve zum Thema: Patrolling Grids With a Bit of Memory ================================================================== Subject: Mittagsseminar am 14.09.2023 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am            Donnerstag, 14.09.2023, 12:00 Uhr, SR 055, Takustraße 9            Michaela Krüger            zum Thema: Grid USO to Cube USO - Part 1 ================================================================== Subject: Noon Seminar 12.9.2023 In the Noon Seminar on Tuesday 12th Sept, Location: SR 55 (or 53), Takustraße 9, László Kozma will talk about: Finding saddle-points faster than sorting. ================================================================== Subject: Mittagsseminar am 07.09.2023 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am            Donnerstag, 07.09.2023, 12:00 Uhr, SR 055, Takustraße 9            Katharina Klost            zum Thema: Balanced Separators in Polygonal Domains ================================================================== Subject: Mittagsseminar Dienstag, 05.09.2023 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin sp= richt am Dienstag, 05.09.2023, 12:00 Uhr, SR 053, Takustra=DFe 9 Mahmoud Elashmawi zum Thema: Complete Colorings of Planar Graphs ================================================================== Subject: Mittagsseminar am Donnerstag, 31.08. Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Donnerstag, 31. August 2023, 12:00 Uhr, SR 055, Takustraße 9 Wolfgang Mulzer zum Thema: Card-based cryptography ================================================================== Subject: Mittagsseminar Dienstag, 29.8.2023 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am      Dienstag, 29. August 2023, 12:00 Uhr, Seminarraum 055      Helmut Alt      zum Thema: Restricted Knapsack ================================================================== Subject: Mittagsseminar 24.8.2023 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Donnerstag, 24.08.2023, 12:00 Uhr, SR 055, Takustraße 9 Max Willert zum Thema: Approximating the burning number ================================================================== Subject: Mittagsseminar Dienstag, 22.8.2023 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 22. August 2023, 12:00 Uhr, Seminarraum 053 Benjamin Berendsohn zum Thema: Twin-width of binary structures ================================================================== Subject: Mittagsseminar Dienstag, 15.8.2023 und Donnerstag, 17.8.2023 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am      Dienstag, 15. August 2023, 12:00 Uhr, Seminarraum 053      Helena Bergold      zum Thema: k-intersecing pseudoconfiguration of points und am      Donnerstag, 17. August 2023, 12:00 Uhr, Seminarraum 053      Günter Rote      zum Thema: Packing and tiling a Square with squares and with rectangles ================================================================== Subject: Mittagsseminar Dienstag, 08.08.2023 und Donnerstag, 10.08.2023 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am     Dienstag, 8. August 2023, 12:00 Uhr, Seminarraum 053(?)     Helena Bergold     zum Thema: k-intersecing pseudoconfiguration of points und am     Donnerstag, 10. August 2023, 12:00 Uhr, Seminarraum 053     Günter Rote     zum Thema: Packing and tiling a Square with squares and with rectangles ================================================================== Subject: Fwd: [Ml-iwimi-mi] Einladung zur Verteidigung meiner Bachelorarbeit Tommorow in the noon seminar, potentionally in German. -------- Weitergeleitete Nachricht -------- Betreff: [Ml-iwimi-mi] Einladung zur Verteidigung meiner Bachelorarbeit Datum: Sun, 16 Jul 2023 22:15:16 +0200 Von: Philipp Walter An: i-studi@inf.fu-berlin.de Kopie (CC): i-profs@inf.fu-berlin.de, i-wimis@inf.fu-berlin.de, maria.koekenhoff@fu-berlin.de Sehr geehrte Damen und Herren, hiermit lade ich Sie zu der Verteidigung meiner Bachelorarbeit mit dem Titel "Experimental Evaluation of Algorithms for Long Plane Trees" ein. Die Verteidigung findet am Donnerstag, den 20.07.2023, um 12:00 Uhr im Seminarraum 055, Takustr. 9 statt. Erstgutachterin: Dr. Katharina Klost Zweitgutachter: Prof. Dr. Wolfgang Mulzer Mit freundlichen Grüßen Philipp Walter Abstract: Longest planar spanning trees are thought to be an NP-hard task. One approach to such problems is to relax the solution’s criteria. This can be achieved by identifying solutions that are not necessarily the longest spanning tree but are planar. This paper investigates the lower bound of the approximation factor of algorithms producing planar spanning trees. We analyze the algorithm proposed in Cabello et al. (2021). The algorithm finds AB trees that improve star graphs. The star is a simple graph proposed by Alon et al. (1993), where one point is connected to every other point. The AB tree algorithm attempts to improve the star by adding zig-zag edges, which increases the total length. To analyze the approximation factors, we implement four algorithms: the aforementioned AB tree algorithm, a brute force algorithm for the longest planar spanning tree, a longest spanning tree algorithm, and a specialized algorithm for convex point sets. A genetic algorithm was used to find point sets with low approximation factors programmatically. The brute force algorithm implementation performed poorly and was only utilized for point sets of no more than 10 points. We analyzed point sets with approximation factors of less than 0.9. The genetic algorithm’s output has an approximation factor of 0.9 as well. The sets with low approximation factors are very elongated point sets, particularly ellipsoid forms. In this work, the lowest approximation factor determined is 0.877. Our analysis finds a more overly stretched graph results in an even lower approximation factor. ================================================================== Subject: Mittagsseminar Donnerstag, 06.07.2023 und Dienstag, 11.07.2023 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 18. Juli 2023, 12:00 Uhr, SR 053, Takustraße 9 Felix Schröder (TU Berlin) zum Thema: Linear Size Universal Point Sets for Classes of Planar Graphs ================================================================== Subject: Mittagsseminar Donnerstag, 13.07.2023 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Donnerstag, 13. Juli 2023, 12:00 Uhr, SR 055, Takustraße 9 Kristin Knorr zum Thema: Short flip sequences to untangle segments in the plane ================================================================== Subject: Mittagsseminar Donnerstag, 06.07.2023 und Dienstag, 11.07.2023 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Donnerstag, 6. Juli 2023, 12:00 Uhr, SR 055, Takustraße 9 Jonas Cleve zum Thema: Pattern Formation with Fat Robots und am Dienstag, 11. Juli 2023, 12:00 Uhr, SR 053, Takustraße 9 Anand Srivastav (Universität Kiel) zum Thema: The Chromatic Number of Randomly Augmented Graphs ================================================================== Subject: noon seminar 4th July Dear all, in the noon seminar on Tuesday, 4th July, I will talk about saddle points. Best regards, Laszlo ================================================================== Subject: Noon Seminar today Dear all, today in the noon seminar a thesis defense (MSc): Claas Frederic Fandré "Bounds on the mixing time of Catalan structures" Best regards, Laszlo ================================================================== Subject: Mittagsseminar Dienstag, 27.06.2023 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am     Dienstag, 27.06.2023, 12:00 Uhr, SR 053, Takustraße 9     Katharina Klost     zum Thema: Planar Obstacle Number ================================================================== Subject: Fwd: [i-prof] Einladung zur Verteidigung meiner Masterarbeit Tomorrow's noon seminar will be a Master defense, see below. Cheers Wolfgang -------- Forwarded Message -------- Subject: [i-prof] Einladung zur Verteidigung meiner Masterarbeit Date: Fri, 16 Jun 2023 12:23:43 +0200 Sehr geehrte Damen und Herren, hiermit lade ich Sie herzlich zur Verteidigung meiner Masterarbeit mit dem Titel „Optimierung des Konfigurationsprozesses von Retail-Geräten durch Entwicklung einer domänenspezifischen Sprache” ein. Die Verteidigung findet am 22.06.23 um 12 Uhr im Rahmen des Mittagsseminars der AG Theoretische Informatik im Raum SR 055 statt. Erstgutachter und Betreuer der Arbeit ist Prof. Dr. Wolfgang Mulzer, Zweitgutachter ist Dr. Sönke Kannapinn. Die Arbeit wurde ebenfalls von Denis Kuniß von der Diebold Nixdorf Systems GmbH betreut. Mit freundlichen Grüßen Sebastian Kuzniarz Zusammenfassung: Die vielschichtige Komplexität in der Entwicklung, Pflege und Konfiguration von Software verlangt eine kontinuierliche Prozessoptimierung zur Effizienzsteigerung und Fehlerminimierung. Aus diesem Grund wird innerhalb dieser Arbeit eine domänenspezifische Konfigurationssprache für die Bibliothekssoftware ProBase Store des Unternehmens Diebold Nixdorf entwickelt, um den aktuellen Konfigurationsprozess von Retail-Geräten zu optimieren. Im theoretischen Teil dieser Arbeit wird ein fundiertes Verständnis für formale Sprachen, Grammatiken und Compilerbau geschaffen, welches als Basis für die Entwicklung einer domänenspezifischen Sprache dient. Anschließend werden domänenspezifische Sprachen (DSLs) als Schnittstellen zwischen Mensch und Maschine definiert, was eine Bewertung hinsichtlich Usability ermöglicht. Diese Definition dient der Entwicklung einer dem Entwicklungsprozess folgenden Nutzerstudie zur Evaluation der Konfigurations-DSL hinsichtlich Effektivität, Effizienz sowie Benutzerzufriedenheit. Auf Basis der theoretischen Grundlagen wird eine DSL unter Verwendung des Xtext-Frameworks entwickelt. Die Entwicklung beruht auf einer umfassenden Analyse der Konfigurationsdomäne und der dem vorherigen Konfigurationsprozess zugrundeliegenden Sprache, welche es ermöglicht, eine die DSL beschreibende kontextfreie Grammatik zu definieren. Darauf aufbauend werden sämtliche Bestandteile der DSL, einschließlich Validierungs- und Scoping-Mechanismen sowie die Abbildung auf die ursprüngliche Sprache, implementiert und in einen für den Konfigurationsprozess optimierte Web-basierten Editor integriert. In einer Nutzerstudie mit 12 Teilnehmer:innen wird die entwickelte domänenspezifische Sprache (DSL) mit dem bisherigen Prozess verglichen. Die Ergebnisse der Studie zeigen, dass Teilnehmer:innen im Vergleich zum alten Prozess bei der Bearbeitung von Testaufgaben durchschnittlich 46,88 % weniger Zeit benötigen sowie 16,66 % weniger Fehler mit der DSL-basierten Lösung machen. Dies sorgt für eine signifikante Verbesserung in Bezug auf Effektivität (von 80,13 % auf 96,79 %) und Effizienz (von 76,91 % auf 93,59 %). Hinsichtlich Usability wird mit Hilfe der System-Usability-Scale (SUS) für den DSL-basierten Prozess ein durchschnittlicher Score von 87,71 ermittelt, was eine deutliche Steigerung im Vergleich zum alten Prozess (SUS-Score: 30,21) darstellt. Im Allgemeinen gelten Systeme mit einem SUS-Score von über 68 als überdurchschnittlich gut. Die Ergebnisse verdeutlichen das Potenzial von DSLs, um Entwicklungs- und Konfigurationsprozesse in Softwareprojekten zu optimieren, insbesondere wenn diese mit Toolunterstützung für Nutzer:innen zur Verfügung stehen. ================================================================== Subject: Mittagsseminar Dienstag 20.06.2023 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 20.06.2023, 12:00 Uhr, SR 053, Takustraße 9 Michaela Borzechowski zum Thema: Necklace Splitting with Unique Solutions ================================================================== Subject: Mittagsseminar 15.06.2023 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Donnerstag, 15.06.2023, 12:00 Uhr, SR 053, Takustraße 9 Benjamin Berendsohn zum Thema: Twin-width and Arborially Satisfied Supersets ================================================================== Subject: Mittagsseminar 13.06.2023 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 13.06.2023, 12:00 Uhr, SR 053, Takustra=DFe 9 Mahmoud Elashmawi zum Thema: Lower Bounds of Longest Monotone Paths in Line Arrangements ================================================================== Subject: Mittagsseminar am Donnerstag, 08.06 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Donnerstag, 07. Jui 2023, 12:00 Uhr, SR 055, Takustraße 9 Wolfgang Mulzer zum Thema: Follow the leader ================================================================== Subject: Mittagsseminar 6.62023 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 06.06.2023, 12:00 Uhr, SR 053, Takustraße 9 Max Willert zum Thema: Moores Bound ================================================================== Subject: noon seminar Thursday, 1st June Dear all, tomorrow in the noon seminar a talk by Arash Pourdamghani (TU Berlin) with details below. (afterwards some spicy candy I brought from Finland ;) Best, Laszlo *Title:* SeedTree: A Dynamically Optimal and Local Self-Adjusting Tree (Paper ) *Abstract:* The vision of developing self-adjusting networks is now a reality. For example, programmable optical networking switches are already being used in big tech companies such as Googleand Microsoft. However, theoretical foundations are lagging behind in this area: previous methods have been designed by having fixed and limited networking resources in mind. In this talk, I detail the background and explain a novel model of the problem inspired by data center networking needs. I will show how online and randomized algorithms are being used to develop a more efficient technique that is optimized toward and match the traffic workload they serve, proving the dynamic optimality of the algorithm. *About:* Arash Pourdamghani is a direct Ph.D. student at the INET  group at the Technical University of Berlin, Germany, and also an associated researcher at the Weizenbaum Institute . Previously he was a researcher at the University of Vienna and completed research internships at IST Austria and CUHK. He got his B.Sc. from the Sharif University of Technology. He is interested in algorithm design and analysis with applications in networks, distributed systems, and blockchains. His particular focus is on self-adjusting networks . ================================================================== Subject: Mittagsseminar am 30.5.2023 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am      Dienstag, 30.5.2023, 12:00 Uhr, SR 053, Takustraße 9      Helena Bergold      zum Thema: 41 NP-hard sign mappings ================================================================== Subject: Mittagsseminar am 23.05.2023 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 23.05.2023, 12:00 Uhr, SR 053, Takustraße 9 Kristin Knorr zum Thema: Obstacle Numbers of Graphs ================================================================== Subject: Mittagsseminar am 16.5.2023 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 16.5.2023, 12:00 Uhr, SR 053, Takustraße 9 Günter Rote zum Thema: The length of the grid parabola, and how the zeta function comes about ================================================================== Subject: Mittagsseminar am 09.05.2023 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 09.05.2023, 12:00 Uhr, SR 053, Takustraße 9 Jonas Cleve zum Thema: Voronoi Diagrams of Rotating Rays ================================================================== Subject: NO Mittagsseminar today Dear TIs, I apologize for the short notice, but I will not be able to give the Mittagsseminar today. Jonas ================================================================== Subject: Fwd: [all] Einladung zur Verteidigung meiner Bachelorarbeit Noon Seminar today, note that the room is 055 (normal noon seminar room) -------- Weitergeleitete Nachricht -------- Betreff: [all] Einladung zur Verteidigung meiner Bachelorarbeit Datum: Thu, 27 Apr 2023 00:04:58 +0200 Von: Konstantin Jaehne An: all@mi.fu-berlin.de, maria.koekenhoff@fu-berlin.de Sehr geehrte Angehörige des Informatik-Instituts, hiermit lade ich zur Verteidigung meiner Bachelorarbeit mit dem Titel "Analyse und experimenteller Vergleich von Suchalgorithmen für sortierte Matrizen" am 27.04. um 12:00 ein (T9 SR055). Betreuerin: Dr. Katharina Klost Zweitkorrektor: Prof. Dr. Wolfgang Mulzer Mit freundlichen Grüßen Konstantin Jaehne ----------------------- Zusammenfassung: In dieser Arbeit geht es um Suchalgorithmen in spalten- und zeilenweisen sortierten Matrizen. Neben der herkömmlichen Zeitkomplexität soll ein besonderes Augenmerk auf dem asymptotischen Verhalten der Anzahl der Vergleiche eines Elements (der Matrix) mit dem gesuchten Objekt liegen. Es wird ein Suchalgorithmus für endliche n×m-Matrizen vorgestellt und eine detaillierte Komplexitätsanalyse vorgenommen. Zudem werden alternative Algorithmen präsentiert und miteinander verglichen. ================================================================== Subject: 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 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. ================================================================== Subject: Mittagsseminar am 18.04.2023 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 18.04.2023, 12:00 Uhr, SR 055, Takustra=C3=9Fe 9 Alexander Kauer zum Thema: Quadforests on the real RAM in our dynamic disk = connectivity data structure=20= ================================================================== Subject: NO Mittagsseminar am 13.04.2023 Hello everybody, Unfortunately, it seems that I caught a cold over easter=E2=80=94there = will be no noon seminar today. Have a nice day, Alexander= ================================================================== Subject: Mittagsseminar am 10.04.2023 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 11.04.2023, 12:00 Uhr, SR 055, Takustraße 9 Katharina Klost zum Thema: Classification of bichromatic points with outliers ================================================================== Subject: Mittagsseminar 6.4.2023 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Donnerstag, 06.04.2023, 12:00 Uhr, SR 055, Takustraße 9 Benjamin Berendsohn zum Thema: k-server with pattern-avoiding input ================================================================== Subject: Mittagsseminar 4.4.2023 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 04.04.2023, 12:00 Uhr, SR 055, Takustraße 9 Johannes Obenaus zum Thema: Induced Paths ================================================================== Subject: Mittagsseminar 16.3.2023 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 16.03.2023, 12:00 Uhr, SR 055, Takustra=DFe 9 Mahmoud Elashmawi zum Thema: Upper bounds for Deterministic online b-matching on (k,d)-gr= aphs ================================================================== Subject: Noon Seminar Tuesday 14.3.2023 Dear all, today in the noon seminar an online talk (via Webex). Tan Junqi, a master student at Harbin Institute of Technology (China) will give the talk: "The Shapley Value of Maximum Independent Set in perfect graphs" Webex Link: https://fu-berlin.webex.com/fu-berlin-en/j.php?MTID=m54d9759049fd72e8ba8c6a4189884582 Best regards, Laszlo ================================================================== Subject: Re: [Mittagsseminar TI] [ti] Mittagsseminar am Donnerstag 09.02. und Dienstag 14.02. Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am         Donnerstag, 09. März 2023, 12:00 Uhr, SR 055, Takustraße 9         Helmut Alt         zum Thema: On online packing ================================================================== Subject: Mittagsseminar 7.3.2023 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 07.03.2023, 12:00 Uhr, SR 055, Takustraße 9 Max Willert zum Thema: TSP (... not what you think :-D) ================================================================== Subject: Fwd: Einladung Verteidigung Bachelorarbeit Today in the noon seminar. Best, Laszlo -------- Forwarded Message -------- Subject: [i-prof] Einladung Verteidigung Bachelorarbeit Date: Wed, 1 Mar 2023 13:32:45 +0100 Sehr geehrte Damen und Herren, ich lade Sie hiermit zur Verteidigung meiner Bachelorarbeit mit dem Titel ""An Algorithm for Hierarchical Clustering - Experiments and Analysis" ein. Der Vortrag wird am 02.03.2023 um 12:00 Uhr in der Takustraße 9 Raum 055 auf Englisch stattfinden. Erstgutachter: Prof. Dr. László Kozma Zweitgutachter: Prof. Dr. Helmut Alt Betreuer: Prof. Dr. László Kozma Viele Grüße, Arman Durmus *** Dear Sir or Madam, I hereby invite you to the defense of my bachelor thesis titled "An Algorithm for Hierarchical Clustering - Experiments and Analysis". The presentation will take place on 02.03.2023 at 12:00 am in Takustraße 9 room 055 in english. First examiner: Prof. Dr. László Kozma Second examiner: Prof. Dr. Helmut Alt Supervisor: Prof. Dr. László Kozma Best regards, Arman Durmus *** Zusammenfassung(Abstract): We present and analyze a new algorithm idea to hierarchically cluster data, and show that it performs well compared to other established hierarchical clustering methods when evaluated based on Dasgupta’s cost function. We prove that in one iteration, our algorithm finds the optimal hierarchical clustering tree for the given order of the points, when limited to hierarchical clustering trees the leaves of which have the same ordering as said points. Additionally, we show that the cost of the found tree can only improve or remain the same with each iteration. Thus, the presented algorithm can be used for hierarchical clustering tasks, or on the results of other hierarchical clustering algorithms to improve those, and leaves room for theoretical improvements and experimentation. ================================================================== Subject: Mittagsseminar am Dienstag, 28.02 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 28. Februar 2023, 12:00 Uhr, SR 055, Takustraße 9 Wolfgang Mulzer zum Thema: Nabil Mustafa's proof of the eps-net theorem ================================================================== Subject: Mittagsseminar am Donnerstag 23.02.2023 Jetzt nochmal mit korrektem Datum... Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am         Donnerstag, 23. Februar 2023, 12:00 Uhr, SR 055, Takustraße 9         Kristin Knorr         zum Thema: Crossing-free Matchings in Geometric Graphs Part Two ================================================================== Subject: Mittagsseminar am Dienstag 21.02.2023 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am         Dienstag, 21. Februar 2023, 12:00 Uhr, SR 055, Takustraße 9         Kristin Knorr         zum Thema: Crossing-free Matchings in Geometric Graphs Part Two ================================================================== Subject: Mittagsseminar am Dienstag 21.02.2023 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am         Dienstag, 21. Februar 2023, 12:00 Uhr, SR 055, Takustraße 9         Helena Bergold         zum Thema: Strong Erdős-Hajnal properties in chordal graphs ================================================================== Subject: Mittagsseminar am Donnerstag 16.02.2023 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Donnerstag, 16. Februar 2023, 12:00 Uhr, SR 055, Takustraße 9 Jonas Cleve zum Thema: Minimum color number for gap-less nearest neighbor graphs in 1d ================================================================== Subject: Mittagsseminar am Donnerstag 09.02. und Dienstag 14.02. Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am         Donnerstag, 09. Februar 2023, 12:00 Uhr, SR 055, Takustraße 9         Michaela Borzechowski         zum Thema: On Phases of USOs - Part 1: Definitions & a small proof         Dienstag, 14. Februar 2023, 12:00 Uhr, SR 055, Takustraße 9         Michaela Borzechowski         zum Thema: On Phases of USOs - Part 2: More proofs ================================================================== Subject: Mittagsseminar am Dienstag, 07.102 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 07. Februar 2023, 12:00 Uhr, SR 055, Takustraße 9 Wolfgang Mulzer zum Thema: Lower Bounds for Selection (results from the 80s) ================================================================== Subject: Mittagsseminar am Donnerstag, 02.02.2023 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Donnerstag, 02.Februar 2023, 12:00 Uhr, SR 055, Takustraße 9 JKatharina Klost zum Thema: Shortest Paths with Multiple Edge-Cost Estimates Please observe the current safety constraints (FFP2 masks recommended), seehttps://www.fu-berlin.de/sites/coronavirus/ ================================================================== Subject: Mittagsseminar am Dienstag, 24.01. Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 24. Januar 2023, 12:00 Uhr, SR 053, Takustraße 9 Johannes Obenaus zum Thema: Flip Graphs for Arrangements of Pseudocircles Please observe the current safety constraints (FFP2 masks recommended), see https://www.fu-berlin.de/sites/coronavirus/ Mittagsseminar schedule: ================================================================== Subject: [Mittagsseminar T Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Donnerstag, 19.01.2023, 12:00 Uhr, SR 055, Takustraße 9 Helmut Alt zum Thema: Online Sorting ================================================================== Subject: Mittagsseminar am Dienstag, 17.01. Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 17. Januar 2023, 12:00 Uhr, SR 053, Takustra=DFe 9 Mahmoud Elashmawi zum Thema: Crossing-Free Matchings in Geometric Graphs Please observe the current safety constraints (FFP2 masks recommended), see https://www.fu-berlin.de/sites/coronavirus/ Mittagsseminar schedule: ================================================================== Subject: Mittagsseminar 12.1.2023 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Donnerstag, 12.01.2023, 12:00 Uhr, SR 055, Takustraße 9 Max Willert zum Thema: Cantor vs. Kronecker ================================================================== Subject: Fwd: [i-prof] Einladung zur Verteidigung meiner Bachelorarbeit Today's mittagsseminar (in German). Cheers Wolfgang -------- Forwarded Message -------- Subject: [i-prof] Einladung zur Verteidigung meiner Bachelorarbeit Date: Thu, 29 Dec 2022 22:35:18 +0100 Sehr geehrte Damen und Herren, hiermit lade ich Sie zur Verteidigung meiner Bachelorarbeit mit dem Titel "Analyse und Vergleich verschiedener Sortieralgorithmen" ein. Die Verteidigung findet am Donnerstag, den 05.01 um 12:00 Uhr im SR 055 statt. Erstgutachter: Prof. Dr. Wolfgang Mulzer Zweitgutachter: Dr. rer. nat. Max Willert Mit freundlichen Grüßen, Glenn Schneider Zusammenfassung: Sortierverfahren sind ein großes Thema in der Informatik und über die Jahre werden immer wieder neue Sortieralgorithmen entwickelt. Sortieralgorithmen sind außerdem oft Themen von wissenschaflichen Arbeiten und es wird heute noch erforscht, wie man sie verbessern kann. Es stellt sich die Frage, warum es so viele verschiedene Algorithmen gibt, was deren Vor-­ und Nachteile sind und in welchen Situationen man welchen Algorithmus verwenden sollte. Gibt es einen ”besten” Sortieralgorithmus den man immer verwenden soll oder ist es eher sinnvoll, basierend auf den gegebenen Daten einen bestimmten Algorithmus auszuwählen? Das Ziel dieser Arbeit ist die Implementierung von ausgewählten Sortieralgorithmen und die Erstellung verschiedener Testfälle, mit denen die Algorithmen in unterschiedlichen Situationen getestet und verglichen werden können. Damit soll experimentell die Frage beantwortet werden, wie sehr es sich lohnt, je nach Situation verschiedene Sortieralgorithmen zu verwenden. ================================================================== Subject: Mittagsseminar am Dienstag, 03.01.2023 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 03. Januar 2023, 12:00 Uhr, SR 055, Takustraße 9 Jonas Cleve zum Thema: The (geometric) goat problem Please observe the current safety constraints (FFP2 masks recommended), see https://www.fu-berlin.de/sites/coronavirus/ ==================================================================