Advances in dynamic algorithms
This course is taught in English. This course was last offered in the summer term 2019/20.
Link to official course page
Summary
In many engineering and business applications, we observe a growing trend of data-driven research. That means, ever-growing amounts of data from users and cyber-physical systems are collected and analyzed, and finally turned into new devices and business models. Those data sets are not just extremely large but they are also highly dynamic. For example, think of mobile phone users navigating their routes from A to B via Google Maps. Here, the phone moves from one cell of the GSM network to the next and the traffic changes instantaneously. Then the optimal driving route from A to B may also change frequently. With hundreds of millions of users navigating at the same time, it is too costly and time-consuming to re-compute their shortest routes from scratch. The seminar deals with dynamic algorithms, which can update optimal solutions (such as shortest routes) exponentially faster for the new data than re-computing from scratch.
Tasks
The seminar will cover 14 topics related to dynamic algorithms. Each topic will be covered by one student, who will present the topic in a 25-minute presentation and a written report of 5-10 pages. Beyond that, each student will have to implement some code in C++ or Python on their subject, and demonstrate its capabilities and limitations on some real data set.
Requirements
Basic understanding of algorithms and their analysis. Knowledge of LaTeX for typesetting the report. Knowledge of C++ or Python to implement the algorithms.
Setup
Max. of 14 participants, 4 appointments à 90 mins. Amount of ECTS depends on your degree program.
Topics
- Dynamic bin packing
- Dynamic graph sparsification
- Dynamic maximal matching
- Dynamic graph coloring
- Dynamic connectivity
- Dynamic all-pairs shortest paths
- Dynamic hitting set
- Cell-probe lower bounds for dynamic problems
- Conditional lower bounds for dynamic problems
