Dear Jeff:

Here is a first review of your manuscript for you to mull over.  The
choice of "good huge book" or "small excellent book" is really up to you.  The
huge book (or largish, anyway) would be more in line with what people are
used to teaching out of, so in that sense would compete better with CLR
and other such books -- and if it caught on could really make a lot of
money for all concerned.  But it would be a lot of work and something of a
gamble.  It sounds as if the smaller book you already have planned could have
a solid market, mostly as a supplementary text, as long as it weren't too
expensive (I would go for a $25-30 paperback).  In either case, it's
clear you've identified the right area of dissatisfaction with the current
texts. 

I do suggest you consider the reviewer's suggestion about adding at least
some discussion of data structures.   

I'm expecting a couple more reviews by early August and will forward them
as they come in.  

Best regards,
Lauren

Lauren Cowles
Cambridge University Press
*********************
Reader A

Jeff Edmonds.  Thinking About Algorithms Abstractly.

This is a very good set of notes and I think that with enough effort
it could be turned into a very good textbook.  I have some concerns
about how well it could compete with less well-presented but more
comprehensive texts already available.

Here's what I like about the manuscript:

1. It has the best presentation I've ever seen of how people who build
algorithms think about them.  Unlike many algorithms books (e.g.
Sedgewick's various textbooks, CLR) that are organized around a large
collection of finished algorithms, Edmonds's manuscript concentrates on
general algorithm design techniques and brings in specific algorithms
only as examples of these general techniques.  Edmonds is also not
afraid to give examples of when techniques don't work, and when some
techniques do work but not as well as they can with additional tweaking,
or as well as some other technique might.  The difference is a bit like
the difference between studying carpentry by looking at houses and by
looking at hammers.

2. Correctness proofs are handled very well.  The manuscript manages
to avoid both fanatical formalism and the approach formalism often
encourages of sweeping correctness under the rug because it's too hard
to deal with.  By emphasizing the structure of correctness arguments
and using explicit invariants, the manuscript again does a good job of
presenting how real algorithm designers think.

3. Complexity of algorithms is handled well, emphasizing how complexity
computations interact with the design and structure of algorithms over
brute calculation itself.  I particularly like the ``Adding Made Easy''
theorems, although it would be nice to have a proof and a better (and
more strongly emphasized) description of what range of functions they
work for.

4. The description of dynamic programming in particular is very
thorough.  If the rest of the book can be brought up to this level of
detail it will be very strong.

5. Though I can't evaluate the missing chapters, I like the fact that
the author plans to cover linear programming and amortization.

6. The author is a strong researcher in the area and it's clear that
he brings all of his knowledge of current work to writing the notes---
for example, the comment that algorithms researcher have only recently
managed to prove superlinear lower bounds is based on new work from last
year.  I am confident that he would continue to bring this very fresh
perspective to a longer textbook.


Here's what I worry about when reading the manuscript:

1. The main competition for this book is going to be encyclopedic
algorithms tomes like CLR or Sedgewick's new multi-volume series.
Though I like the approach of the manuscript better than the approach of
these other books, an issue for the students is how good a toolbox the
book will give them.  I suspect that a typical CS student reads exactly
one algorithms textbook in her life, and if that book is missing some
topic, she'll never learn about it.  So while this book will likely do a
great job of teaching people to invent wheels, it may not do a very good
job of pointing to pre-invented wheels.

I don't want the book to turn into another cookbook, since we already
have enough of those.  But I think it would be handy if in addition
to the chapters already described in the table of contents there were
a few chapters at the end on application of existing algorithms.  One
example of a such a chapter might be a chapter on solving problems using
graph algorithms.  This could look at the questions of how to pull a
graph out of a problem that at first glance doesn't look like a graph
problem, how to translate the problem into one one has seen before,
how to recognize NP-hard graph problems, and so forth.  I'd imagine
that most of the algorithms that would be used here (e.g. shortest
paths, minimum spanning tree, network flows and cuts) would have been
presented earlier, but it would still be useful to bring them together
with some examples of how one attacks a problem that may be vulnerable
to many known tools.  Similarly, a chapter specifically on combinatorial
optimization problems could do the same sort of pulling-together for
network-flows, linear programming, dynamic programming, and some of the
NP-hardness results.

There are also areas of algorithm design that at the moment aren't
touched on (and possibly shouldn't be).  The biggest area missing is
probably parallel algorithms.  It's not clear how well a section on
parallel algorithms could be fit in with the rest, but it might be worth
putting something in.

2. The manuscript appears to make fairly strong assumptions about the
background of students coming into the course.  This makes sense for
course notes, since the author knows what the prerequisites are for
SC/COSC 3101 and can adjust his material to match.  But if the book is
to be used elsewhere there are some gaps that may need to be filled in.

One glaring hole is that the manuscript doesn't talk about data
structures much as an explicit topic.  I assume that the students taking
the author's course have had a fairly thorough data structures course
before.  However it may be limiting to leave data structures out,
especially since (a) a student coming to this book may not have seen
much algorithm treatment of data structures (analysis of performance and
correctness), even if he's had a here's-where-to-put-the-pointers course
before; and (b) designing an algorithm to use a data structure well
would fit so well at the end of the section on iterative algorithms--- a
data structure is just the knight in armor that defends and preserves a
complicated invariant that the algorithm needs to keep going.

On the other side, the manuscript appears to assume that the students
don't have much discrete math background.  I noticed for example that
it scrupulously avoids algorithms based on finite fields and similar
mathematical tools.  This is not necessarily a problem, since many
students don't bring these tools to their first algorithms course,
and the basic idea of algorithm design can be lost if one is trying
to prove that some value is or isn't a quadratic residue, but it does
exclude pretty much anything about cryptography and related topics like
pseudorandom generators and the design of hash functions.

3. The litany of friends, little birds, higher powers, and so forth
sometimes comes off as a little twee.  This isn't necessarily a problem,
but there is a danger with adopting user-friendly jargon that it just
becomes more jargon, incompatible with what everybody else uses--- and
after the first few times you hear it there isn't really all that much
difference between friend and subroutine.


Finally, the big question: would I adopt this book?  It's hard to say.
I'm currently using CLR, which though a bit dated and clearly not as
well presented as the manuscript has the advantage of being relatively
comprehensive.  I could certainly imagine adopting something similar to
the current version (with some fleshing out in the missing chapters of
course) as a supplement to a book like CLR, since I think it does a much
better job of presenting what it covers, but I'd be leery of replacing
CLR with it outright unless it covers much more ground than it does
now.  I have great confidence that the author could produce a good huge
book, so I suppose the question is whether he would rather stick with
an excellent small one, and whether that excellent small book would
be excellent enough to use on its own even if it means leaving some
material out of the course.