Let me start with the winner. For the past couple of years I have been using the textbook written by Dasgupta, Papadimitriou and Vazirani. Here is what I think of it.

-Its first quality is that it is softcover and therefore relatively inexpensive. Some preliminary version is available for free on the authors' web pages.

-Its second quality is that it is relatively small and therefore light to carry around.

-Its third quality is that it is written in good English. The style is crisp, and the authors occasionally inject emotions in their descriptions, giving more texture to the book. "

*Now the time has come to meet the quest’s most embarrassing and persistent failures.*"

-Its fourth quality is that for each problem, the textbook goes straight to the heart of the difficulty. It does not waste space on secondary notes, avoids redundancy, and gives the gist of an argument in just a few lines. The proofs are often beautiful because they are direct and minimal, with no unnecessary detours. They are a pleasure to read.

-Its fifth quality is that it is short enough that a student could aim to read it in its entirety.

However, the book is not perfect.

-Its first fault is that it contains mistakes. The authors obviously did not implement their algorithms. Special cases may be overlooked in the problem specifications. Base cases may be done in a hurry, or barely mentioned when they contain nothing of interest. Calculations can be slightly off where the constants are concerned. The authors are keen on communicating the central ideas, but there is a certain carelessness about details. In that sense, the presentation is not up to the standards that we expect from our own students.

-Its second fault is a lack of examples. For me, designing algorithms is first done by working through examples, and a student who wishes to study the course material has to supplement the book with more examples. In that case, the tradeoff between size of book and content comes out in favor of examples, in my opinion.

-Its third fault is the choice of topics with which to start the book: the first chapter talks about arithmetic operations. That's natural because students learned algorithms for those at a young age, but that immediately raises problems that should be swept under the carpet until much later: when we talk about an input of size n, what is n? Starting by numbers creates problems that spoil the beginning of the semester: when we sort by comparisons, why do we assume that comparing two numbers can be done in constant time? What if the numbers are really large? Those concerns are valid, but they should come up at the end of the semester, when the student is comfortable with runtime analysis and ready to revisit his assumptions. This textbook's approach naturally leads students to raise those questions early on, and at that stage they only create confusion.

-Its fourth fault is a lack of exercises. There are not enough exercises for students to practice what they are learning.

-Its fifth fault is the choice of topics to be covered, that does not correspond one hundred per cent to my own taste; it is more of a reflection of the authors' tastes; however that is natural for any book.

Overall, I like this book very much. It is the one that comes closest to my taste. A cleaned up and slightly expanded version of that book would be ideal for me.

I won't use a textbook that doesn't let me spend a few lectures on computational geometry — just as it's important to cover the basic algorithm design paradigms (divide and conquer, dynamic programming, prune and search, etc) I think it's also important to cover the basic types of algorithmic problem (algorithms on sets and sequences, algorithms on graphs, algorithms on strings, algorithms on numbers, algorithms on geometric data, etc). That rules out the one you mention, which from what I can tell has no geometry.

ReplyDeleteIn recent years I've been using the one by Goodrich and Tamassia (full disclosure: Goodrich is in my department).

The most important thing is that the book is available online for free. It is outrageous that people think that students should pay 70$ (or more) for a book, considering how expensive the tuition is. In any case, a book is just another resource - I do not follow any book too closely.

ReplyDelete--Sariel

What's a textbook?

ReplyDeleteJeffe: right.

ReplyDeleteThat's why I want cheap (or free) textbooks.

This is a transition. I'm not sure what students will use next, but they do need textbooks to some extent still now, to avoid relying exclusively on the instructor and on random searches on the internet.

I use Kleinberg and Tardos. I like its approach to covering topics by technique rather than application domain, and it has lots of good problems which cover many domains (including the ones mentioned by D. Eppstein above). I like that way of doing things: all these algorithmic techniques are similar, and can be applied to a diverse set of circumstances. I also appreciate its end-run around some of the technical parts of the Cook-Levin theorem.

ReplyDeleteI dislike its price, and I quibble with how some things are presented, but overall I like its contents a lot, and prefer it to CLRS.

Actually, the Dasgupta-Papadimitriou-Vazirani textbook is also organized by techniques, and I agree that it is a nice way to order material.

ReplyDeleteDavid E.,

ReplyDeleteI have almost given up on teaching computational geometry algorithms. My attempts have been largely mediocre, because

(1) Without any assumed background on any basic geometric primitive, I find that the details are messy, and

(2) I have many colleagues who like to incorporate computational geometry examples in their courses, so whatever I teach is likely to have been seen already by some fraction of the class.

In addition, there is a course, occasionally taught, that is exclusively on computational geometry.