A Course in Discrete Structures
A Course in Discrete Structures
Rafael Pass Wei-Lung Dustin Tseng
Preface
Discrete mathematics deals with objects that come in discrete bundles, e.g., 1 or 2 babies. In contrast, continuous mathematics deals with objects that vary continuously, e.g., 3.42 inches from a wall. Think of digital watches versus analog watches (ones where the second hand loops around continuously without stopping).
Why study discrete mathematics in computer science? It does not directly help us write programs. At the same time, it is the mathematics underlying almost all of computer science. Here are a few examples:
? Designing high-speed networks and message routing paths. ? Finding good algorithms for sorting. ? Performing web searches. ? Analysing algorithms for correctness and efficiency. ? Formalizing security requirements. ? Designing cryptographic protocols.
Discrete mathematics uses a range of techniques, some of which is seldom found in its continuous counterpart. This course will roughly cover the following topics and specific applications in computer science.
1. Sets, functions and relations 2. Proof techniques and induction 3. Number theory
a) The math behind the RSA Crypto system 4. Counting and combinatorics 5. Probability
a) Spam detection b) Formal security 6. Logic a) Proofs of program correctness 7. Graph theory
i
a) Message Routing b) Social networks 8. Finite automata and regular languages a) Compilers
In the end, we will learn to write precise mathematical statements that captures what we want in each application, and learn to prove things about these statements. For example, how will we formalize the infamous zeroknowledge property? How do we state, in mathematical terms, that a banking protocol allows a user to prove that she knows her password, without ever revealing the password itself?
Contents
Contents
iii
1 Sets, Functions and Relations
1
1.1 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4 Set Cardinality, revisited . . . . . . . . . . . . . . . . . . . . . . 8
2 Proofs and Induction
13
2.1 Basic Proof Techniques . . . . . . . . . . . . . . . . . . . . . . 13
2.2 Proof by Cases and Examples . . . . . . . . . . . . . . . . . . . 15
2.3 Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.4 Inductive Definitions . . . . . . . . . . . . . . . . . . . . . . . . 26
2.5 Fun Tidbits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3 Number Theory
37
3.1 Divisibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.2 Modular Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . 41
3.3 Primes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.4 The Euler Function . . . . . . . . . . . . . . . . . . . . . . . 52
3.5 Public-Key Cryptosystems and RSA . . . . . . . . . . . . . . . 56
4 Counting
61
4.1 The Product and Sum Rules . . . . . . . . . . . . . . . . . . . 61
4.2 Permutations and Combinations . . . . . . . . . . . . . . . . . 63
4.3 Combinatorial Identities . . . . . . . . . . . . . . . . . . . . . . 65
4.4 Inclusion-Exclusion Principle . . . . . . . . . . . . . . . . . . . 69
4.5 Pigeonhole Principle . . . . . . . . . . . . . . . . . . . . . . . . 72
5 Probability
73
iii
5.1 Probability Spaces . . . . . . . . . . . . . . . . . . . . . . . . . 73 5.2 Conditional Probability and Independence . . . . . . . . . . . . 77 5.3 Random Variables . . . . . . . . . . . . . . . . . . . . . . . . . 85 5.4 Expectatation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 5.5 Variance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
6 Logic
95
6.1 Propositional Logic . . . . . . . . . . . . . . . . . . . . . . . . . 95
6.2 Logical Inference . . . . . . . . . . . . . . . . . . . . . . . . . . 100
6.3 First Order Logic . . . . . . . . . . . . . . . . . . . . . . . . . . 105
6.4 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
7 Graphs
109
7.1 Graph Isomorphism . . . . . . . . . . . . . . . . . . . . . . . . 112
7.2 Paths and Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . 115
7.3 Graph Coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
7.4 Random Graphs [Optional] . . . . . . . . . . . . . . . . . . . . 122
8 Finite Automata
125
8.1 Deterministic Finite Automata . . . . . . . . . . . . . . . . . . 125
8.2 Non-Deterministic Finite Automata . . . . . . . . . . . . . . . 130
8.3 Regular Expressions and Kleene's Theorem . . . . . . . . . . . 133
A Problem Sets
137
A.1 Problem Set A . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
B Solutions to Problem Sets
141
B.1 Problem Set A . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- writing in the computer science curriculum
- computer science principles
- computer science fundamentals
- helping your child learn science pdf
- computational thinking what and why
- science in the primary school department of education
- a course in discrete structures
- why computer skills are important
- what is computer science
Related searches
- college course in high school
- certificate course in mental health
- discrete structures symbols
- creating a course syllabus
- a course in financial calculus
- course in general linguistics summary
- saussure course in general linguistics
- course in general linguistics pdf
- digital marketing course in india
- basic computer course in pdf
- nmls training course in california
- first course in probability pdf