Seminar Algorithms for Dynamic Data
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.
Requirement to complete this seminar is a firm grasp of the topics of data structures, algorithms and the computability and complexity. Knowledge from the course "Complexity Theory" is beneficial but not required.