Pearls of Functional Algorithm Design

Cover
Half-title
Title
Copyright
Dedication
Content
Preface
1 The smallest free number
	Introduction
	An array-based solution
	A divide and conquer solution
	Final remarks
2 A surpassing problem
	Introduction
	Specification
	Divide and conquer
	Final remarks
	References
3 Improving on saddleback search
	Afterword
	References
4 A selection problem
	Introduction
	Formalisation and first steps
	Divide and conquer
	Final remarks
	References
5 Sorting pairwise sums
	Introduction
	Lambert’s algorithm
	Divide and conquer
	Final remarks
	References
6 Making a century
	Introduction
	A little theory
	Making a century
	Final remarks
	References
7 Building a tree with minimum height
	Introduction
	First steps
	Fusion
	Optimal insertion
	Final remarks
	References
8 Unravelling greedy algorithms
	Introduction
	Specification
	Derivation
	Final remarks
	References
9 Finding celebrities
	Afterword
	References
10 Removing duplicates
	Introduction
	A first version
	A generalisation
	Introducing sets
	Final remarks
	References
11 Not the maximum segment sum
	Introduction
	Specification
	Derivation
	Final remarks
	References
12 Ranking suffixes
	Introduction
	Specification
	Properties of rank
	A better algorithm
	Proof
	A better rank
	The final algorithm
	Analysis
	Experimental results
	Final remarks
	References
13 The Burrows—Wheeler transform
	Introduction
	Defining the BWT
	Recreational calculation
	A faster algorithm
	Transform revisited
	Final remarks
	References
14 The last tail
	Introduction
	An inductive definition
	Borders
	Border
	Cocktail
	Reducing the problem size
	Final optimisations
	Final remarks
	References
15 All the common prefixes
	Introduction
	A key property
	Dara Refinement
	Final remarks
	References
16 The Boyer--Moore algorithm
	Introduction
	The scan lemma
	The Boyer-Moore algorithm
	Shifting
	A final improvement
	Computing shifts
	Final remarks
	References
17 The Knuth–Morris–Pratt algorithm
	Introduction
	First steps
	Data refinement
	Trees
	Final remarks
	References
18 Planning solves the Rush Hour problem
	Introduction
	Puzzles
	Planning
	Rush Hour
	Results
	Final remarks
	References
19 A simple Sudoku solver
	Introduction
	Specification
	Pruning the matrix of choices
	Single-cell expansion
	Final remarks
20 The Countdown problem
	Introduction
	A simple program
	Two optimisations
	An even stronger logality test
	Memoisation
	Skeleton trees
	A further experiment
	Final remarks
	References
21 Hylomorphisms and nexuses
	Introduction
	Folds, unfolds and hylomorphisms
	Three examples
	Building a nexus
	Why build the nexus?
	Final remarks
	References
22 Three ways of computing determinants
	Introduction
	The school-book method
	Using rational division
	Using integer division
	Interleaving
	Using no division
	A brief comparison
	Final remarks
	References
23 Inside the convex hull
	Introduction
	Background
	Convex hulls
	An incremental algorithm
	Finding a simplex
	Updates
	An inprovement
	Quick
Check
	Final remarks
	References
24 Rational arithmetic coding
	Introduction
	Arithematic coding with rational arithemetic
	Narrowing
	Models
	Encoding
	Decoding
	Incremental encoding and decoding
	Streaming
	Final remarks
	References
	Appendix
25 Integer arithmetic coding
	Introduction
	New definitions
	Incremental encoding and interval expansion
	Interval expansion
	A new difinition
	A crucial question
	A final problem
	Inverting streams
	The helper function
	Incremental decoding
	Final remarks
	Appendix
26 The Schorr–Waite algorithm
	Introduction
	Specification
	Safe replacement
	Eliminating duplicate entries
	Threading the stack
	Representing the stack by a linked list
	Final remarks
	References
27 Orderly insertion
	Introduction
	A naive algorithm
	An improved algorithm
	Proofs
	Implementation
	Final remarks
	References
28 Loopless functional algorithms
	Introduction
	Loopless algorithms
	Four warm-up exercises
	Boustrophedon product
	Tupling
	Trees and queues
	Final remarks
	References
29 The Johnson–Trotter algorithm
	Introduction
	A recursive formulation
	The plan
	A loopless algorithm
	Final remarks
	References
30 Spider spinning for dummies
	Introduction
	A loopless program
	Spider spinning with general spiders
	A loopless algorithm
	Parity spiders
	The remaining steps
	The initial state
	Final remarks
	References
Index