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.

course description.
Instructor: Gudmund Skovbjerg Frandsen
Classes: Monday 11-13 and Thursday 9-11 in Shannon 164 (Finlandsgade 24A).
Starting March 29 and ending May 17.

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

(Problems 1-11) Problems for dynamic algorithms.
(Note) Introduction to dynamic algorithms.
(Note) van Emde Boas trees.
(S) Skyum: A self-adjusting datastructure - splay trees.
(FMS) Frandsen, Miltersen, Skyum, Dynamic word problems, Journal of the ACM 44 (1997) 257 - 271
(T) Tarjan, Data structures and Network algorithms, SIAM, 1983. Chapter 5: Linking and cutting trees.
(EITTWY) Eppstein, Italiano, Tamassia, Tarjan, Westbrook, Yung, Maintenance of a Minimum Spanning Forest in a Dynamic Plane Graph, J. Algorithms 13 (1992) 33--54, and J. Algorithms 15 (1993) 173.
(HLT) Holm, Lichtenberg, Thorup: Poly-logarithmic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. JACM 48 (2001) pp.723-760
(T2) Thorup: Near-optimal fully-dynamic graph connectivity. STOC'00 pp.343-350
(DI) Demetrescu, Italiano: A new approach to dynamic all pairs shortest paths STOC'03 pp. 159--166.
(T3) Thorup: Fully Dynamic All Pairs Shortest paths: faster and allowing negative cycles, SWAT'04.
(RS) Rauhe, Skyum: Dyck sprogene, Dynamiske algoritmer og deres kompleksitet, speciale (in Danish), 1995.
(MSU) Mehlhorn, Sundar, Uhrig: Maintaining Dynamic Sequences Under Equality-Tests in Polylogarithmic Time. Algorithmica 17 (1997) 183-198.
(FHMRS) Frandsen, Husfeldt, Miltersen, Rauhe, Skyum: Dynamic Algorithms for the Dyck Languages. WADS'95, LNCS 955, pp.98-108.
(ABR) Alstrup, Brodal, Rauhe: Pattern Matching in Dynamic Texts. In Proc. 11th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 819-828, 2000.
(RT) Reif, Tate: On dynamic algorithms for algebraic problems. Journal of algorithms 22 (1997) pp. 347-371.
(FHM) Frandsen, Hansen, Miltersen. Lower bounds for dynamic algebraic problems. Information and Computation 171 (2001) pp. 333-349

Exam Projects

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

Project 1 (hand in by April 23) version 2 available, April 11 (LaTeX source, xfig source)
Project 2 (hand in by May 14) version 2 available, April 27 (LaTeX source, BibTeX source, xfig source)

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

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