Slashdot Mirror
Mastering Algorithms with C
There are many books on programming algorithms, and quite a few of them use C for their examples, but even so, I was looking forward to this new book from O'Reilly.
Most of the existing algorithm books were designed as college text books. While they have their place, there is certainly room for a book that approaches the subject matter in the informal, clear writing style and practical focus that is O'Reilly's trademark. Unfortunately, for me at least, Mastering Algorithms in C was not that book.
My Problem with Algorithms One of O'Reilly's strengths has always been their attention to the structure of their books. O'Reilly books are usually well designed, with logical and reader-friendly layouts. But Mastering Algorithms with C has a layout that I found somewhat vexing.
The chapter on linked lists serves to illustrate. An introductory section describes three kinds of lists, then briefly describes several applications for them (mailing lists, memory management, scrolled lists in GUIs, etc.). This is followed by a brief section describing the basic concepts of linked lists.
>From there the chapter moves directly to an implementation of linked lists, starting with a section called "Interface for Linked Lists". This section enumerates each function in a linked list library. For each function we are given its function prototype, followed by its return value, a brief description of the function's purpose, and finally, its algorithmic complexity in O-notation.
The next section is called "Implementation and Analysis of Linked Lists". After a paragraph describing some data structures, we are presented with a listing of the C header file, list.h, followed by a lengthier description of each of the functions described in the previous section. Finally, we are presented with a code listing of list.c.
And this is where I started having a problem.
First, I feel the author plunges much too quickly into implementation before providing a proper context. Let's assume that the reader knows nothing about linked lists (that's why, after all, they bought the book). Before describing a specific implementation, shouldn't the reader be clued in on the basic operations (independent of the implementation language) performed on linked lists: adding a node, deleting a node, etc.? While a little of this is given early on, the author seems in a rush to move on to the implementation.
And when we have the implementation described, the information is
spread across (at least) three locations. For example, the
function list_ins_next is first introduced in the "Interface"
section, its prototype is shown in the list.h file, a more
detailed description is provided in the "Implementation" section,
and finally the actual code is presented in the list.c code
listing. This forces the reader to jump around quite a bit to get
all the info about each function.
How Much Should the Reader Know? How much should the writer assume you know about linked lists (or any of the other algorithms described in this book)? If the reader already understands the basic concepts of linked lists, and if they're already a C programmer, they most likely wouldn't need this book. So let's assume the reader is starting at ground zero (or its general vicinity) when it comes to linked lists.
If that's the case, then I would expect the writer to present a relatively "bare bones" implementation, at least for basic algorithms like lists.
Instead, what is presented is an almost object-oriented implementation with init and destroy functions, function pointers, and other details that may provide a clean implementation but may be an impediment to the authors primary duty: teaching the reader the algorithm.
For much the same reasons, I found many of the examples out of sync with what was being taught. While virtual memory paging schemes are a lot of fun, they're a hell of a thing to spring on some poor sucker trying to grasp the concept of linked lists.
Finally, I had some problems with the author's prose style. This may be more my preconception of how an O'Reilly book should read. Luckily, you can (and should) make your own decision. O'Reilly has Chapter 13, Numerical Methods, available at their web site.
But Wait While I have problems with this book, I don't mean to imply the book is bad. It's a fair book, I just don't think it's great book. It covers a lot of territory. For me, its main fault is that it fails to explain concepts clearly and basically enough before diving into the code.
On the plus side, I found the figures that illustrate concepts throughout the book to be clear and helpful. The selection of which algorithms to cover is also quite good, as these are all areas that a wide variety of programmers will face at some point in their work.
If you already have a moderate understanding of the algorithms, and want a text that presents a clear and documented implementation of them, then you may want to consider this book.
Pick this book up at Amazon.
Table of Contents:
Preface
- Preliminaries
- Introduction
- Pointer Manipulation
- Recursion
- Analysis of Algorithms
- Data Structures
- Linked Lists
- Stacks and Queues
- Sets
- Hash Tables
- Trees
- Heaps and Priority Queues
- Graphs
- Algorithms
- Sorting and Searching
- Numerical Methods
- Data Compression
- Data Encryption
- Graph Algorithms
- Geometric Algorithms
Are there any insightfull ideas or algorithms discussed in this book? What topics are covered and how well? Is this book simply a rehashing of a college algorithms class, or does it discuss issues about implementation complexity and efficency? Is the process of algorithm construction addressed by the book?
I picked up The Practice of Programming a while ago, and have found it to be an interesting treatise on the major problems and solutions in programming. If this book is anything like it I might consider reading it, but this review gave me little insight.
--Tom
For C/C++ books, I'm afraid Addison-Wesley kicks O'Reilley's ass every time. That's okay, though... O'Reilley has great books in their catalog, and I'm happy to purchase from either.
So for C/C++, be sure to get "The C Programming Language (Second edition)" and "The C++ Programming Language (Third edition)."
For algorithms, I'd recommend Cormen et al "Introduction to Algorithms". It's *not* an intro, it's a 1000+ page behemoth textbook, very thorough. We used it in university, covering half the material. We also had more specialised texts on numerical methods, etc. Most of these books are available on Dr. Dobb's CDROMs, check their web site.
Also, I have the Knuths and have read some of them. While that's clearly beyond the average programmer, I have to say I find his wit, style, and attention to detail inspiring.
Of course, if you just want to *use* algorithms, you use the C++ standard template library, or whatever. I've heard numerical recipes has some problems and bugs.
--
Marc A. Lepage
Software Developer
My recommendation is Algorithms in C by Robert Sedgewick. It's one of the classic texts of the field. I think its a good text for a motivated beginner to learn algorithsm and some data structures. It's not as watered down as a lot of intro texts. But it's not as overwhelming as Knuth or something like that. Plus the examples are written in C, if not particularly readable C. (Be careful, there is another edition that does not use C. Buyer beware).
This is a very well-written text with clear and detailed explanations. The pseudocode takes a bit of getting used to, but I like the fact the the algorithms are presented in a language-neutral fashion. This is the book that helped me understand alorithms, O notation and the tradeoffs between data structures.
Plus, it's a big book and covers pretty much everything your average hacker would ever want, and more.
--
I haven't read the book being reviewed here, but if anyone is interested in a very exhaustive introductory algorithms book, I'd recommend Introduction to Algorithms from the MIT Electrical Engineering and Computer Science series. very very intelligent treatment of any algorithm-related subject you would want to read about.
here it is at Amazon
Hmmmm ... looking at the chapter, I'd say that it's a bit lightweight. You don't need to be a maths purist to think that it's a bit poor to teach people to do least-squares estimation without calculating the standard errors as they go. Or at least without even mentioning that there are such things as standard errors.
...
And polynomial interpretation is only useful when you have a very good idea of what the data's going to give you -- it can go very badly wrong otherwise. For a small step-up in complexity, they could have covered cubic splines, which are much more generally useful.
Numerical Recipes, now there was a book
jsm
If you're looking for an algorithm book, have a look at:
m
Algorithms and Data Structures in C++
Author: Ammeraal, Leendert
Publisher: Wiley
ISBN: 0471963550
Price:£ 29.95
I've got the C version of this and it was worth looking at.
Algorithms in C++
Author: Sedgewick, Robert
Publisher: Addison-Wesley
ISBN: 0201510596
Price:£ 32.99
I've got the older version of this and it was worth looking at.
You can get other peoples opinions from ACCU's book reviews:
http://www.accu.org/bookreviews/public/index.ht
There are several problems with Numerical Recipes. Don't take my word for it; see what the people at NASA's Jet Propulsion Lab have to say: http://math.jpl.nasa.gov/nr/ They also list several alternatives.
Introduction to Algorithms by Cormen, Leiserson, and Rivest, MIT Press
Numerical Recipes in (various languages) by Press et al., Cambridge University Press
The main difficulty with the Cormen textbook is that it is too analytical for a lot of people. You really do need the math in the first part of the book to understand the rest of it (so it's your fault if you skip those chapters). Also, I hate red-black trees; AVL trees are simpler to understand, simpler to implement, and perform about as well. Otherwise, very nice pseudocode and analysis.
The Knuth books are classic, but the choice of MIX for programming is dreadful.
For numerical algorithms, the Numerical Recipes books are superb. I wish the style of analysis in the Cormen book was more like this.
After reading this review I'd like to clarify one thing. A linked list is not an algorithm, it is an abstract data type. The algorithm part is the description on how operations on the list are carried out.
For those interested in the subject I'd recommend "Data Structures & Their Algorithms" by Harry R. Lewis and Larry Denenberg. It may not be very well suited for the novice programmer as the content is rather mathematical and abstract but it discusses algorithmic complexity to some degree. It also contains implementations for important algorithms in pseudo-code.
Just my 0.02 sek
I third that. (someone already seconded it ;)
Cormen's book lacks some not so often found data structures (skewed heaps, tries, leftist heaps, and splay trees for instance). It has a fairly good treatment on miscellaneous well-known algorithms (FFT, RSA, string matching, ...)
I'm about to get my M.Sc. in Computer Science and I haven't read TAOCP (it's a deep personal dishonor I have to live with, until I have the time to go through it). The CS degrees are too shallow nowadays, knowing how to program is almost enough. To get a decent all-round knowledge of the field I've had to read the old classics in my spare time, since _none_ of them are a part of the curriculum. The degrees are geared towards providing IT companies employees and IMO that is not what CS is all about. Ever notice the 'science' part in the name of the discipline ? That's why I'm studying for a Ph.D in CS. Anyway I wonder how TAOCP compares to this book.
AC