Discrete Mathematics: Schedule

Introduction to propositions/statements, logical connectives, and translation of sentences.

Lecture notes (printer-friendly). Further reading: Levin 4 – 14 and Levin 198 – 204.

For homework (due Sunday 2021-02-12 at midnight), follow these instructions (printer-friendly) to familiarize yourself with Gradescope submissions.

Truth tables and an introduction to logical equivalence.

Lecture notes (printer-friendly). Further reading: Levin pages 201 – 204.

For homework (due Friday, 26 February 2021 by 11:59pm), complete these exercises (printer-friendly).

Algebra of logical equivalence (using the basic equivalences). Disjunctive normal form of propositional statements. Introduction to arguments, including a list of rules of inference (i.e. basic argument forms).

Lecture notes (printer-friendly). Recorded lecture. Further reading: my logic studysheet (because I am dangerously kind).

Proofs in the propositional logic system. Using replacement rules (that is, the laws of equivalent exchange) and simple applications of the rules of inference.

Lecture notes (printer-friendly). Recorded lecture. Further reading: Logica (many examples and a decent discussion), my notes (printer-friendly).

Conditional proof and proof by contradiction in the propositional logic system.

Lecture notes (printer-friendly). Recorded lecture. Further reading: Logica (many examples and a decent discussion), my notes (printer-friendly).

Introduction to predicates and quantifiers. Introduction to (naive) set theory. Common sets in mathematics.

Lecture notes (printer-friendly). Recorded lecture. Further reading: my notes (printer-friendly), Levin pages 15 – 17 and pages 24 – 34.

More on set theory and predicate logic.

Lecture notes (printer-friendly). Recorded lecture. Further reading: Levin pages 24 – 34 and Sundstrom section 5.1.

Our first mathematical proofs, all involving sets and set relationships.

Lecture notes (printer-friendly). Recorded lecture. Further reading: Sundstrom section 5.2.

Wrap-up discussion of set equalities. An introduction to weak mathematical induction with some very simple examples. Brief introduction to the Fibonacci numbers.

Lecture notes (printer-friendly). Recorded lecture. Further reading: Levin section 2.5 and Sundstrom section 4.1. For some more examples (in video form), see this page.

More mathematical induction, with more focus on the Fibonacci numbers.

Lecture notes (printer-friendly). Recorded lecture. Further reading: Levin section 2.5 and Sundstrom section 4.1.

For homework (due Monday 2021-03-15 at midnight), complete these exercises (printer-friendly).

Still more on mathematical induction, in case this horse is not yet dead… We saw another good induction proof, followed by some induction pitfalls (i.e. common errors) illustrated with some bad proofs and discussed what went wrong.

Lecture notes (printer-friendly). Recorded lecture. Further reading: Levin section 2.5 and Sundstrom section 4.1.

Student-driven review session for Exam 1 (here are the solutions–and printer-friendly version–from the review session problems I was asked).

Exam 1 administered on Zoom during the normal lecture time.

Grading done; regrade requests due before midnight on Friday 19 March 2021.

Introduction to divisibility among integers, and the basic properties thereof.

Lecture notes (printer-friendly). Recorded lecture. Further reading: Levin section 5.2 and my notes on number theory.

Brief discussion of the Well-Ordering Principle. A proof of the Quotient-Remainder Theorem using the Well-Ordering Principle.

Lecture notes (printer-friendly). Recorded lecture. Further reading: Levin section 5.2 and my notes on number theory. Note that Levin calls the Quotient-Remainder Theorem by another name: the Division Algorithm.

Introduction to arithmetic modulo a positive integer. Brief discussion of the greatest common divisor.

Lecture notes (printer-friendly). Recorded lecture. Further reading: Levin section 5.2 and my notes on number theory.

Euclid's Algorithm for efficient computation of greatest common divisors.

Lecture notes (printer-friendly). Recorded lecture. Further reading: Levin section 5.2 and my notes on number theory.

Solving linear congruence equations (modulo \(m\)). Note: we began late and ended early because the campus WiFi was acting unreliably for both instructor and students…

Lecture notes (printer-friendly). Recorded lecture. Further reading: Levin section 5.2 and my notes on number theory.

Prime numbers, Euclid's Lemma, and prime sieves. The Fundamental Theorem of Arithmetic.

Lecture notes (printer-friendly). Recorded lecture. Further reading: Levin section 5.2 and my notes on number theory.

For homework, complete and submit these exercises (printer-friendly) to Gradescope before midnight on 13th April.

Introduction to cardinality and basic enumeration techniques (the Addition Principle, the Product Principle, and the Correspondence Principle) with many simple examples.

Lecture notes (printer-friendly). Recorded lecture. Further reading: Levin section 1.1 and Doerr and Levasseur sections 2.1 – 2.2; these sections have many examples worked out completely, and many practice problems. You can also look at my notes from a previous semester.

Enumeration of general sequences, permutations, and ordered $k$-subsets.

Lecture notes (printer-friendly). Recorded lecture. Further reading: Levin section 1.1 and Doerr and Levasseur sections 2.1 – 2.2; these sections have many examples worked out completely, and many practice problems.

A formula for the binomial coefficients. Enumerating anagrams and other simple enumeration problems.

Lecture notes (printer-friendly). Recorded lecture. Further reading: Levin section 1.1 and Doerr and Levasseur section 2.3; these sections have many examples worked out completely, and many practice problems.

Student-driven review session for Exam 2. Here are the Lecture notes (printer-friendly) and video from the review session.

Note: for enumeration practice, students should see the exercises in Levin section 1.1 and Doerr and Levasseur sections 2.1 – 2.3.

Exam 2 administered on Zoom during the normal lecture time.

Update: Exam graded, regrade requests closed.

More on the binomial coefficients, including some simple identities via enumeration. A proof of the Binomial Theorem.

Lecture notes (printer-friendly). Recorded lecture. Further reading: Levin sections 1.3 – 1.4 (has many examples worked out completely–and many practice problems).

A review of basic techniques and an introduction to the Inclusion-Exclusion Principle. A brief introduction to the Pigeonhole Principle and the Generalized Pigeonhole Principle.

Lecture notes (printer-friendly). Recorded lecture. Further reading: Levin example 3.2.9 and section 1.1, Doerr and Levasseur section 2.3.2, and this Mathologer video.

An example-filled introduction to relations, including properties of reflexivity, symmetry, and transitivity.

Lecture notes (printer-friendly). Recorded lecture. Further reading: my notes.

Equivalence relations. Set functions. Injective functions.

Lecture notes (printer-friendly). Recorded lecture. Further reading: Levin section 0.4 and my notes.

Note: The presentation problems (printer-friendly) are available to browse!

Brief word on the relationship between partitions and equivalence relations. Injective and surjective functions.

Lecture notes (printer-friendly). Recorded lecture. Further reading: Levin section 0.4 and my notes.

Wrapping up on injective, surjective, and bijective functions.

Lecture notes (printer-friendly). Recorded lecture. Further reading: Levin section 0.4 and my notes.

Introduction to graphs and related concepts and terminology.

Lecture notes (printer-friendly). Recorded lecture. Further reading: Levin section 4.1.

Some more introductory content on graphs (including a proof of the Handshaking Lemma and applications to the degree sequence).

Lecture notes (printer-friendly). Recorded lecture. Further reading: Levin section 4.1.

Reminder: Homework 4 is due tonight!

Discussed walks, trails, connected components, and gave a characterization of graphs with an Euler Trail.

Lecture notes (printer-friendly). Recorded lecture. Further reading: Levin section 4.5.

Recalled Euler trails and defined Hamilton paths. Note: Many student presentations given at the start of lecture.

Lecture notes (printer-friendly). Recorded lecture. Further reading: Levin section 4.5 and proof the Petersen graph has no Hamilton cycles.

Lecture notes (printer-friendly). Recorded lecture. Further reading: Levin section 4.1.

Introduction to coloring graphs.

Lecture notes (printer-friendly). Recorded lecture. Further reading: Levin section 4.4.

Reminder: Homework 5 is due tonight!

Deletion and contraction in general graphs. The chromatic polynomial of a graph via deletion and contraction.

Lecture notes (printer-friendly). Recorded lecture.

Characterizing trees. Leaves and roots. Why are trees always upside down?

Lecture notes (printer-friendly). Recorded lecture. Further reading: Levin section 4.2.

Finding minimum weight spanning trees in a weighted graph. Prim's Algorithm. Kruskal's Algorithm.

Lecture notes (printer-friendly). Recorded lecture. Further reading: Levin section 4.2.

The number of labeled trees and explicitly encoding such these labelled trees.

Lecture notes (plus additional examples) (printer-friendly). Recorded lecture.

I held an (optional but encouraged) review session on 21 May 2021 (PDF, printer-friendly).

I will hold open office hours for the last time on 24 May 2021.

Our final exam will take place Tuesday, 25 May 2021 from 10:25am – 12:25pm EDT in the usual Zoom room. See the official schedule for a complete list of maths exams (that page supercedes this one for exam times).