Discrete Mathematics for Computer Scientists: International Edition

Stein/Drysdale/Bogart's Discrete Mathematics for Computer Scientists is ideal for computer science students taking the discrete math course. Written specifically for computer science students, this unique textbook directly addresses their needs by providing a foundation in discrete math while using motivating, relevant CS applications. This text takes an active-learning approach where activities are presented as exercises and the material is then fleshed out through explanations and extensions of the exercises.

Table of Contents:
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

About the Author :
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.