Introduction to dynamic algorithms
Partial and fully dynamic algorithms.
The balanced binary tree technique.
Splay trees.
Note1, S

Dynamic trees
Linking and cutting trees.
Ta

*** Easter ***

*** Easter ***

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.1), 2.2

Dynamic algorithms for undirected graphs
Euler tour tree data structure.
Dynamic maintenance of connected components.
HLT 2.1,3; problem 5

van Emde Boas trees
van Emde Boas trees.
Dynamic word problems.
Note2,
FMS (introduction and sect.2.4), Problem 1, Problem 2

Dynamic word problems
Dynamic word problems (continued).

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 7

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 8

Dynamic geometric algorithms
Dynamic range search
Problem 9

Dynamic string algorithms (cont.)
Dynamic Pattern Matching.
(ABR)

Dynamic algebraic algorithms
Trivial dynamic solution: matrix multiplication
Balanced binary tree technique applied to prefix sum
Cut value technique applied to the discrete Fourier Transform
Global rebuilding applied to polynomial multiplication
Reductions between dynamic algebraic problems.
RT 1,3,4; (FHM 1, 2.1)

Dynamic algebraic algorithms (cont.)
Dynamic matrix inverse, adjoint, determinant
Dynamic transitive closure
San 4, 11

*** Ascension Day ***

Deadline for project hand-in

To be announced

Multiple choice test
NB: starts early at 9:45 (place will be announced)