The discrete mathematics book industry is flourishing. The increasing demand for discrete mathematics courses for computer scientists and others has led to the publication of an increasing number of texts for these courses in the past couple of years. The book under review is one of the most recent; it has many virtues and only a few defects.

The authors cover a fairly standard set of topics for a two-semester sequence. These include introductory material on sets, functions, and relations (although rather more on each of these topics than is often found in such books). Then there are chapters on basic combinatorics, graphs, trees, logic (two chapters), and matrices. The only somewhat standard topic missing is difference equations. Then there are several chapters on topics from abstract algebra, including semigroups, Boolean algebras, and general algebraic systems. The authors admit there is more abstract algebra than necessary for undergraduates in computer science, but justify it on the basis that computer science will in the future require more and more of this material. I agree, but suspect that much of this material was included because the authors like it and feel comfortable with it. My own belief is that the lack of mathematical sophistication with which most students come to college today suggests that abstract algebra is best relegated to the fairly standard junior level course because most if it will be lost on and/or bore lower division undergraduates.

This brings us to the question of what level audience this book is aimed at. The authors say that they have taught the material to “average students at the level of beginning calculus.” This ambiguous phrase probably implies that at the University of Oregon, where the authors teach, only some freshmen (probably fewer and fewer each year) are ready for calculus; therefore, it is often sophomores and maybe even juniors who would take a course from this book. In any case, this book is appropriate for students taking their first course in college mathematics. But average students won’t find it easy. The considerable emphasis on abstract mathematics and the significant number of fairly difficult theorems, proofs, and examples means that students will tend to find the book hard and demanding (a good thing, I think).

Among the virtues of this book are the following:

• There is more emphasis on algorithms than is often found in such books, although most of the algorithms are just in the two chapters on Graphs and Trees. The need to verify algorithms is also recognized (but there is regrettably little on the analysis of algorithms).

• There is a more successful effort than usual to introduce topics in computer science in nontrivial ways. Much of this relates to theoretical computer science (e.g., formal languages), but there are also nice sections on Polish notation and the use of Boolean algebra in logic design.

• There are many examples illustrating the mathematics. Most of these are inevitably pure mathematical examples, rather than practical applications, but they are well done.

• There are many good problems; hints and answers are given to the odd-numbered ones at the back of the book.

• The writing is good; the presentations are clear and informal; and the book seems very free of errors.

The graph theory chapter provides one clear example of this. In a curious section early in this chapter, considerable space is devoted to finding the path of minimum weight between two vertices in a weighted digraph (assuming one already knows what the minimum weight itself is). While there are many applications in which the computation of minimum weight paths is important, such computation is always the byproduct of finding the minimum weight. Indeed, the authors implicitly recognize this in a later section of the chapter where they discuss some algorithms for computing shortest paths. But here, alas, they focus on algorithms to find the shortest path between all pairs of vertices. They also present Dijkstra’s algorithm to find the shortest path between a pair of vertices [1], but only in passing and so cursorily that few instructors, much less readers, will understand it. Unfortunately, none of the shortest path algorithms are analyzed at all.

Another example occurs in the discussion of minimum spanning tree algorithms, in which the assumption is made that the edges are ordered according to their length. Fair enough, perhaps, for a mathematician, but computer scientists need to be taught that O(n log n) processes are to be eschewed when there are algorithms which only require the shortest edge to be found initially (an O(n) process).

All this really means is that discrete mathematics books will have to evolve over the next decade or so until an approach satisfactory to both mathematicians and computer scientists is found. In the meantime this book should certainly be considered by anyone wishing to teach a serious course in discrete mathematics.