Programming Algorithms in Lisp: Writing Efficient Programs with Examples in ANSI Common Lisp

Table of Contents
About the Author
About the Technical Reviewer
Acknowledgments
Chapter 1: Introduction
	Why Algorithms Matter
	A Few Words About Lisp
Chapter 2: Algorithmic Complexity
Chapter 3: A Crash Course in Lisp
	The Core of Lisp
	A Code Example
	The REPL
	Basic Expressions
		Sequential Execution
		Branching
		Looping
		Procedures and Variables
		Comments
	Getting Started
Chapter 4: Data Structures
	Data Structures vs. Algorithms
	The Data Structure Concept
	Contiguous and Linked Data Structures
	Tuples
	Passing Data Structures in Function Calls
	Structs in Action: Union-Find
	Takeaways
Chapter 5: Arrays
	Arrays as Sequences
	Dynamic Vectors
	Why Are Arrays Indexed from 0
	Multidimensional Arrays
	Binary Search
		Binary Search in Action: A Fast Specialized In-Memory DB
	Sorting
		O(n^2) Sorting
		Quicksort
		Production Sort
		Performance Benchmark
	Takeaways
Chapter 6: Linked Lists
	Lists as Sequences
	Lists as Functional Data Structures
	Different Kinds of Lists
	FIFO and LIFO
		Queue
		Stack
		Deque
		Stacks in Action: SAX Parsing
	Lists as Sets
	Merge Sort
		Parallelization of Merge Sort
	Lists and Lisp
	Takeaways
Chapter 7: Key-Values
	Concrete Key-values
		Simple Arrays
		Associative Lists
		Hash-Tables
		Structs
		Trees
	Operations
	Memoization
		Memoization in Action: Transposition Tables
	Cache Invalidation
		Second Chance and Clock Algorithms
		LFU
		LRU
	Low-Level Caching
	Takeaways
Chapter 8: Hash-Tables
	Implementation
		Dealing with Collisions
		Hash-Code
		Advanced Hashing Techniques
	Hash-Functions
	Operations
		Initialization
		Access
		Iteration
	Perfect Hashing
		Implementation
		The CHM92 Algorithm
	Distributed Hash-Tables
	Hashing in Action: Content Addressing
	Takeaways
Chapter 9: Trees
	Implementation Variants
	Tree Traversal
	Binary Search Trees
	Splay Trees
		Complexity Analysis
	Red-Black and AVL Trees
	B-Trees
	Heaps
	Tries
	Trees in Action: Efficient Mapping
	Takeaways
Chapter 10: Graphs
	Graph Representations
	Topological Sort
	MST
		Prim’s Algorithm
		Kruskal’s Algorithm
	Pathfinding
		Dijkstra’s Algorithm
		A* Algorithm
	Maximum Flow
	Graphs in Action: PageRank
		Implementation
	Takeaways
Chapter 11: Strings
	Basic String-Related Optimizations
	Strings in the Editor
	Substring Search
		Knuth-Morris-Pratt (KMP)
		Boyer-Moore (BM)
		Rabin-Karp (RK)
		Aho-Corasick (AC)
	Regular Expressions
		Implementation of Thompson’s Construction
	Grammars
	String Search in Action: Plagiarism Detection
	Takeaways
Chapter 12: Dynamic Programming
	Fibonacci Numbers
	String Segmentation
	Text Justification
	Pathfinding Revisited
	LCS and Diff
	DP in Action: Backprop
	Takeaways
Chapter 13: Approximation
	Combinatorial Optimization
	Local Search
	Evolutionary Algorithms
	Branch and Bound
	Gradient Descent
		Improving GD
	Sampling
	Matrix Factorization
		Singular Value Decomposition
	Fourier Transform
		Fourier Transform in Action: JPEG
	Takeaways
Chapter 14: Compression
	Encoding
	Base64
	Lossless Compression
	Huffman Coding
		Huffman Coding in Action: Dictionary Optimization
	Arithmetic Coding
	DEFLATE
	Takeaways
Chapter 15: Synchronization
	Synchronization Troubles
	Low-Level Synchronization
	Mutual Exclusion Algorithms
	High-Level Synchronization
		Lock-Free Data Structures
		Data Parallelism and Message Passing
		STM
	Distributed Computations
		Distributed Algorithms
		Distributed Data Structures
		Distributed Algorithms in Action: Collaborative Editing
	Persistent Data Structures
	Takeaways
Afterword
Index