1 Introduction

      1.1 Required background

      1.2 Design philosophy

    2 Tools and Techniques

      2.1 Order notation and its discontents

        2.1.1 Ambiguities in mathematics

        2.1.2 A formal definition

        2.1.3 Abuse of notation

        2.1.4 What is running time?

        2.1.5 Precision leads to complications

        2.1.6 Algorithm analysis in practice

        2.1.7 More useful notation

      2.2 Functional programming and algorithm analysis

        2.2.1 The OCaml programming language

        2.2.2 Insertion sort

        2.2.3 Analyzing insertion sort

        2.2.4 Mergesort

        2.2.5 Algebraic data types

        2.2.6 The Sequence abstract data type

        2.2.7 Using a module to implement an ADT

        2.2.8 Immutable and mutable ADTs

        2.2.9 Improving the index operation for Sequence

    3 Queues

      3.1 Simple queues

        3.1.1 Mutation in OCaml

        3.1.2 Using arrays for queues

      3.2 Amortized analysis

      3.3 Lazy evaluation with memoization

        3.3.1 Incremental vs monolithic computation

        3.3.2 Flattening using streams

        3.3.3 Queues using streams

        3.3.4 Achieving constant time with full persistence

      3.4 Priority queues

        3.4.1 Functors (parameterized modules)

        3.4.2 Priority queues using Braun heaps

        3.4.3 LJNP trees revisited

        3.4.4 Merging heaps

    4 Sets and Maps

      4.1 Ordered domains

        4.1.1 Binary search trees: the naive implementation

        4.1.2 History of efficient implementations

        4.1.3 The general framework

        4.1.4 Treaps

          4.1.4.1 Probabilistic analysis of treap Map operations

          4.1.4.2 Remarks on the analysis of set operations

          4.1.4.3 Reusing the treap analysis for added benefit

        4.1.5 AVL trees

        4.1.6 Weight-balanced trees

        4.1.7 Red-black trees

      4.2 Binary tries

    5 Text Processing

      5.1 Simple exact matching

        5.1.1 The naive algorithm

        5.1.2 The Gusfield-Main-Lorentz (GML) algorithm

        5.1.3 An overview of classical algorithms

          5.1.3.1 The Knuth-Morris-Pratt (KMP) algorithm

          5.1.3.2 The Boyer-Moore (BM) algorithm

      5.2 Suffix trees

        5.2.1 From suffix tries to suffix trees

        5.2.2 Constructing suffix trees

        5.2.3 Applications of suffix trees

      5.3 Suffix arrays

        5.3.1 Search using a suffix array

        5.3.2 Constructing a suffix array

    6 Hashing

      6.1 Chaining

        6.1.1 Universal hash functions

        6.1.2 Balls in boxes

      6.2 Open addressing

      6.3 Cuckoo hashing

      6.4 Perfect hashing

    7 Sources and Resources

      7.1 Acknowledgements