# Discrete Mathematics textbooks for undergraduates

For the first time, I will be teaching a course on Discrete Mathematics for electrical and computer undergraduates students.

I intend to focus on practical applications.

I would be grateful if people would suggest names of books/lecture notes on the subject. Thank you in advance!

• This should be community wiki – Stopple Aug 1 '12 at 15:08
• @Stopple: done! – Papiro Aug 1 '12 at 16:43

I like Concrete Mathematics by Graham, Knuth and Patashnik:

This book introduces the mathematics that supports advanced computer programming and the analysis of algorithms. The primary aim of its well-known authors is to provide a solid and relevant base of mathematical skills - the skills needed to solve complex problems, to evaluate horrendous sums, and to discover subtle patterns in data. It is an indispensable text and reference not only for computer scientists - the authors themselves rely heavily on it! - but for serious users of mathematics in virtually every discipline.

Concrete Mathematics is a blending of CONtinuous and disCRETE mathematics. "More concretely," the authors explain, "it is the controlled manipulation of mathematical formulas, using a collection of techniques for solving problems." The subject matter is primarily an expansion of the Mathematical Preliminaries section in Knuth's classic Art of Computer Programming, but the style of presentation is more leisurely, and individual topics are covered more deeply. Several new topics have been added, and the most significant ideas have been traced to their historical roots. The book includes more than 500 exercises, divided into six categories. Complete answers are provided for all exercises, except research problems, making the book particularly valuable for self-study.

• I love this book, but I don't think it is a good fit for the original request. Although it does very concrete problems, it doesn't try to do real life problems and, although the prerequisites are formally very small (just calculus and linear algebra, until the last chapter), it is written for people who are used to reading mathematics. – David E Speyer Aug 1 '12 at 15:42
• I agree- this is a great textbook for graduate students in computer science, but it is utterly unsuitable for the typical freshmen/sophomore level discrete math course for CS majors. – Brian Borchers Aug 1 '12 at 16:39
• @BrianBorchers I read Concrete Mathematics when I was in class 11 or 12 (i.e., before being an undergraduate), and loved it. Of course there were a few parts I didn't understand, but most of the book is accessible to a high-school student interested in mathematics IMO. (Or perhaps that should be "interested in IMO mathematics"!) I agree that it may not be a good book for first-year CS undergraduates without a good mathematical background from high school, but it's not a textbook solely for graduate students. – shreevatsa Oct 16 '16 at 9:43

Discrete Mathematics and Its Applications, by Ken Rosen, 2012. Amazon link. Here is the publisher's description:

Discrete Mathematics and its Applications, Seventh Edition, is intended for one- or two-term introductory discrete mathematics courses taken by students from a wide variety of majors, including computer science, mathematics, and engineering. This renowned best-selling text, which has been used at over 500 institutions around the world, gives a focused introduction to the primary themes in a discrete mathematics course and demonstrates the relevance and practicality of discrete mathematics to a wide variety of real-world applications…from computer science to data networking, to psychology, to chemistry, to engineering, to linguistics, to biology, to business, and to many other important fields.

It is now in its 7th(!) edition. Here is a link to its table of contents. And here is a review (of the 5th edition) by Diane Spresser, which ends

... this is, overall, an excellent text, with an impressive supplemental package.

• I agree with this recommendation- this is a very widely used textbook for first courses in discrete mathematics aimed at CS majors. – Brian Borchers Aug 1 '12 at 16:41
• (also, isn't this one of those money-making industrial style textbooks that cost a huge amount of money to rip off poor students). interestingly though, your amazon link is to an ancient edition which is quite cheap :-) – Suvrit Aug 1 '12 at 19:16
• @Suvrit: You are correct that the 7th edition has grown to exceed 1000 pages and to list on Amazon for $167. But: (a) Because this text is so popular, it is available used, and/or in earlier editions, at considerably discounted prices; (b )Scheinerman's (excellent!) textbook listsat $230 at Amazon: amazon.com/Mathematics-Discrete-Introduction-Edward-Scheinerman/… – Joseph O'Rourke Aug 1 '12 at 20:25

Lex Schrijver, who led a team redesigning the Dutch railway schedule, has a course in Combinatorial Optimization with a number of applications (although usually not at a very concrete level). I'm not always happy with the level of detail in the proofs in the text, but keep in mind that these are lecture notes and they're free. He also has a number of other texts on his website; it's a treasure trove.

This, of course, is "Hungarian" combinatorics. As for enumerative and algebraic combinatorics, I don't know of a source giving many applications (but then again, who needs applications if you can have universal properties?...).

Try Hochstättler, Schliep: An Interactive Course in Combinatorial Optimization. This book makes use of the Catbox software and the GATO interface, see http://gato.sourceforge.net/, which are great to illustrate practical examples.

Jiřì Matoušek's Thirty-three Miniatures: Mathematical and Algorithmic Applications of Linear Algebra provides a nice treatment of many discrete topics, such as spectral graph theory, combinatorics, and coding theory at an undergraduate level, with special emphasis on the practical application of linear algebra. The wide range of topics makes it a useful resource in many areas of computer science and information theory. It was also made available online by the AMS: https://kam.mff.cuni.cz/~matousek/stml-53-matousek-1.pdf

Harold S. Stone's Discrete Mathematical Structures and their Applications (Science Research Associates, 1973) has applications of group theory to computer design (adders, dynamic memories) and applications of linear finite-state machines to linear feedback shift registers. You might want to use a newer text, though.

• The preface states that the book's applications "tend to be oriented largely toward computer design." Also, "the scope of the text is close in spirit to the scope of the discrete structures course (Course B3) of the 1968 ACM curriculum. This text differs from that course primarily in that it contains much less graph theory and substantially more material on modern algebra." – Joel Reyes Noche Aug 1 '12 at 12:51

I was quite happy with Discrete Mathematics by Norman L. Biggs.

The book is carefully structured, coherent and comprehensive, and is the ideal text for students seeking a clear introduction to discrete mathematics, graph theory, combinatorics, number theory, coding theory and abstract algebra.