Table of Contents

1 Introduction
1.1 Algorithms
1.2 Functional languages
1.3 Bibliographical notes

2 Functional programming in Haskell
2.1 About the language
2.2 Equations and functions
2.3 Basic types and constructed types
2.4 Lists
2.5 Higher-order functional programming techniques
2.6 Algebraic types and polymorphism
2.7 Arrays
2.8 Type classes and class methods
Exercises
2.9 Bibliographical notes

3 The efficiency of functional programs
3.1 Reduction order
3.2 Analysing the efficiency of programs
3.3 Program transformation
3.4 Conclusion
Exercises
3.5 Bibliographical notes

4 Concrete data types
4.1 Lists
4.2 Trees
4.3 Arrays
Exercises
4.4 Bibliographical notes

5 Abstract data types
5.1 Introduction
5.2 Stacks
5.3 Queues
5.4 Priority queues
5.5 Sets
5.6 Tables
5.7 Binary search trees
5.8 Heaps
5.9 AVL trees
Exercises
5.10 Bibliographical notes

6 Sorting
6.1 Introduction
6.2 Comparison-based sorting
6.3 Basic sorting algorithms
6.4 Tree-based sorting
6.5 Efficiency of comparison-based algorithms
6.6 Representation-based sorting
Exercises
6.7 Bibliographical notes

7 Graph algorithms
7.1 Definitions and terminology
7.2 The graph ADT
7.3 Depth-first and breadth-first search
7.4 Topological sort
7.5 Minimum spanning tree
7.6 Depth-first search trees and forests
7.7 Conclusion
Exercises
7.8 Bibliographical notes

8 Top-down design techniques
8.1 Divide-and-conquer
8.2 Backtracking search
8.3 Priority-first search
8.4 Greedy algorithms
Exercises
8.5 Bibliographical notes

9 Dynamic programming
9.1 Introduction
9.2 The dynamic programming higher-order function
9.3 Chained matrix multiplications
9.4 Optimal binary search trees
9.5 All-pairs shortest path
9.6 The travelling salesperson
9.7 Conclusion
Exercises
9.8 Bibliographical notes

10 Advanced topics
10.1 Process network
10.2 Monads
10.3 Parallel algorithms
10.4 Bibliographical notes

Bibliography

A Haskell implementations

B Mathematical background
B.1 Notation
B.2 Logarithms
B.3 Summation formulas
B.4 Solving recurrence equations

Index