Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Mathematics of discrete structures for computer science
Pace G., Springer Publishing Company, Incorporated, New York, NY, 2012. 309 pp. Type: Book (978-3-642298-39-4)
Date Reviewed: Dec 18 2012

I thought this would be a good discrete mathematics text for an undergraduate computer science course, but I was wrong! The standard topics--including propositional logic, predicate calculus, sets, relations, discrete structures, defining new structured types, numbers, and reasoning about programs--are covered with mild rigor, but proofs of consistency and completeness are omitted.

As such, the book is suitable for students who understand algebra and can program. It fits with traditional chalk-and-talk pedagogy, and uses both natural deduction and calculational style proofs [1]. It uses the set comprehension notation from the language Z and promoted by David Gries. There are other texts that cover this material; for example, Gries and Schneider [1] have authored another rigorous and logical derivation of the same ideas (in a different sequence, with different steps in most proofs). Donald Knuth promoted Concrete mathematics [2] as the mathematics needed to compare algorithms and data structures. This is less focused on the logic of discrete mathematics than on combinatorics. A fun text, Discrete mathematics with ducks [3], includes most of the material in this book by Pace, but with combinatorics and probability. Teachers who use this text have noted how enthusiastically their students discuss its ideas in class. I liked the formal logic and the computer science examples. My favorite section is 2.7.4, “Not All Proofs Are Equal.”

Overall, the book is well made. However, there are some issues: chapter 8 needs debugging; the ML style type definitions can lead to inconsistencies (their syntax must be changed to forbid the recursive definitions that, by Cantor’s theorem and Dana Scott’s work [4], define types that cannot exist); and citations, history, references, and a bibliography are absent, making it difficult to trace the sources for notations and proofs. (Mostly, they seem to have come from the Programming Research Group at Oxford University in the 1970s.)

Reviewer:  Richard Botting Review #: CR140756 (1303-0183)
1) Gries, D.; Schneider, F. B. A logical approach to discrete mathematics. Springer Verlag, New York, NY, 1993.
2) Graham, R. L.; Knuth, D. E.; Patashnik, O. Concrete Mathematics: A foundation for Computer Sciences. Addison-Wesley, Boston, MA, 1994.
3) Belcastro, S.-M. Discrete mathematics with ducks. A K Peters Ltd., Boca Raton, Florida, 2012.
4) Scott, D. Turing Award lectures: the first twenty years 1966-1985. ACM Press, Addison Wesley, New York, NY, 1987.
Bookmark and Share
  Featured Reviewer  
 
Computations On Discrete Structures (F.2.2 ... )
 
 
Formal Definitions And Theory (D.3.1 )
 
 
General (G.2.0 )
 
Would you recommend this review?
yes
no
Other reviews under "Computations On Discrete Structures": Date
The performance of algorithms for colouring planar graphs
Williams M., Milne K. The Computer Journal 27(2): 165-170, 1984. Type: Article
May 1 1985
A separator theorem for graphs of bounded genus
Gilbert J., Hutchinson J., Tarjan R. (ed) Journal of Algorithms 5(3): 391-407, 1984. Type: Article
May 1 1985
On the computational complexity of path cover problems
Ntafos S., Gonzalez T. Journal of Computer and System Sciences 29(2): 225-242, 1984. Type: Article
Jun 1 1986
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy