Written specifically for the computer scientists, this unique book directly addresses their needs by providing a foundation in discrete math while using motivating, relevant CS problems. Topic coverage reflects what is important to the CS market, including areas that are not covered as completely in other books-recursion trees, the relationship between induction and recursive problem decomposition, and randomized algorithms. An ideal reference for computer science professionals and students.

**Clifford Stein** is a Professor of IEOR at Columbia University. He also holds an appointment in the Department of Computer Science. He is the director of Undergraduate Programs for the IEOR Department. Prior to joining Columbia, he spent 9 years as an Assistant and Associate Professor in the Dartmouth College Department of Computer Science.

His research interests include the design and analysis of algorithms, combinatorial optimization, operations research, network algorithms, scheduling, algorithm engineering and computational biology. Professor Stein has published many influential papers in the leading conferences and journals in his field, and has occupied a variety of editorial positions including the journals ACM Transactions on Algorithms, Mathematical Programming, Journal of Algorithms, SIAM Journal on Discrete Mathematics and Operations Research Letters. His work has been supported by the National Science Foundation and Sloan Foundation. He is the winner of several prestigious awards including an NSF Career Award, an Alfred Sloan Research Fellowship and the Karen Wetterhahn Award for Distinguished Creative or Scholarly Achievement. He is also the co-author of two textbooks: *Discrete Math for Computer Science* with Scot Drysdale and *Introduction to Algorithms*, with T. Cormen, C. Leiserson and R. Rivest—the best-selling textbook in algorithms, which has been translated into 8 languages.

**(Robert L.) Scot Drysdale, III** is a professor of Computer Science at Dartmouth College and served as Chair of the Computer Science department for eight years. His main research area is algorithms, primarily computational geometry. He is best known for papers describing algorithms for computing variants of a geometric structure called the Voronoi Diagram and algorithms that use the Voronoi Diagram to solve other problems in computational geometry. He has also developed algorithms for planning and testing the correctness of tool path movements in Numerical Control (NC) machining. His work has been supported by grants from the National Science Foundation and Ford Motor Company and he was awarded a Fulbright Fellowship.

He has also made contributions to education. He is a winner of the Dartmouth Distinguished Teaching award. He was a member of the development committee for the AP exam in computer science for four years during its transition from C++ to Java and then chaired the committee for three years. He has been Principal Lecturer for DIMACS and NSF workshops and was co-director of a DIMACS institute. He was a faculty member of the ACM/MAA Institute for Retraining in Computer Science for five years.

List of Theorems, Lemmas, and Corollaries xix

Preface xxi

**CHAPTER 1 Counting 1**

1.1 Basic Counting 1

The Sum Principle 1

Abstraction 3

Summing Consecutive Integers 3

The Product Principle 4

Two-Element Subsets 6

Important Concepts, Formulas, and Theorems 7

Problems 8

1.2 Counting Lists, Permutations, and Subsets 10

Using the Sum and Product Principles 10

Lists and Functions 12

The Bijection Principle 14

k-Element Permutations of a Set 15

Counting Subsets of a Set 16

Important Concepts, Formulas, and Theorems 18

Problems 20

1.3 Binomial Coefficients 22

Pascal’s Triangle 22

A Proof Using the Sum Principle 24

The Binomial Theorem 26

Labeling and Trinomial Coefficients 28

Important Concepts, Formulas, and Theorems 29

Problems 30

1.4 Relations 32

What Is a Relation? 32

Functions as Relations 33

Properties of Relations 33

Equivalence Relations 36

Partial and Total Orders 39

Important Concepts, Formulas, and Theorems 41

Problems 42

1.5 Using Equivalence Relations in Counting 43

The Symmetry Principle 43

Equivalence Relations 45

The Quotient Principle 46

Equivalence Class Counting 46

Multisets 48

The Bookcase Arrangement Problem 50

The Number of k-Element Multisets

of an n-Element Set 51

Using the Quotient Principle to Explain a Quotient 52

Important Concepts, Formulas, and Theorems 53

Problems 54

**CHAPTER 2 Cryptography and Number Theory 59**

2.1 Cryptography and Modular Arithmetic 59

Introduction to Cryptography 59

Private-Key Cryptography 60

Public-Key Cryptosystems 63

Arithmetic Modulo n 65

Cryptography Using Addition mod n 68

Cryptography Using Multiplication mod n 69

Important Concepts, Formulas, and Theorems 71

Problems 72

2.2 Inverses and Greatest Common Divisors 75

Solutions to Equations and Inverses mod n 75

Inverses mod n 76

Converting Modular Equations to Normal Equations 79

Greatest Common Divisors 80

Euclid’s Division Theorem 81

Euclid’s GCD Algorithm 84

Extended GCD Algorithm 85

Computing Inverses 88

Important Concepts, Formulas, and Theorems 89

Problems 90

2.3 The RSA Cryptosystem 93

Exponentiation mod n 93

The Rules of Exponents 93

Fermat’s Little Theorem 96

The RSA Cryptosystem 97

The Chinese Remainder Theorem 101

Important Concepts, Formulas, and Theorems 102

Problems 104

2.4 Details of the RSA Cryptosystem 106

Practical Aspects of Exponentiation mod n 106

How Long Does It Take to Use the RSA Algorithm? 109

How Hard Is Factoring? 110

Finding Large Primes 110

Important Concepts, Formulas, and Theorems 113

Problems 114

**CHAPTER 3 Reflections on Logic and Proof 117**

3.1 Equivalence and Implication 117

Equivalence of Statements 117

Truth Tables 120

DeMorgan’s Laws 123

Implication 125

If and Only If 126

Important Concepts, Formulas, and Theorems 129

Problems 131

3.2 Variables and Quantifiers 133

Variables and Universes 133

Quantifiers 134

Standard Notation for Quantification 136

Statements about Variables 138

Rewriting Statements to Encompass Larger Universes 138

Proving Quantified Statements True or False 139

Negation of Quantified Statements 140

Implicit Quantification 143

Proof of Quantified Statements 144

Important Concepts, Formulas, and Theorems 145

Problems 147

3.3 Inference 149

Direct Inference (Modus Ponens) and Proofs 149

Rules of Inference for Direct Proofs 151

Contrapositive Rule of Inference 153

Proof by Contradiction 155

Important Concepts, Formulas, and Theorems 158

Problems 159

**CHAPTER 4 Induction, Recursion, and Recurrences 161**

4.1 Mathematical Induction 161

Smallest Counterexamples 161

The Principle of Mathematical Induction 165

Strong Induction 169

Induction in General 171

A Recursive View of Induction 173

Structural Induction 176

Important Concepts, Formulas, and Theorems 178

Problems 180

4.2 Recursion, Recurrences, and Induction 183

Recursion 183

Examples of First-Order Linear Recurrences 185

Iterating a Recurrence 187

Geometric Series 188

First-Order Linear Recurrences 191

Important Concepts, Formulas, and Theorems 195

Problems 197

4.3 Growth Rates of Solutions to Recurrences 198

Divide and Conquer Algorithms 198

Recursion Trees 201

Three Different Behaviors 209

Important Concepts, Formulas, and Theorems 210

Problems 212

4.4 The Master Theorem 214

Master Theorem 214

Solving More General Kinds of Recurrences 217

Extending the Master Theorem 218

Important Concepts, Formulas, and Theorems 220

Problems 221

4.5 More General Kinds of Recurrences 222

Recurrence Inequalities 222

The Master Theorem for Inequalities 223

A Wrinkle with Induction 225

Further Wrinkles in Induction Proofs 227

Dealing with Functions Other Than nc 230

Important Concepts, Formulas, and Theorems 232

Problems 233

4.6 Recurrences and Selection 235

The Idea of Selection 235

A Recursive Selection Algorithm 236

Selection without Knowing the Median in Advance 237

An Algorithm to Find an Element in the Middle Half 239

An Analysis of the Revised Selection Algorithm 242

Uneven Divisions 244

Important Concepts, Formulas, and Theorems 246

Problems 247

**CHAPTER 5 Probability 249**

5.1 Introduction to Probability 249

Why Study Probability? 249

Some Examples of Probability Computations 252

Complementary Probabilities 253

Probability and Hashing 254

The Uniform Probability Distribution 256

Important Concepts, Formulas, and Theorems 259

Problems 260

5.2 Unions and Intersections 262

The Probability of a Union of Events 262

Principle of Inclusion and Exclusion for Probability 265

The Principle of Inclusion and Exclusion for Counting 271

Important Concepts, Formulas, and Theorems 273

Problems 274

5.3 Conditional Probability and Independence 276

Conditional Probability 276

Bayes’ Theorem 280

Independence 280

Independent Trials Processes 282

Tree Diagrams 284

Primality Testing 288

Important Concepts, Formulas, and Theorems 289

Problems 290

5.4 Random Variables 292

What Are Random Variables? 292

Binomial Probabilities 293

A Taste of Generating Functions 295

Expected Value 296

Expected Values of Sums and Numerical Multiples 299

Indicator Random Variables 302

The Number of Trials until the First Success 304

Important Concepts, Formulas, and Theorems 306

Problems 307

5.5 Probability Calculations in Hashing 310

Expected Number of Items per Location 310

Expected Number of Empty Locations 311

Expected Number of Collisions 312

Expected Maximum Number of Elements in a Location of a Hash Table 315

Important Concepts, Formulas, and Theorems 320

Problems 321

5.6 Conditional Expectations, Recurrences, and Algorithms 325

When Running Times Depend on More than Size of Inputs 325

Conditional Expected Values 327

Randomized Algorithms 329

Selection Revisited 331

QuickSort 333

A More Careful Analysis of RandomSelect 336

Important Concepts, Formulas, and Theorems 339

Problems 340

5.7 Probability Distributions and Variance 343

Distributions of Random Variables 343

Variance 346

Important Concepts, Formulas, and Theorems 354

Problems 355

**CHAPTER 6 Graphs 359**

6.1 Graphs 359

The Degree of a Vertex 363

Connectivity 365

Cycles 367

Trees 368

Other Properties of Trees 368

Important Concepts, Formulas, and Theorems 371

Problems 373

6.2 Spanning Trees and Rooted Trees 375

Spanning Trees 375

Breadth-First Search 377

Rooted Trees 382

Important Concepts, Formulas, and Theorems 386

Problems 387

6.3 Eulerian and Hamiltonian Graphs 389

Eulerian Tours and Trails 389

Finding Eulerian Tours 394

Hamiltonian Paths and Cycles 395

NP-Complete Problems 401

Proving That Problems Are NP-Complete 403

Important Concepts, Formulas, and Theorems 406

Problems 407

6.4 Matching Theory 410

The Idea of a Matching 410

Making Matchings Bigger 414

Matching in Bipartite Graphs 417

Searching for Augmenting Paths in Bipartite Graphs 417

The Augmentation-Cover Algorithm 420

Efficient Algorithms 426

Important Concepts, Formulas, and Theorems 427

Problems 428

6.5 Coloring and Planarity 430

The Idea of Coloring 430

Interval Graphs 433

Planarity 435

The Faces of a Planar Drawing 437

The Five-Color Theorem 441

Important Concepts, Formulas, and Theorems 444

Problems 445

**APPENDIX A Derivation of the More General Master Theorem 449**

More General Recurrences 449

Recurrences for General n 451

Removing Floors and Ceilings 452

Floors and Ceilings in the Stronger Version of the Master Theorem 453

Proofs of Theorems 453

Important Concepts, Formulas, and Theorems 457

Problems 458

**APPENDIX B Answers and Hints to Selected Problems 461**

Bibliography 477

Index 479