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

* Author:* Vsevolod Domkin

* Publisher:* Apress

* Year:* 2021

It is only about 5 months since I read and * reviewed* a good book on

*written by*

**Lisp***. The present book is by*

**Michał “phoe” Herda***and I purchased it two weeks ago. Coincidentally,*

**Vsevolod Domkin***is the technical reviewer for this book.*

**Michał**In * Chapter 1*, the author starts off by touching upon about why algorithms are important, and why he chose

*as the language for describing algorithms in this book. While I might not agree with him as to why another language such as C++ or Java could not have been chosen, the fact remains that there is no other book that focusses on Algorithms in*

**Lisp***, and in that sense, this book is welcome indeed.*

**Lisp*** Chapter 2* touches upon the notion of algorithmic complexity. There is a good chance that readers of this book will already have a practical understanding of complexity theory, so this chapter can be conveniently skipped.

* Chapter 3* is a 28-page crash course in

*. It is meant for those who have no background in the language so that they can understand the algorithms discussed in the subsequent chapters. The coverage is decent, but cannot be a substitute for a good book on*

**Lisp***basics. You can check this*

**Lisp***for my personal recommendation for learning*

**article***. The author makes a reference to his*

**Lisp***, which he uses in many places in his Lisp code, and shows how it can be imported into the*

**RUTILS****library***environment. One thing I noticed is that the section on*

**Lisp***does not mention the multiline comment enclosed within*

**“Comments”***and*

**#|***.*

**|#*** Chapter 4* talks about the importance of

*and*

**Data structures***. The author tries to drive home the point that choosing a good data structure is quite important as it lends itself automatically to an efficient algorithm. In passing, he also differentiates between*

**Algorithms***and*

**call-by-value***in the context of passing a data structure as a function parameter. He concludes by implementing an efficient*

**call-by-reference***algorithm.*

**Union-Find*** Chapter 5* is the beginning of the discussion of various data structures. The most common of data structures is arrays, so this chapter delves into

*, both fixed size and dynamic. Readers will find the discussion on*

**Arrays/Vectors***Interesting and informative. This chapter also discusses*

**“Why are arrays indexed from 0?”***and*

**Searching***algorithms and concludes with a performance comparison of three sorting algorithms.*

**Sorting**As a natural progression, the next chapter is on * Linked lists*. List being the fundamental data structure in

*, it is widely used in day-to-day development.*

**Lisp***covers Lists in detail, including how to use them as*

**Chapter 6***, and explains the*

**Sets***sort algorithm as applied to lists. Towards the end, the author presents a parallel version*

**Merge***sort using the*

**Merge***library.*

**Eager Future 2**The next chapter is on * Key-Values* and the author presents interesting ideas on using

*data structure for*

**KV***, a technique often used to speed up algorithms.*

**memoization*** Chapter 8* provides a detailed look at

*– how they can be implemented, importance of hash functions, and the common operations on hash tables. The section on*

**Hash Tables***, including the*

**Perfect Hashing***algorithm is an interesting read.*

**CHM92**In * Chapter 9*, the author covers the ubiquitous

*data structure. Different types of Trees namely,*

**Tree***,*

**Binary Search Tree***,*

**Splay Tree***,*

**Red-Black Tree***,*

**AVL Tree****, and even**

*B-Tree**and*

**Heaps***are all covered. The chapter ends with a brief discussion of the application of*

**Tries***for storing*

**Trees***data.*

**Spatial**The next chapter is about * Graphs*. Here too, the author takes care to cover the essentials of representing graphs and different algorithms, including

*sorting,*

**Topological***and*

**Minimum Spanning Tree (Kruskal, Prim)***and*

**Path finding algorithms (Dijkstra, A*)***. The last section is a*

**Maximum Flow***algorithm implementation. Quite a decent coverage, I must say.*

**Page Rank*** Chapter 11* is about

*and String-related algorithms:*

**Strings***and*

**Substring search (Knuth-Morris-Pratt, Boyer-Moore, Robin-Karp, and Aho-Corasick)***. As a practical application of String search, there is brief discussion on*

**Regular Expressions (Thompson’s construction)***.*

**Plagiarism****detection*** Chapter 12* is on

*. It begins with a simple example of*

**Dynamic Programming***in the context of*

**memoization***sequence computation and moves on to*

**Fibonacci***and*

**String segmentation***. The chapter concludes by showing how*

**Text justification***can be viewed as a DP problem.*

**Back Propagation**In * Chapter 13*, the author talks about

*that are used for calculations aimed at an*

**approximation algorithms***result within certain constraints (usually time).*

**“acceptable”***and*

**Local search, Genetic algorithms, Branch and Bound, Gradient Descent,***are discussed in some detail. The last section touches upon*

**Singular Value Decomposition***and how it is effectively used in compression formats such as*

**Fourier transform***.*

**JPEG*** Chapter 14* is entirely devoted too

*. Starting with the concept of*

**Compression***, the author moves on to*

**Encoding***compression using*

**Lossless***and shows an example of its use in compressing and storing a large dictionary. There is also a brief discussion of the*

**Huffman coding***algorithm.*

**Deflate**The last chapter, * Chapter 15*, is about

*. After talking about low-level synchronisation primitives such as*

**Synchronization***, the discussion moves on to*

**Compare and Swap***algorithms,*

**Mutual exclusion***and*

**Lock-free data structures,***. The last section in this chapter gives an overview of*

**Distributed algorithms***.*

**Persistent data structures**That is a lot of complex topics bundled into a single book!

Who will benefit from this book? I do not expect programmers who are not familiar with * Lisp* to start reading this book, although there is a chapter that introduces

*. People who want to learn*

**Lisp***will most probably start with a book such as*

**Lisp***[2] or*

**Peter Seibel’s “ Practical Common Lisp“***[3]. You may also want to go through my detailed*

**Peter Norvig’s “Paradigms of Artificial Intelligence Programming”***. In my opinion, this book will primarily help programmers who are familiar with*

**recommendation***to some extent and who are looking for material focussed on data structures and algorithms.*

**Lisp**Possible improvements? Firstly, I feel that the author could have included pseudocode for the various algorithms (at least the major ones) before giving the * Lisp* implementation. The book by

*[1] is a great example of how this can be done. This would have increased the size of the book, but it would have certainly enhanced its value. Secondly, the author could have included a brief chapter (preferably after Chapter 2) explaining the different constructs from his*

**Jason Brownlee***library, which he has used in the*

**RUTILS***code. This would help those who have not looked at this library before, although an experienced*

**Lisp***developer can understand what is going on.*

**Lisp**Minor limitations aside, this is a book worth having in your * Lisp* library. As far as I can recall, there is no single book on

*that covers various data structures and algorithms in such detail. I sincerely appreciate the author’s dedication and hard work.*

**Lisp**Have a nice week!

### Reference

[1]. Jason Brownlee, Clever Algorithms: Nature-Inspired Programming Recipes, 2012.

[2]. Peter Siebel, Practical Common Lisp, Apress, 2005.

[3]. Peter Nerving, Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp, Morgan Kaufmann,1992.

Thanks for the thorough review and suggestions!