CSC378 Online Notes

The Notes

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
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
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

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
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