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

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)

*** Ascension Day ***

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

Deadline for project hand-in

*** Whit Monday ***

Project Feedback

Dynamic algebraic algorithms (cont.)
Dynamic Charateristic Polynomial
Dynamic Eigenproblem
(FS)

Multiple choice test
(preliminary - may be changed)