Dynamic algorithms, F2004 (4th quarter)

*** 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.

Literature

Exam Projects

The course is evaluated by a grade from the 13-scale based on your response to 2 project assignments.

Course Plan

(preliminary)

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 1-4, (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


Last modified: Tue Apr 27 19:47:16 2004.
Gudmund S. Frandsen
gudmund@daimi.au.dk