Lecture #1
Mon 29/07

Introduction to the course • Admin and logistics • ADTs and data structures  examples


Sign up on Ed discussions

Lecture #2
Tue 30/07

Dynamic arrays  linked lists vs arrays • Amortized analysis  aggregate method


PS0 released

Lecture #3
Wed 31/07

Dynamic arrays • Amortized analysis  accounting and potential methods



Lecture #4
Thu 01/08

Dynamic arrays with insertions and deletions  amortized analysis using the potential method



Lecture #5
Mon 05/08

Basic discrete probability  sample spaces, events, independence, union bound



Lecture #6
Tue 06/08

Random variables and their properties  examples • Quicksort



Lecture #7
Wed 07/08

Quicksort  correctness, recurrence for running time, randomization



Lecture #8
Thu 08/08

Analysis of randomized quicksort


PS1 released

Lecture #9
Mon 12/08

Dictionaries and Hash tables  tradeoffs between runningtime and size, random hash functions and collisions



Lecture #10
Tue 13/08

Random hash functions and collisions  the birthday problem



Tutorial #1
Wed 14/08

Based on Problem sets 0 and 1


PS2 released

Lecture #11
Mon 19/08

Universal hash families I  construction and analysis



Lecture #12
Tue 20/08

Universal hash families II  more constructions and analysis



Lecture #13
Wed 21/08

Perfect hashing  static dictionaries and FKS hashing



Test #1
Thu 22/08

Based on Lectures 1  8 (Problem sets 0, 1, 2)



Lecture #14
Mon 26/08

Hashing using open addressing  linear probing


PS3 released

Lecture #15
Tue 27/08

Hashing using open addressing  linear probing (contd.)



Lecture #16
Wed 28/08

Skip lists  definition, examples, implementation details

 Sections 4.1, 4.2  Morin


Tutorial #2
Thu 29/08

Based on Problem set 3



Quiz #1
Mon 02/09

Based on Lectures 1 13 (Problem sets 0, 1, 2, 3)



Lecture #17
Tue 03/09

Skip lists  analysis • Binary search trees  examples



Lecture #18
Wed 04/09

Binary search trees  search, insert and delete operations, examples, time complexity



Lecture #19
Thu 05/09

Balanced BSTs  definitions, examples • Selfadjusting BSTs  handling searches and deletions


PS4 released

Lecture #20
Mon 09/09

Scapegoat trees  handling searches and insertions, examples, analysis



Lecture #21
Tue 10/09

Scapegoat trees  analysis (contd.) • Priority queues  binary minheaps, properties and examples



Lecture #22
Wed 11/09

Binary heaps  examples, properties, algorithms and complexity • Minmax heaps  examples and properties



Lecture #23
Thu 12/09

Minmax heaps  examples, implementation details, time complexity • Binomial heaps  properties, examples


PS5 released

Lecture #24
Mon 16/09

Binomial heaps  implementing insert and extractmin using merges, bounds on runningtime • Lazier binomial heaps  faster insertions at the cost of extractmin



Lecture #25
Wed 18/09

Lazy binomial heaps  amortized complexity of extractmin • Fibonacci heaps  examples, decreasing keys using cascading cuts

 Sections 19.2, 19.3  CLRS

