,Programming Algorithms
A comprehensive guide to writing efficient programs
with examples in Lisp
Vsevolod Domkin
This book is for sale at http://leanpub.com/progalgs
This version was published on 2020-06-21
* * * * *
This is a Leanpub book. Leanpub empowers authors and publishers
with the Lean Publishing process. Lean Publishing is the act of
publishing an in-progress ebook using lightweight tools and many
iterations to get reader feedback, pivot until you have the right book
and build traction once you do.
* * * * *
© 2020 Vsevolod Domkin
,Table of Contents
Introduction
Why Algorithms Matter
A Few Words about Lisp
Algorithmic Complexity
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
Essential Data Structures
1 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
Take-Aways
2 Arrays
Arrays as Sequences
Dynamic Vectors
Why Are Arrays Indexed from 0
Multi-Dimensional Arrays
Binary Search
Binary Search in Action: a Fast Specialized In-Memory DB
Sorting
O(n^2) Sorting
Quicksort
Production Sort
Performance Benchmark
Take-Aways
3 Linked Lists
, Lists as Sequences
Lists as Functional Data Structures
Different Kinds of Lists
FIFO & LIFO
Queue
Stack
Deque
Stacks in Action: SAX Parsing
Lists as Sets
Merge Sort
Parallelization of Merge Sort
Lists and Lisp
Take-Aways
4 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
Take-Aways
Derivative Data Structures
5 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
A comprehensive guide to writing efficient programs
with examples in Lisp
Vsevolod Domkin
This book is for sale at http://leanpub.com/progalgs
This version was published on 2020-06-21
* * * * *
This is a Leanpub book. Leanpub empowers authors and publishers
with the Lean Publishing process. Lean Publishing is the act of
publishing an in-progress ebook using lightweight tools and many
iterations to get reader feedback, pivot until you have the right book
and build traction once you do.
* * * * *
© 2020 Vsevolod Domkin
,Table of Contents
Introduction
Why Algorithms Matter
A Few Words about Lisp
Algorithmic Complexity
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
Essential Data Structures
1 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
Take-Aways
2 Arrays
Arrays as Sequences
Dynamic Vectors
Why Are Arrays Indexed from 0
Multi-Dimensional Arrays
Binary Search
Binary Search in Action: a Fast Specialized In-Memory DB
Sorting
O(n^2) Sorting
Quicksort
Production Sort
Performance Benchmark
Take-Aways
3 Linked Lists
, Lists as Sequences
Lists as Functional Data Structures
Different Kinds of Lists
FIFO & LIFO
Queue
Stack
Deque
Stacks in Action: SAX Parsing
Lists as Sets
Merge Sort
Parallelization of Merge Sort
Lists and Lisp
Take-Aways
4 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
Take-Aways
Derivative Data Structures
5 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
