*** Remember signing up for examination (during week 14, March 29 - April 4) ***
Advanced course at the Department of Computer Science, University of Aarhus in the 4th quarter, Spring 2004.
Usually each two-hour class will start with a lecture and end with a problem session related to the lectures of the previous week.
The course is evaluated by a grade from the 13-scale based on your response to 2 project assignments.
|March 29||Lecture D1||Introduction to dynamic algorithms
Partial and fully dynamic algorithms.
The balanced binary tree technique.
| Problem for D1: |
|Apr. 1||Lecture D2||van Emde Boas trees
van Emde Boas trees.
Dynamic word problems.
FMS (introduction and sect.2.4)
| Problems for D2:
|Apr. 5||Lecture D3||Dynamic trees
Linking and cutting trees.
| Problem for D3:
|Apr. 15||Lecture D4||Dynamic MST for plane graph
minimum and maximum spanning tree for plane graph and dual.
Maintaining min/max spanning tree for dynamic plane graph.
||Apr. 19||Lecture D5||Dynamic string algorithms
Deterministic coin tossing.
Signature encoding of strings.
Dynamic, persistent maintenance of a set of strings under concatenation, split, comparison.
MSU (RS 7)
| Problem for D5:
|Apr. 22||Lecture D6||Dynamic string algorithms (cont.)
Dynamic Maintenance of parenthesis balance information.
Randomized solution using the finger print technique.
Deterministic solution using the dynamic string data structure.
FHMRS 1-4, (RS 2,5,6,8)
| Problem for D6:
|Apr. 26||Lecture D7||Dynamic algorithms for undirected graphs
Euler tour tree data structure.
Dynamic maintenance of connected components.
||Apr. 29||Lecture D8||Undirected graphs (cont.)
Decremental minimum spanning forest.
Fully dynamic minimum spanning tree.
| Problem for D8:
|May 3||Lecture D9||Dynamic algorithms for directed graphs
Fully dynamic all pairs shortest paths.
||May 6||Lecture D10||Dynamic geometric algorithms
Dynamic range search
| Problem for D10:
|May 10||Lecture D11||Dynamic string algorithms (cont.)
Dynamic Pattern Matching.
||May 13||Lecture D12||Dynamic algebraic algorithms
Trivial dynamic solution: matrix multiplication
Cut value technique applied to the discrete Fourier Transform
Reductions between dynamic algebraic problems.
| Problem for D12: