6.8

2 Outline

This outline will be mostly correct in terms of topics and ordering. The times (if provided) will be largely guesses and may not be accurate. We’ll just start the material and see how it goes.

(Under construction.)

1. Tools and techniques.

Review: ADTs (immutable/mutable), algorithm analysis, order notation.

Review and update: persistence, recurrences, sequences, sets, maps.

Language introduction.

2. Queues of various flavours.

Simple queues. Amortized analysis. Banker’s method, physicist’s method. Lazy evaluation and memoization. Priority queues: Braun heaps, array-based heaps, maxiphobic heaps.

3. Maps on ordered domains.

A unified approach to balanced binary search trees: treaps, AVL, weight-balanced, red-black.

4. Hashing (the virtues of imperfection).

Chaining. Open addressing. Cuckoo hashing. Perfect hashing.

5. Text searching and compression.

String matching: prefix preprocessing, Boyer-Moore, KMP. Tries. Compressed tries. Suffix tries. Suffix arrays. HAMT. Ternary search trees. Burrows-Wheeler transform. Lempel-Ziv compression.