Problem Sheet 1 [pdf]

Problem Sheet 2 [pdf]

Problem Sheet 3 [pdf]

Lecture template [pdf],  [tex]

Lecture 1 -- Self adjusting data structures, amortized analysis, self adjusting lists [pdf]

Lecture 2 -- 2-competitiveness of `move to front' heuristic', self adjusting binary search trees [pdf]

Lecture 3 -- Splay trees, their performance and related conjectures [pdf]

Lecture 4 -- Interleave lower bound, Tango trees, an O(log log n)- competitive binary search tree [pdf]

Lecture 5, 6 -- Geometric view of binary search trees [pdf]

Lecture 7 (Preliminary version) -- Hashing, FKS perfect hashing  [pdf]

Lecture 8 -- Cuckoo hasing, dynamic perfect hashing [pdf]

Lecture 9 -- van Emde Boas priority queue and Y-Fast tries [pdf]

Lecture 10 -- Fusion Trees  [pdf]

Lecture 11 -- Predecessor Lower Bound  [pdf]

Lecture 12 -- Predecessor Lower Bound (Cont'd)  [pdf]

Lecture 13 -- Sorting in O(n log log n) time (Scribe: Meesum)  

Lecture 14 -- Link-Cut Trees  [pdf]

Lecture 15 -- Fully dynamic connectivity in polylogarithmic time  [pdf]

Lecture 16, 17 -- Dynamic all pairs shortest paths [pdf]

Lecture 18 -- Lower bounds for dynamic connectivity [pdf]

Lecture 19,20 -- Suffix trees and arrays  [pdf]

Lecture 21 -- Linear time construction of Suffix trees and arrays  [pdf]

Lecture 22 -- Succinct Data Structures (Scribe: Meesum)  

Lecture 23 -- Search tree attaining unified bound (Arjun Arul)  

Lecture 24 -- Data structures for range minima/mode (Anudhyan)  

Lecture 25 -- External memory data structures  [pdf]

Lecture 26 -- Geometric data structures (Schion)  

Lecture 27 -- Lower bound for text indexing (Ashutosh)  

Lecture 28 -- Top trees (Anil Shukla)  [pdf]

Lecture 29 -- Retroactive data structures (Sankardeep)  

Lecture 30 -- Online optimal structure for planar point location (Meesum)