| Introduction | Jan 10 lecture |
Introduction to complexity analysis How to analyze with O() Formal definitions of asymptotic notation Log/log graphs: estimating asymptotic complexity by experiment | |||
| Jan 17 tutorial |
Analysis of recursive programs Height of a complete binary tree | ||||
| Priority Queues |
Jan 17 lecture |
Abstract data types Array heaps BuildHeap, with analysis | |||
| Jan 24 tutorial |
K-way merge of lists Probability Review | ||||
| Jan 24 lecture |
Leftist Trees | ||||
| Dictionaries |
Optimal lists | ||||
| Jan 31 tutorial |
Brief review of binary search trees (BSTs) Optimal BSTs | ||||
| Jan 31 lecture |
Move-to-front lists Insert and Delete in BSTs | ||||
| Feb 7 tutorial |
Assignment 1 returned Solutions and Marking Guide discussed | ||||
| Feb 7 lecture |
Red-Black trees Red-Black insertion | ||||
| Feb 14 tutorial | Midterm 1 | ||||
| Augmenting Data Structures |
Feb 14 lecture |
Augmenting BSTs: - prefix sum - rank - interval trees | |||
| Feb 21 | Reading week: no tutorial, no lecture | ||||
| Feb 28 tutorial | Midterm 1 returned and discussed | ||||
| Feb 28 lecture |
More on interval trees (same notes as above) Hulltrees (assignment 2) Quick introduction to Binary Space Partitions | ||||
| Randomized Alorithms |
Mar 7 tutorial |
Hashing with open addressing Generating random permutations | |||
| Mar 7 lecture |
Binary Space Partitions | ||||
| Mar 14 tutorial | no tutorial | ||||
| Mar 14 lecture |
Universal hashing Skip lists | ||||
| Mar 21 tutorial | Midterm 2 | ||||
| Mar 21 lecture |
Another example of Universal Hashing Perfect hashing | ||||
| Mar 28 tutorial |
Midterm 2 returned and discussed Random BSTs and Treaps | ||||
| Amortized Analysis |
Mar 28 lecture |
Introduction to Amortized Analysis Potential method | |||
| Apr 4 tutorial |
Queue with maximum element (in Postscript) time permitting: Convex Hull algorithm (in Postscript) | ||||
| Apr 4 lecture |
Amortized analysis of the MTF list Dynamic Stacks | ||||