Discrete Mathematics for Computer Science

0 About the Book 0.1 Active Learning 0.2 Problem-based Learning 0.3 Python Programming Language 0.4 Acknowledgments Part I — Mathematical Thinking in Computer Science 1 Proofs: Convincing Arguments 1.1 Warm Up 1.2 Existence Proofs 2 Finding an Example 2.1 How to Find an Example 2.2 Optimality 2.3 Computer Search 3 Recursion and Induction 3.1 Recursion 3.2 Induction 4 Logic 4.1 Examples and Counterexamples 4.2 Logic 4.3 Reductio ad Absurdum 5 Invariants 5.1 Double Counting 5.2 Searching for Invariants 5.3 Termination 5.4 Even and Odd Numbers 6 Project: 15-Puzzle 6.1 The Puzzle 6.2 Permutations and Transpositions 6.3 Why 15-puzzle Has No Solution 6.4 When 15-puzzle Has a Solution 6.5 Implementation 7 Appendix 7.1 Cutting a Figure 7.2 Using SAT-solvers 7.3 Using ILP-solvers 7.4 Visualizing Football Fans Part II — Combinatorics and Probability 8 Basic Counting 8.1 Starting to Count 8.2 Recursive Counting 8.3 Tuples and Permutations 9 Binomial Coefficients 9.1 Number of Games in a Tournament 9.2 Combinations 9.3 Binomial Theorem 9.4 Practice Counting 10 Advanced Counting 10.1 Review 10.2 Combinations with Repetitions 10.3 Practice Counting 11 Probability 11.1 What is Probability? 11.2 Probability: Do's and Don'ts 11.3 Conditional Probability 11.4 Monty Hall Paradox 12 Random Variables 12.1 Random Variables and Their Expectations 12.2 Linearity of Expectation 12.3 Expectation is Not All 12.4 Markov's Inequality 13 Dice Games 13.1 Dice Game Problem 13.2 Optimal Strategy