Vsevolod Domkin - Programming Algorithms

This book started after teaching an intensive course on algorithms to working programmers in Kyiv, in spring 2016. It took more than 3 years to complete, and, meanwhile, I also did 3 iterations of the course. Its aim is to systematically explain how to write efficient programs and, also, the approaches and tools for determining why the program isnt efficient enough. In the process, it will teach you some Lisp and show in action the technics of algorithmic development. And, even if you wont program in Lisp afterwards, youll still be able to utilize the same approaches and tools, or be inclined to ask why they arent available in your language of choice, from its authors :)

In our industry, currently, there seems to prevail a certain misunderstanding of the importance of algorithms for the working programmer. Theres often a disconnect between the algorithmic questions posed at the job interviews and the everyday essence of the same job. Thats why opinions are voiced that you, actually, dont have to know CS to be successful in the software developers job. Thats true, you dont, but youd better do if you want to be in the notorious top 10% programmers. For several reasons. One is that, actually, you can find room for algorithms almost at every corner of your work provided you are aware of their existence. To put it simply, the fact that you dont know a more efficient or elegant solution to a particular programming problem doesnt make your code less crappy. The current trend in software development is that, although the hardware becomes more performant, the software becomes slower faster. There are two reasons for that, in my humble opinion:

1. Most of the application programmers dont know the inner workings of the underlying platforms. And the number of platform layers keeps increasing.
2. Most of the programmers also dont know enough algorithms and algorithmic development technics to squeeze the most from their code. And often this means a loss of one or more orders of magnitude of performance.

In the book, Ill address, primarily, the second issue but will also try to touch on the first whenever possible.

Besides, learning the art of solving difficult algorithmic problems trains the brain and makes it more apt to solving various other problems, in the course of your day-to-day work.

Finally, you will be speaking the same lingua franca as other advanced programmers the tongue that transcends the mundane differences of particular programming languages. And youll gain a more detached view of those differences, freeing your mind from the dictate of a particular set of choices exhibiting in any one of them.

One of the reasons for this gap of understanding of the value of algorithms, probably, originates from how they are usually presented in the computer science curriculum. First, it is often done in a rather theoretical or mathematical way with rigorous proofs and lack of connection to the real world. Second, the audience is usually freshmen or sophomores who dont have a lot of practical programming experience and thus cant appreciate and relate how this knowledge may be applied to their own programming challenges (because they didnt have those yet) rather, most of them are still at the level of struggling to learn well their first programming language and, in their understanding of computing, are very much tied to its choices and idiosyncrasies.

In this book, the emphasis is made on the demonstration of the use of the described data structures and algorithms in various areas of computer programming. Moreover, I anticipate that the self-selected audience will comprise programmers with some experience in the field. This makes a significant difference in the set of topics that are relevant and how they can be conveyed. Another thing that helps a lot is when the programmer has a good command of more than one programming language, especially, if the languages are from different paradigms: static and dynamic, object-oriented and functional. These factors allow bridging the gap between theoretical algorithms and practical coding, making the topic accessible, interesting, and inspiring.

This is one answer to a possible question: why write another book on algorithms? Indeed, there are several good textbooks and online courses on the topic, of which Id recommend the most Steven Skiennas The Algorithm Design Manual. Yet, as I said, this book is not at all academic in presentation of the material, which is a norm for other textbooks. Except for simple arithmetic, it contains almost no math or proofs. And, although proper attention is devoted to algorithm complexity, it doesnt deal with theories of complexity or computation and similar scientific topics. Besides, all the algorithms and data structures come with some example practical use cases. Last, but not least, theres no book on algorithms in Lisp, and, in my opinion, its a great topic to introduce the language. The next chapter will provide a crash course to grasp the basic ideas, and then well discuss various Lisp programming approaches alongside the algorithms they will be used to implement.

This is an introductory book, not a bible of algorithms. It will draw a comprehensive picture and cover all topics necessary for further advancement of your algorithms knowledge. However, it wont go too deep into the advanced topics, such as persistent or probabilistic data structures, advanced tree, graph, and optimization algorithms, as well as algorithms for particular fields, such as Machine Learning, Cryptography or Computational Geometry. All of those fields require (and usually have) separate books of their own.

For a long time, Ive been contemplating writing an introductory book on Lisp, but something didnt add up, I couldnt see the coherent picture, in my mind. And then I got a chance to teach algorithms with Lisp. From my point of view, its a perfect fit for demonstrating data structures and algorithms (with a caveat that students should be willing to learn it), while discussing the practical aspects of those algorithms allows to explain the language naturally. At the same time, this topic requires almost no endeavor into the adjacent areas of programming, such as architecture and program design, integration with other systems, user interface, and use of advanced language features, such as types or macros. And that is great because those topics are overkill for an introductory text and they are also addressed nicely and in great detail elsewhere (see Practical Common Lisp and ANSI Common Lisp).