A Course in Discrete Structures

✍ Scribed by Raphael Pass, Wei-lung Tseng

• Year: 2011
• Tongue: English
• Leaves: 153
• Category: Library

✦ Table of Contents

Contents......Page 4
1.1 Sets......Page 6
1.2 Relations......Page 10
1.3 Functions......Page 12
1.4 Set Cardinality, revisited......Page 13
2.1 Basic Proof Techniques......Page 18
2.2 Proof by Cases and Examples......Page 20
2.3 Induction......Page 22
2.4 Inductive Definitions......Page 31
2.5 Fun Tidbits......Page 36
3.1 Divisibility......Page 42
3.2 Modular Arithmetic......Page 46
3.3 Primes......Page 52
3.4 The Euler \phi Function......Page 57
3.5 Public-Key Cryptosystems and RSA......Page 61
4.1 The Product and Sum Rules......Page 66
4.2 Permutations and Combinations......Page 68
4.3 Combinatorial Identities......Page 70
4.4 Inclusion-Exclusion Principle......Page 74
4.5 Pigeonhole Principle......Page 77
5.1 Probability Spaces......Page 78
5.2 Conditional Probability and Independence......Page 82
5.3 Random Variables......Page 90
5.4 Expectatation......Page 92
5.5 Variance......Page 97
6.1 Propositional Logic......Page 100
6.2 Logical Inference......Page 105
6.3 First Order Logic......Page 110
6.4 Applications......Page 113
7 Graphs......Page 114
7.1 Graph Isomorphism......Page 117
7.2 Paths and Cycles......Page 120
7.3 Graph Coloring......Page 125
7.4 Random Graphs [Optional]......Page 127
8.1 Deterministic Finite Automata......Page 130
8.2 Non-Deterministic Finite Automata......Page 135
8.3 Regular Expressions and Kleene's Theorem......Page 138
A.1 Problem Set A......Page 142
B.1 Problem Set A......Page 146