Dynamic Graph Algorithms
This is an elective course meant for M.Sc students and third year B.Sc students.
Instructors:
Pranabendu Misra, Samir Datta, Prajakta Nimbhorkar
Topics covered so far (there are two lectures on each Friday):
- Aug 9 [PM]: Introduction to dynamic algorithms, dynamic connectivity in forests
- Aug 16[PM]: Dynamic connectivity in general graphs using layered forests (Ref: this paper and
these and these slides for the two lectures)
- Aug 16[PN]: Splay trees and their amortized analysis (Ref: this, this Also see this for motivation and example)