Notes on Discrete Mathematics

Table of contents
List of figures
List of tables
List of algorithms
Preface
Resources
Introduction
	So why do I need to learn all this nasty mathematics?
	But isn't math hard?
	Thinking about math with your heart
	What you should know about math
		Foundations and logic
		Basic mathematics on the real numbers
		Fundamental mathematical objects
		Modular arithmetic and polynomials
		Linear algebra
		Graphs
		Counting
		Probability
		Tools
Mathematical logic
	The basic picture
		Axioms, models, and inference rules
		Consistency
		What can go wrong
		The language of logic
		Standard axiom systems and models
	Propositional logic
		Operations on propositions
			Precedence
		Truth tables
		Tautologies and logical equivalence
			Inverses, converses, and contrapositives
			Equivalences involving true and false
				Example
		Normal forms
	Predicate logic
		Variables and predicates
		Quantifiers
			Universal quantifier
			Existential quantifier
			Negation and quantifiers
			Restricting the scope of a quantifier
			Nested quantifiers
			Examples
		Functions
		Equality
			Uniqueness
		Models
			Examples
	Proofs
		Inference Rules
		Proofs, implication, and natural deduction
			The Deduction Theorem
			Natural deduction
		Inference rules for equality
		Inference rules for quantified statements
	Proof techniques
	Examples of proofs
		Axioms for even numbers
		A theorem and its proof
		A more general theorem
		Something we can't prove
Set theory
	Naive set theory
	Operations on sets
	Proving things about sets
	Axiomatic set theory
	Cartesian products, relations, and functions
		Examples of functions
		Sequences
		Functions of more (or less) than one argument
		Composition of functions
		Functions with special properties
			Surjections
			Injections
			Bijections
			Bijections and counting
	Constructing the universe
	Sizes and arithmetic
		Infinite sets
		Countable sets
		Uncountable sets
	Further reading
The real numbers
	Field axioms
		Axioms for addition
		Axioms for multiplication
		Axioms relating multiplication and addition
		Other algebras satisfying the field axioms
	Order axioms
	Least upper bounds
	What's missing: algebraic closure
	Arithmetic
	Connection between the reals and other standard algebras
	Extracting information from reals
Induction and recursion
	Simple induction
	Alternative base cases
	Recursive definitions work
	Other ways to think about induction
	Strong induction
		Examples
	Recursively-defined structures
		Functions on recursive structures
		Recursive definitions and induction
		Structural induction
Summation notation
	Summations
		Formal definition
		Scope
		Summation identities
		Choosing and replacing index variables
		Sums over given index sets
		Sums without explicit bounds
		Infinite sums
		Double sums
	Products
	Other big operators
	Closed forms
		Some standard sums
		Guess but verify
		Ansatzes
Asymptotic notation
	Definitions
	Motivating the definitions
	Proving asymptotic bounds
	General principles for dealing with asymptotic notation
		Remember the difference between big-O, big-Omega, and big-Theta
		Simplify your asymptotic terms as much as possible
		Use limits (may require calculus)
	Asymptotic notation and summations
		Pull out constant factors
		Bound using a known sum
			Geometric series
			Constant series
			Arithmetic series
			Harmonic series
		Bound part of the sum
		Integrate
		Grouping terms
		An odd sum
		Final notes
	Variations in notation
		Absolute values
		Abusing the equals sign
Number theory
	Divisibility
	The division algorithm
	Modular arithmetic and residue classes
		Arithmetic on residue classes
	Greatest common divisors
		The Euclidean algorithm for computing gcd(m,n)
		The extended Euclidean algorithm
			Example
			Applications
	The Fundamental Theorem of Arithmetic
		Unique factorization and gcd
	More modular arithmetic
		Division in Zm
		The Chinese Remainder Theorem
		The size of Z*m and Euler's Theorem
	RSA encryption
Relations
	Representing relations
		Directed graphs
		Matrices
	Operations on relations
		Composition
		Inverses
	Classifying relations
	Equivalence relations
		Why we like equivalence relations
	Partial orders
		Drawing partial orders
		Comparability
		Lattices
		Minimal and maximal elements
		Total orders
			Topological sort
		Well orders
	Closures
		Examples
Graphs
	Types of graphs
		Directed graphs
		Undirected graphs
		Hypergraphs
	Examples of graphs
	Local structure of graphs
	Some standard graphs
	Subgraphs and minors
	Graph products
	Functions between graphs
	Paths and connectivity
	Cycles
	Proving things about graphs
		Paths and simple paths
		The Handshaking Lemma
		Characterizations of trees
		Spanning trees
		Eulerian cycles
Counting
	Basic counting techniques
		Equality: reducing to a previously-solved case
		Inequalities: showing |A| <= |B| and |B| <= |A|
		Addition: the sum rule
			For infinite sets
			The Pigeonhole Principle
		Subtraction
			Inclusion-exclusion for infinite sets
			Combinatorial proof
		Multiplication: the product rule
			Examples
			For infinite sets
		Exponentiation: the exponent rule
			Counting injections
		Division: counting the same thing in two different ways
			Binomial coefficients
			Multinomial coefficients
		Applying the rules
		An elaborate counting problem
		Further reading
	Binomial coefficients
		Recursive definition
			Pascal's identity: algebraic proof
		Vandermonde's identity
			Combinatorial proof
			Algebraic proof
		Sums of binomial coefficients
		The general inclusion-exclusion formula
		Negative binomial coefficients
		Fractional binomial coefficients
		Further reading
	Generating functions
		Basics
			A simple example
			Why this works
			Formal definition
		Some standard generating functions
		More operations on formal power series and generating functions
		Counting with generating functions
			Disjoint union
			Cartesian product
			Repetition
				Example: (0|11)*
				Example: sequences of positive integers
			Pointing
			Substitution
				Example: bit-strings with primes
				Example: (0|11)* again
		Generating functions and recurrences
			Example: A Fibonacci-like recurrence
		Recovering coefficients from generating functions
			Partial fraction expansion and Heaviside's cover-up method
				Example: A simple recurrence
				Example: Coughing cows
				Example: A messy recurrence
			Partial fraction expansion with repeated roots
				Solving for the PFE directly
				Solving for the PFE using the extended cover-up method
		Asymptotic estimates
		Recovering the sum of all coefficients
			Example
		A recursive generating function
		Summary of operations on generating functions
		Variants
		Further reading
Probability theory
	Events and probabilities
		Probability axioms
			The Kolmogorov axioms
			Examples of probability spaces
		Probability as counting
			Examples
		Independence and the intersection of two events
			Examples
		Union of events
			Examples
		Conditional probability
			Conditional probabilities and intersections of non-independent events
			The law of total probability
			Bayes's formula
	Random variables
		Examples of random variables
		The distribution of a random variable
			Some standard distributions
			Joint distributions
				Examples
		Independence of random variables
			Examples
			Independence of many random variables
		The expectation of a random variable
			Variables without expectations
			Expectation of a sum
				Example
			Expectation of a product
			Conditional expectation
				Examples
			Conditioning on a random variable
		Markov's inequality
			Example
			Conditional Markov's inequality
		The variance of a random variable
			Multiplication by constants
			The variance of a sum
			Chebyshev's inequality
				Application: showing that a random variable is close to its expectation
				Application: lower bounds on random variables
		Probability generating functions
			Sums
			Expectation and variance
		Summary: effects of operations on expectation and variance of random variables
		The general case
			Densities
			Independence
			Expectation
Linear algebra
	Vectors and vector spaces
		Relative positions and vector addition
		Scaling
	Abstract vector spaces
	Matrices
		Interpretation
		Operations on matrices
			Transpose of a matrix
			Sum of two matrices
			Product of two matrices
			The inverse of a matrix
				Example
			Scalar multiplication
		Matrix identities
	Vectors as matrices
		Length
		Dot products and orthogonality
	Linear combinations and subspaces
		Bases
	Linear transformations
		Composition
		Role of rows and columns of M in the product Mx
		Geometric interpretation
		Rank and inverses
		Projections
	Further reading
Finite fields
	A magic trick
	Fields and rings
	Polynomials over a field
	Algebraic field extensions
	Applications
		Linear-feedback shift registers
		Checksums
		Cryptography
Sample assignments from Fall 2017
	Assignment 1: Due Wednesday, 2017-09-13, at 5:00 pm
		A curious proposition
		Relations
		A theory of shirts
	Assignment 2: Due Wednesday, 2017-09-20, at 5:00 pm
		Arithmetic, or is it?
		Some distributive laws
		Elements and subsets
	Assignment 3: Due Wednesday, 2017-09-27, at 5:00 pm
		A powerful problem
		A correspondence
		Inverses
	Assignment 4: Due Wednesday, 2017-10-04, at 5:00 pm
		Covering a set with itself
		More inverses
		Rational and irrational
	Assignment 5: Due Wednesday, 2017-10-11, at 5:00 pm
		A recursive sequence
		Comparing products
		Rubble removal
	Assignment 6: Due Wednesday, 2017-10-25, at 5:00 pm
		An oscillating sum
		An approximate sum
		A stretched function
	Assignment 7: Due Wednesday, 2017-11-01, at 5:00 pm
		Divisibility
		Squares
		A Series of Unfortunate Exponents
	Assignment 8: Due Wednesday, 2017-11-08, at 5:00 pm
		Minimal and maximal elements
		No trailing zeros
		Domination
	Assignment 9: Due Wednesday, 2017-11-15, at 5:00 pm
		Quadrangle closure
		Cycles
		Deleting a graph
	Assignment 10: Due Wednesday, 2017-11-29, at 5:00 pm
		Too many injections
		Binomial coefficients
		Variable names
Sample exams from Fall 2017
	CPSC 202 Exam 1, October 17th, 2017
		Factorials (20 points)
		A tautology (20 points)
		Subsets (20 points)
		Surjective functions (20 points)
	CPSC 202 Exam 2, December 7th, 2017
		Non-decreasing sequences (20 points)
		Perfect matchings (20 points)
		Quadratic forms (20 points)
		Minimal lattices (20 points)
Sample assignments from Fall 2013
	Assignment 1: due Thursday, 2013-09-12, at 5:00 pm
		Tautologies
		Positively equivalent
		A theory of leadership
	Assignment 2: due Thursday, 2013-09-19, at 5:00 pm
		Subsets
		A distributive law
		Exponents
	Assignment 3: due Thursday, 2013-09-26, at 5:00 pm
		Surjections
		Proving an axiom the hard way
		Squares and bigger squares
	Assignment 4: due Thursday, 2013-10-03, at 5:00 pm
		A fast-growing function
		A slow-growing set
		Double factorials
	Assignment 5: due Thursday, 2013-10-10, at 5:00 pm
		A bouncy function
		Least common multiples of greatest common divisors
		Adding and subtracting
	Assignment 6: due Thursday, 2013-10-31, at 5:00 pm
		Factorials mod n
		Indivisible and divisible
		Equivalence relations
	Assignment 7: due Thursday, 2013-11-07, at 5:00 pm
		Flipping lattices with a function
		Splitting graphs with a mountain
		Drawing stars with modular arithmetic
	Assignment 8: due Thursday, 2013-11-14, at 5:00 pm
		Two-path graphs
		Even teams
		Inflected sequences
	Assignment 9: due Thursday, 2013-11-21, at 5:00 pm
		Guessing the median
		Two flushes
		Dice and more dice
Sample exams from Fall 2013
	CS202 Exam 1, October 17th, 2013
		A tautology (20 points)
		A system of equations (20 points)
		A sum of products (20 points)
		A subset problem (20 points)
	CS202 Exam 2, December 4th, 2013
		Minimum elements (20 points)
		Quantifiers (20 points)
		Quadratic matrices (20 points)
		Low-degree connected graphs (20 points)
Midterm exams from earlier semesters
	Midterm Exam, October 12th, 2005
		A recurrence (20 points)
		An induction proof (20 points)
		Some binomial coefficients (20 points)
		A probability problem (20 points)
	Midterm Exam, October 24th, 2007
		Dueling recurrences (20 points)
		Seating arrangements (20 points)
		Non-attacking rooks (20 points)
		Subsets (20 points)
	Midterm Exam, October 24th, 2008
		Some sums (20 points)
		Nested ranks (20 points)
		Nested sets (20 points)
		An efficient grading method (20 points)
	Midterm exam, October 21st, 2010
		A partial order (20 points)
		Big exponents (20 points)
		At the playground (20 points)
		Gauss strikes back (20 points)
Final exams from earlier semesters
	CS202 Final Exam, December 15th, 2004
		A multiplicative game (20 points)
		An equivalence in space (20 points)
		A very big fraction (20 points)
		A pair of odd vertices (20 points)
		How many magmas? (20 points)
		A powerful relationship (20 points)
		A group of archaeologists (20 points)
	CS202 Final Exam, December 16th, 2005
		Order (20 points)
		Count the subgroups (20 points)
		Two exits (20 points)
		Victory (20 points)
		An aggressive aquarium (20 points)
		A subspace of matrices (20 points)
	CS202 Final Exam, December 20th, 2007
		A coin-flipping problem (20 points)
		An ordered group (20 points)
		Weighty vectors (20 points)
		A dialectical problem (20 points)
		A predictable pseudorandom generator (20 points)
		At the robot factory (20 points)
	CS202 Final Exam, December 19th, 2008
		Some logical sets (20 points)
		Modularity (20 points)
		Coin flipping (20 points)
		A transitive graph (20 points)
		A possible matrix identity (20 points)
	CS202 Final Exam, December 14th, 2010
		Backwards and forwards (20 points)
		Linear transformations (20 points)
		Flipping coins (20 points)
		Subtracting dice (20 points)
		Scanning an array (20 points)
How to write mathematics
	By hand
	LaTeX
	Microsoft Word equation editor
	Google Docs equation editor
	ASCII and/or Unicode art
	Markdown
Tools from calculus
	Limits
	Derivatives
	Integrals
The natural numbers
	The Peano axioms
	A simple proof
	Defining addition
		Other useful properties of addition
	A scary induction proof involving even numbers
	Defining more operations
Bibliography
Index