2 Outline

This outline will be mostly correct in terms of topics and ordering. Times are hard to estimate.

1. Tools and techniques.

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

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

Introduction to OCaml.

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. Binary tries.

4. Text searching and compression.

A unified approach to string matching: prefix preprocessing, Boyer-Moore, KMP. General tries. Compressed tries. Suffix tries. Suffix arrays. Lempel-Ziv compression. Other topics if time permits (HAMT, ternary search trees, Burrows-Wheeler transform).

5. Hashing (the virtues of imperfection).

Chaining. Open addressing. Cuckoo hashing. Perfect hashing.