Dynamic Algebraic Algorithms

CS 8803 - DAA, Fall 2022

Time: Mon/Wed 3:30-4:45pm.
Location: Engineering Sci and Mechanics 202
Office hours: Tue 4-5pm in KACB 2116
TA: Mehrdad Ghadiri
Instructor: Jan van den Brand

Access course on canvas.

Description

Dynamic algebraic algorithms allow to efficiently maintain properties of matrices and vector spaces that change over time. These techniques can also be used to maintain properties of a graph while the graph changes (e.g. the shortest path in a road network under changing traffic conditions). When used as a subroutine, dynamic algebraic techniques can accelerate many iterative algorithms. This course will explore different algorithmic techniques, connections and applications related to dynamic algebraic algorithms, including: Prerequisites are basic knowledge of linear algebra (matrices, determinant, inverse etc), probability theory and theoretical analysis of algorithms.
This is a theory course, both the lecture and the problem sets are proof-oriented.

Grading

Problemsets: You are encouraged to collaborate, but you must write your own solutions.

Final project: The project should demonstrate understanding of tools and techniques covered in this course. A possible project could be one of the following:

The list above is a suggestion and you can propose another project. You are encouraged to relate the project to your research interests, but it must involve techniques covered in this course. Projects must be proposed in advance (some time in October) so I can confirm scope and topic fit. You can work in groups but the scope of the project should match the group size.

Optional: Depending on demand, there will be an option to present your project.