Master algorithms programming using Lisp, including the most important data structures and algorithms. This book also covers the essential tools that help in the development of algorithmic code to give you all you need to enhance your code.
Programming Algorithms in Lisp shows real-world engineering considerations and constraints that influence the programs that use these algorithms. It includes practical use cases of the applications of the algorithms to a variety of real-world problems.
What You Will Learn
• Program algorithms using the Lisp programming language
• Work with data structures, arrays, key-values, hash-tables, trees, graphs, and more
• Use dynamic programming
• Program using strings
• Work with approximations and compression
Who This Book Is For
Intermediate Lisp programmers wanting to do algorithms programming. A very experienced non-Lisp programmer may be able to benefit from this book as well.
About the Author
Vsevolod Domkin from Kyiv, Ukraine is a Lisp programmer and enthusiast, a natural language processing researcher, an occasional writer/blogger, and a teacher.
Author(s): Vsevolod Domkin
Edition: 1
Publisher: Apress
Year: 2021
Language: English
Commentary: Vector PDF
Pages: 390
City: New York, NY
Tags: Algorithms; Genetic Algorithms; Programming; Lisp; Data Structures; Gradient Descent; Dynamic Programming; Graph Algorithms; Hash Functions; Distributed Applications; Fourier Transform; Trees; Compression Algorithms; Approximation Algorithms; Dijkstra's Algorithm; Kruskal’s Algorithm; String Algorithms; Topological Sort; A* Algorithm; Evolutionary Algorithms
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
