DynAlg
|
Week by week
Preliminary course plan.
| Week |
Lectures |
Problems |
Week 15
10/04 - 11/04
|
Thursday
Introduction to dynamic algorithms
Partial and fully dynamic algorithms.
The balanced binary tree technique.
Splay trees.
Note1, S
|
|
Week 16
14/04 - 18/04
|
Monday
Dynamic trees
Linking and cutting trees.
Problem 4.
Ta
Thursday
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
|
S.exercise.1.1+1.4
problem 10
|
Week 17
21/04 - 25/04
|
Monday
Dynamic algorithms for undirected graphs
Euler tour tree data structure.
Dynamic maintenance of connected components.
HLT 2.1,3; problem 5
Thursday
van Emde Boas trees
van Emde Boas trees.
Dynamic word problems.
Note2,
FMS (introduction and sect.2.4), Problem 1, Problem 2
|
|
Week 18
28/04 - 2/05
|
Monday
Dynamic word problems
Dynamic word problems (continued).
Thursday
*** Ascension Day ***
|
|
Week 19
5/05 - 9/05
|
Monday
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
Thursday
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
|
|
Week 20
12/05 - 16/05
|
Monday
*** Whit Monday ***
Thursday
Dynamic geometric algorithms
Dynamic range search
Problem 9
|
|
Week 21
19/05 - 23/05
|
Monday
Dynamic string algorithms (cont.)
Dynamic Pattern Matching.
(ABR)
Thursday
Dynamic algorithms for directed graphs
Fully dynamic all pairs shortest paths.
(DI,) Th2 1-2, (3)
Friday
Deadline for project hand-in
|
|
Week 22
26/05 - 30/05
|
Monday
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)
Thursday
To be announced
|
|
Week 23
2/06 - 2/06
|
Monday
Multiple choice test
NB: starts early at 9:45
|
|
|
