appendix-b
appendix B Further reading
These are some of the resources I used when I had to learn about arcane data structures and algorithms. This list is far from exhaustive. You can find many of these papers at https://github.com/ericlippert/FabulousAdventures.
Chapter 2
- [Hughes] A Novel Representation of Lists and Its Application to the Function Reverse (1984) describes the Hughes list.
- [Okasaki] Purely Functional Data Structures, both the 1996 thesis and the 1999 book based on it, is a deep dive into amortized performance analysis of persistent data.
Chapter 3
- [Guibas et al.] A New Representation for Linear Lists (1977) introduces the concept of finger trees and applies it to B-trees.
- [Hinze et al.] Finger trees: a simple general-purpose data structure (2006) shows how to create deques, priority queues, and other data structures from finger trees.
Chapter 4
- [Conway et al.] Winning Ways for Your Mathematical Plays, Volume 2 (1982) explains Life.
- [Gosper] Exploiting Regularities in Large Cellular Spaces (1984) sketches Gosper’s HashLife algorithm but doesn’t provide an implementation.
Chapter 5
- [Lucchesi et al.] Applications of Finite Automata Representing Large Vocabularies (1993)
- [Watson] A taxonomy of finite automata minimization algorithms (1993)
- [Daciuk et al.] Incremental Construction of Minimal Acyclic Finite-state Automata (2000)
Chapter 6
- [Even] Algorithmic Combinatorics (1973)
- [Cover] Enumerative Source Encoding (1973)
- [Sedgewick] Permutation Generation Methods (1977)