Programming Algorithms in Lisp [electronic resource] : Writing Efficient Programs with Examples in ANSI Common Lisp

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. 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