• Course web site
• Course structure
  • Course description
  • Week by week
• Materials
  • Literature
  • Program libraries
• Examimation
  • Project
  • Multiple choice test
• Who, where, when
  • Time and place
  • Staff and students

Literature

Kompendium for sale in Information Office at course start - is available now!

• (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
• (DI) Demetrescu, Italiano: A new approach to dynamic all pairs shortest paths JACM 51 (2004) 968--992.
• (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
• (San) Sankowski, Dynamic transitive closure via dynamic matrix inverse. FOCS'04, pp. 509--517