*** 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 twohour 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 13scale 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. Splay trees. Note, S 
Problem for D1: 6 S.exercise.1.1+1.4 
Apr. 1  Lecture D2  van Emde Boas trees van Emde Boas trees. Dynamic word problems. Note, FMS (introduction and sect.2.4) 
Problems for D2: 1 
Apr. 5  Lecture D3  Dynamic trees Linking and cutting trees. T 
Problem for D3: 4 
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. EITTWY 

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: 7 
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 14, (RS 2,5,6,8) 
Problem for D6: 8 
Apr. 26  Lecture D7  Dynamic algorithms for undirected graphs Euler tour tree data structure. Dynamic maintenance of connected components. HLT 2,3 

Apr. 29  Lecture D8  Undirected graphs (cont.) Decremental minimum spanning forest. Fully dynamic minimum spanning tree. HLT 4,5 
Problem for D8: 5 
May 3  Lecture D9  Dynamic algorithms for directed graphs Fully dynamic all pairs shortest paths. DI,T3 

May 6  Lecture D10  Dynamic geometric algorithms Dynamic range search 
Problem for D10: 9 
May 10  Lecture D11  Dynamic string algorithms (cont.) Dynamic Pattern Matching. ABR 

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. RT; FHM 
Problem for D12: 10 