- References will appear as
**RED TEXT**. In these references,

**CLR**means the course text by Cormen, Leiserson, and Rivest,**L&D**means ``Data Structures and their Algorithms'' by Lewis and Denenberg, and**Weiss**means ``Data Structures and Algorithm Analysis in C'' by Weiss.

- Questions will appear as
**PURPLE TEXT**in boxes. Click on the box to (maybe) get an answer.

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 |

Up to CSC378 home page