IMPORTANT: All future lectures will be held in Noyes 217, rather than Altgeld 245.
Course Calendar
(Note that this calendar is potentially subject to revision, based on the needs of the class)
Lecture 1: Motivation, set definition and notation
Lecture 2: Set equality, subsets, power sets, cartesian products, relations, visualization with Venn diagrams
Lecture 3: Union, intersection, set difference, complement, set identities
Lecture 4: Proof strategies for set identities, membership tables, basic definitions for functions
Lecture 6: Algorithms, pseudocode, and the greedy-change problem
Lecture 7: Greedy-change problem continued, scheduling problem, introduction to big-O notation
Lecture 10: More examples of inductive proofs (divisibility and set identities), common errors in inductive proofs
Lecture 11: Strong induction, well-ordering property
Lecture 12: Introduction to counting (product and sum rules)
Lecture 13: Subtraction rule, division rule, pigeonhole principle
Lecture 14: Generalized pigeonhole principle, permutations, combinations
Lecture 18: Modeling counting problems with boxes and balls, introduction to discrete probability
Lecture 20: Probability distributions, uniform probability, examples of non-uniform probability distributions
Lecture 21: Pairwise independence, mutual independence, conditional probability, Bernoulli trials, binomial distribution
Lecture 22: Binomial distribution example, Bayes' Theorem
Lecture 23: Sequences, recurrence relations, Fibonacci's rabbit problem, Tower of Hanoi problem
Lecture 24: Finding closed formulas via iteration, more recurrence relation examples, classifying recurrence relations
Lecture 25: Definition of characteristic equation, solving linear homogenous recurrence relations with constant coefficients
Lecture 26: Examples of solving linear homogeneous recurrence relations, linear nonhomogeneous recurrence relations
Lecture 27: Particular solutions to nonhomogeneous recurrence relations, motivating the principle of inclusion-exclusion
Lecture 28: Principle of Inclusion-Exclusion, basic examples of applying the PIE to enumerative questions
Lecture 29: Applications of Inclusion-Exclusion, including the hatcheck problem
Lecture 30: Definition of a relation, basic properties (symmetric, antisymmetric, reflexive, transitive), many examples
Lecture 31: Composites of relations, matrix representations of relations (properties and computing unions/intersections)
Lecture 33: Examples and non-examples of equivalence relations, equivalence classes, partitions
Lecture 34: Introduction to Graph Theory, basic definitions and many examples
Lecture 38: Incidence matrices for directed graphs, paths, circuits, connected and disconnected graphs, subgraphs
Lecture 39: Vertex connectivity, edge connectivity, Whitney's Theorem
As mentioned in the syllabus, I highly encourage typesetting assignments rather than writing by hand. You may wish to do so using Overleaf, which is free and cloud-based. If you would find it helpful, I have created a basic template for homework in this course (the TeX code is available here). You are not required to use this template or to use LaTeX.
Homework 3: PDF, TeX
Solutions: PDF, TeX
Induction Handout: PDF
Homework 7: PDF, TeX (NOW DUE WEDNESDAY, MARCH 30TH)
Solutions: PDF, TeX
Linear recurrence relation flow chart: PDF
Homework 9: PDF, TeX (NOW DUE MONDAY, APRIL 18TH)
Solutions: PDF, TeX
Homework 10: PDF, TeX (NOW DUE WEDNESDAY, APRIL 27th)
Solutions: PDF, TeX
"Guidelines for good mathematical writing," by Francis Su.
Detexify, a web app for identifying the LaTeX command(s) for various symbols.
Overleaf, a cloud-based LaTeX editor.
GraTeX, a free tool for generating TikZ code for graphs.