Seminar Algorithms for Dynamic Data
Inhalt
In many applications, we need to solve the same algorithmic problems repeatedly over dynamically changing data such as, for example, social networks evolving over time or relational databases that are frequently updated. In such scenarios, it may be inefficient to solve the problem again and again from scratch after each change of the data. Instead, we can try to design data structures that can be efficiently updated as the data evolve, and that support solving the algorithmic problem more efficiently.
A well-known example is "dynamic graph connectivity": we can decide the connectivity of an undirected graph using only polylogarithmic time after each update.
In this seminar, we will study dynamic algorithms and data structures for different applications, focusing on the theoretical analysis.
Voraussetzungen
Voraussetzung für eine erfolgreiche Teilnahme am Seminar sind ein sicherer Umgang mit den Themen der Vorlesungen Datenstrukturen und Algorithmen und Berechenbarkeit und Komplexität. Kenntnisse aus der Vorlesung Komplexitätstheorie sind hilfreich aber nicht obligatorisch.
Organisation
Dozent