|Classic Computer Science Problems in Python|
Author: David Kopec
There are versions of this book in Swift and Java and I've already reviewed the Java version. This is very much the same book as the Java version, but in Python and there is nothing wrong with this. My only worry when I approached this book was that the author might be happier coding in Java than Python. This isn't an important consideration, however, because the code is reasonably Pythonic - so much so that some might not find it easy to follow. The biggest shock for many readers is the use of Python typing. Most Python programmers tend not to use typing and neither do most examples. The use of "optional" typing does make simple programs look more complicated and it possibly isn't a good choice for examples intended to illuminate algorithms rather than code.
The first thing to say is that some of the "classic" algorithms are very simple and they are even announced as "small problems" in Chapter 1. The first algorithm in the book is the Fibonacci sequence and this is implemented using recursion, which is a bit of a barrier to put at the very start of any book. Even so, as long as you don't lose confidence, it is easy enough. I'm not sure I'd call it a classic algorithm, however it is a very common example. The implementation is also elaborated to include memoization, which either is or isn't part of a classic algorithm depending on your point of view. Memoization is about efficiency and hence isn't really an issue if you are considering theoretical algorithms, but it is a basic technique to make almost anything go faster. I'd rather not see it introduced in this confusing position. After all this sophistication we have a final iterative version - perhaps this would be better presented first? The rest of the chapter details a simple encoding/decoding problem, calculating Pi using the easy, but slow to converge, series and the Towers of Hanoi problem. I don't really think any of these are classic algorithms in the computer science sense, but they are all commonly used as examples. If you are looking for some sort of connection or theme in this first chapter - there isn't one. The topics are just "small problems"
Chapter 2 is about search, which is a classic problem, but the solutions presented are the usual computer science approach of linear search, binary search and so on wrapped up in a problem involving searching DNA. From here we have depth first and breadth first search and A*.
Chapter 3 is about constraint satisfaction, which is not a mainstream "classical" problem, but we do meet the eight queens problem which is. This is essentially about backtracking search and the main example is solving word arithmetic problems.
Chapter 4 moves on to consider graph algorithms. Here we meet some classic algorithms - Minimum Spanning Tree and Dijkstra's algorithm. Chapter 5 is about genetic algorithms, which I do not think of as classic problems or even classic algorithms, interesting though they are. The same goes for Chapter 6 and the K-means clustering algorithm. As far as I'm concerned K-means is just one a set of possible clustering algorithms and more - this is, or used to be classical statistics and now might be put into the category of simple AI.
Chapter 7 continues with a look a neural networks and, for me, nothing could be further from a classic problem. It covers back-propagation and goes fairly deeply into basic neural networks. Chapter 8, called Adversarial Search, it is still more connected to AI than anything else. The examples are tic-tac-toe and Connect Four and the algorithms are mini-max and alpha-beta pruning. Classics of AI indeed.
The final "proper" chapter, Chapter 9, is on the knapsack problem and the travelling salesman problem, with a brief introduction to NP problems. Now this is classic computer science.
This book might well not be what some potential readers are expecting? I'm not sure that the selection of problems is what a majority of computer scientists would consider "classic", but this is a matter of opinion. There are a lot of AI-oriented algorithms included and this pulls the book's focus away from what many would consider mainstream Computer Science. The biggest omission is the sorting algorithms, which arguably are the starting point for all accounts of classical computer science algorithms - why no quicksort? Also there are no data structure algorithms - linked lists, stacks, trees etc. If you do want to stray from pure computer science then what about the Fast Fourier Transform? All good candidates for a classic problems book.
What all this means is that this book isn't going to be of much use to anyone hoping for some help with a computer science course. Its idea of classic algorithms is too patchy and too biased to be of much help. The introduction to the book does state very clearly that it isn't an academic tome covering big O analysis etc, but even so the choice of algorithms doesn't fit with its title.
Having said this the algorithms are that are described are well presented and it is a slim book and so you can't really expect it to cover everything. So the bottom line is that if the selection of problems interests you, then why not give it a try? What it does do is done well.
|Last Updated ( Saturday, 10 September 2022 )|