-
Asymptotic notation
[CLRS]: 43-52
-
Intro to algorithm design
[CLRS]: 5-14, 23-25, 27-29; [more]
-
Elementary data structures
[CLRS]: 232-240, 246-248; [note]
-
More analysis techniques
-
Average-case analysis
[CLRS]: 114-116, 120-121; [more]
-
More on probabilistic analysis
[CLRS]: 139-141
-
Expected analysis
[CLRS]: 122-124
-
Permuting uniformly at random
[CLRS]: 126-128
-
Analyzing a Monte Carlo algorithm
[KT]: 708-713
-
Sorting
-
Bubble, Selection
[wiki]: 1, 2
-
Insertion, Shell
[CLRS]: 16-22; [wiki]: 1, 2
-
Bucket
[CLRS]: 200-202; [more]
-
Quick, Merge
[CLRS]: 170-176, 29-37
-
Heapsort
[CLRS]: 159-161
-
Lower bounding with decision trees
[CLRS]: 191-193
-
Counting, Radix
[CLRS]: 194-196, 197-199
-
Avg-case time: Insertion, Bucket
[note]; [CLRS]: 202-204
-
Expected time: Randomized quick
[CLRS]: 179, 181-184
-
Selection
-
Minimum and Maximum
[CLRS]: 213-215
-
Blum et al.,'s algorithm
[CLRS]: 220-222
-
Lower bounding with adversary arguments
[note]
-
Range minimum queries
[note]
-
Hoare's Las Vegas algorithm
[CLRS]: 215-219
-
A Monte Carlo algorithm
[MU]: 47, 51-52, 57-62
-
In dynamic sets with a BST
a variant of [CLRS]: 339-347
-
Amortized analysis
-
Three methods with two examples
[CLRS]: 451-461
-
Dynamic arrays
[CLRS]: 463-469
-
Heaps
-
Binary
[CLRS]: 151-159, 162-165, exer 6.1-2, 6.1-7, 6.3-3
-
Leftist
[note]
-
Fibonacci
[CLRS]: 505-526
-
Dictionaries: search trees
-
Binary search tree
[CLRS]: 286-299, exer 12.2-6
-
AVL tree
[note]
-
2-4 tree and its generalization
[CLRS]: 488-502
-
Red-black tree
[CLRS]: 308-329; [24vsRB]
-
Splay tree
[note]
-
Tries
[note]
-
More on suffix arrays
[wiki]: 1, 2 --- not covered this time
-
Randomized dictionaries
-
Randomly built BST
[CLRS]: 299-303; [Jensen's ineq]
-
Random treap
[MR]: 201-208 with mild modifications
-
Skip list
[note]
-
Hashing based dictionaries
-
Separate chaining
[CLRS]: 253-260, 263
-
2-Universal hashing
[CLRS]: 265, 267-268
-
Static perfect hashing
[CLRS]: 277-282
-
Open addressing
[CLRS]: 269-271, 274-276
-
Bloom filter for set membership
[note] --- AR
-
For disjoint-sets
-
Two representations
[CLRS]: 561-562, 564-571
-
Analysis of disjoint-set forest
[note]
-
For graphs
-
Three representations
[CLRS]: 589-592+, 562-564
-
Breadth-first traversal
[CLRS]: 594-601
-
Depth-first traversal
[CLRS]: 603-610
-
[CLRS]: Introduction to Algorithms by T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Third Edition.
-
For those (sub)topics covered in lectures but not detailed in the above textbook, links/notes are posted on this page.
-
AR stands for additional reading (no lecture delivered but included in syllabus).
