# Fundamentals of Discrete Math for Computer Science

Genres:

Book Preface

While this is a new edition of Fundamentals of Discrete Math for Computer Science, the goal of the book remains the same: To present discrete mathematics to computer science students in a form that is accessible to them, and in a way that will improve their programming competence. This edition improves upon its predecessor by introducing a new chapter on directed graphs, introducing a new section on drawing and coloring graphs, adding more than 100 new exercises, and providing solutions to selected exercises. We have also made numerous minor modifications in the second edition that make the text easier to read, improve clarity, or correct errata.

Most chapters begin with an example that sets the stage for its content. Chapter 1 begins by setting the stage for the whole book: How do you design algorithms to solve computing problems? How do you know your algorithm will work correctly for every suitable input? How long will your algorithm take to generate its output? In our view, teaching is much more than presenting content, and we have written this text as a design for the experience of students with our subject. A students’ first experience with a new subject can have a long-lasting impact on their perception it. We want that experience to be positive. Our text empowers students to think critically, to be effective problem solvers, to integrate theory and practice, and to recognize the importance of abstraction. It engages them with memorable, motivating examples. It challenges them with many new ideas, methods, and rigorous thinking, and we hope it entertains them like no other textbook with “Math” in its title.

This book introduces much of the “culture” of Computer Science and the common knowledge shared by all computer scientists (beyond programming). Much of it is devoted to the solutions to fundamental problems that all computer scientists have studied: how to search a list for a particular target; how to sort a list into a natural order; how to generate all objects, subsets, or sequences of some kind in such an order; how to traverse all of the nodes in a graph or digraph; and especially, how to compare the efficiency of algorithms and prove their correctness. Our constant theme is the relevance of the mathematics we present to Computer Science.

Perhaps the most distinguishing feature of this text is its informal and interactive nature. Detailed walkthroughs of algorithms appear from beginning to end. We motivate the material by inserting provocative questions and commentary into the prose, and we simulate a conversation with our reader, more like our lectures and less like other pedantic and ponderous mathematics texts. We employ the symbol “//” to denote “comments”, to indicate asides (especially expanding and explaining mathematical arguments), as signals of what comes next, and to prompt questions we want to raise in the reader’s mind. We’ve kept the text (words, sentences, and paragraphs) short and to the point, and we’ve used font changes, bold, italic and underlining to capture, focus and recapture our reader’s attention. But this book is a mathematics text. We expand on students’ intuition with precise mathematical language and ideas. Although detailed proofs are delayed until Chap. 3, the fundamental nature of proof in mathematics is explained, maintained, and applied repeatedly to proving the correctness of algorithms. One of the purposes of the text is to provide a toolbox of useful algorithms solving standard problems in Computer Science. The other purpose is to provide a catalogue of useful concepts without which the underlying theory of Computer Science cannot be understood.