Probability
[CLRS: Appendix C]
Apr 1

Randomized Searching
[CLRS: Chapter 5]
Apr 3

Randomized Quick Sort
[CLRS: Section 7.3-4]
Apr 8

Verifying Matrix Multiplication

Apr 10

Primality Testing
[CLRS: Section 31.8]
Apr 15

Randomized Min-Cut

Apr 17

Amortized Analysis
[CLRS: Chapter 16]
Apr 22

Disjoint Sets
[CLRS: Chapter 19]
Apr 24

Universal Hashing
[paper]
[CLRS: Chapter 11]
Apr 29

Skip List
[paper]
May 1

2-3 Trees
[CLRS: Chapter 18]
May 6

MIDTERM EXAM
May 8

Treaps
[paper]
May 13

Splay Trees
[paper]
May 15

String Matching
[CLRS: Sections 31.1, 31.2]
May 20

Z Algorithm
[G: Chapter 1]
May 22

Knuth-Morris-Pratt Algorithm
[G: Sections 2.3, 3.3]
May 27

Boyer-Moore Algorithm
[G: Sections 2.2, 3.1]
May 29

Suffix Trees
[G: Chapter 5]
Jun 3

Suffix Arrays
[G: Section 7.14]
Jun 5

FINAL EXAM
Jun 10