Dynamic algorithms, F2005.Q4 (F2004)

*** Remember signing up for examination: dansk, English (during week 14, April 4 - 11) ***

Advanced course at the Department of Computer Science, University of Aarhus in the 4th quarter, Spring 2005.

• course description (dansk).
• Instructor: Gudmund Skovbjerg Frandsen
• Classes: Wednesday 12-14 and Friday 10-12 in Shannon 157 (Finlandsgade 24A).
  Starting April 6 and ending May 27.

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

Kompendium for sale in Information Office at course start (week 14)

• (Problems 1-11) Problems for dynamic algorithms.
• (Note1) Introduction to dynamic algorithms.
• (Note2) 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
• (Ta) Tarjan, Data structures and Network algorithms, SIAM, CBMS 44, 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
• (Th1) 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.
• (Th2) Thorup: Fully Dynamic All Pairs Shortest paths: faster and allowing negative cycles, SWAT'04 pp. 384--396.
• (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

Course examination

The course is evaluated by a grade from the 13-scale based on a project and a multiple choice test.

• The project counts 50% in your final grade.
  You may work in groups of up to 3 people on the project.
  The project report is due May 20th at 12:00 (preferably by email). I want only one report from each group.
  Handwritten responses are not acceptable. You should use LaTeX or similar.
  Project, version 1, available Mar. 14th (LaTeX source)
• The multiple choice test counts the last 50% in your final grade.
  The test is 2 hours and takes place during the last class meeting on May 27th.
  The examination requirements (pensum) is all material from the lectures, i.e. Note1; Note2; S; FMS introduction and sect.2.4; Ta; EITTWY 1-2; MSU; RS 2,5,6,7,8; FHMRS 1-4; HLT 2-5.1; Th2 1-3; ABR; RT 1,3,4; FHM 1, 2.1;
  You are not allowed to consult the textbook or your notes during the test.
  A sample test is available.

Course Plan

Apr. 6	Lecture D1	Introduction to dynamic algorithms Partial and fully dynamic algorithms. The balanced binary tree technique. Splay trees. Note1, S	Problem for D1: 6 S.exercise.1.1+1.4
Apr. 8	Lecture D2	van Emde Boas trees van Emde Boas trees. Dynamic word problems. Note2, FMS (introduction and sect.2.4), Problem 2
Apr. 13	Lecture D3	Dynamic word problems Dynamic word problems (continued).	Problems for D3: 1
Apr. 15	Lecture D4	Dynamic trees Linking and cutting trees. Ta	Problem for D4: 4
Apr. 20	Lecture D5	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 1-2
Apr. 22		*** St. Bededag ***
Apr. 27	Lecture D6	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 D6: 7
Apr. 29	Lecture D7	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 D7: 8
May 4	Lecture D8	Dynamic algorithms for undirected graphs Euler tour tree data structure. Dynamic maintenance of connected components. HLT 2,3
May 6	Lecture D9	Undirected graphs (cont.) Decremental minimum spanning forest. Fully dynamic minimum spanning tree. HLT 4,5-5.1	Problem for D9: 5
May 11	Lecture D10	Dynamic algorithms for directed graphs Fully dynamic all pairs shortest paths. (DI,) Th2 1-3
May 13	Lecture D11	Dynamic geometric algorithms Dynamic range search	Problem for D11: 9
May 18	Lecture D12	Dynamic string algorithms (cont.) Dynamic Pattern Matching. ABR
May 20	Lecture D13	Dynamic algebraic algorithms Trivial dynamic solution: matrix multiplication Cut value technique applied to the discrete Fourier Transform Reductions between dynamic algebraic problems. RT 1,3,4; FHM 1, 2.1	Problem for D13: 10
May 27		Last session Multiple Choice Test (10:15-12:15). Course evaluation.