This is the official website of math314-01-s20.¹ Please read our syllabus…

Due to the COVID-19 pandemic, our course has gone entirely online. Please carefully read the updated syllabus and the site below.

THIS PAGE NO LONGER RECEIVES UPDATES

Meetings: Meetings take place during our old class time (08:00 - 09:30 on MWF).

Office Hours: By appointment on Zoom. Appointments should be made for reasonable times of the day (“reasonable” as defined by me).

Textbook: Discrete Mathematics and its Applications (8e) by Kenneth Rosen.

Grading: See the course syllabus for a grade distribution.

Content: Propositional logic, methods of proof, naive set theory, functions and relations, induction and recursion, counting, and basic graph theory.

Videos: I will upload videos to replace some lectures. You are to watch these videos, take notes, and answer any questions posed in them.²⁾

Notes: I will sometimes post PDFs for you to read. These are assigned reading; take notes on these PDFs, as they are fair game for homework and the final exam.

Readings: I will still assign reading from the textbook.

Problem Sessions: Roughly twice a week, I will host a problem session on Zoom during our old class meeting time. You are expected to attend these sessions.

Here is a quick look at what you will need to submit homework for the remainder of the course.

Homework is to be submitted as a PDF through Gradescope; the company has made their service free-to-use for this semester. See the Gradescope guide for students and watch the Gradescope video on submitting homework.

I will not accept homework in any form other than PDF.

I will not accept homework via email. Use Gradescope.

I offer you 1 homework bonus point per homework turned in using the LaTeX typesetting language; you must typeset exercises legibly. I wrote a short PDF on how to use LaTeX; you can use its source code as a startup template. The easiest way to get started is to make an account on Overleaf so you can view and compile .tex files; if you end up using LaTeX more frequently, you will probably want a different setup.

If you choose not to learn LaTeX, you can use a PDF scanning application to submit your homework. I think “Tiny Scanner” is nice; you can download it on your phone with either Android or iOS.

Here are documents on basic proof techniques and proof-writing style for your reference.

As a portion of your grade, you must contribute to our class notes. This can be done in one of the following two ways.

• Notes: Typing a portion of our notes from lectures (either one or two lectures).
• Project: Typing a short report on some topic related to our course.

All contributions must be approved by me in advance. The typing can be done either as plain-text or in $\LaTeX{}$; in either case students must discuss formatting with me before beginning their work.

• Review Syllabus
• Basic Logic and Sets
  • Propositions
  • Logical Connectives
• Homework:
  • Read textbook sections 1.1, 1.3.1 - 1.3.5

• Basic Logic and Sets
  • Translation of Sentences
  • Logical Equivalence
• Homework:
  • Read textbook sections 1.4 - 1.5

• Basic Logic and Sets
  • Predicates and Quantifiers
• Homework:
  • Read textbook sections 2.1 - 2.2 and 1.6

• Basic Logic and Sets
  • Sets and Set Operations
  • Rules of Inference
• Homework:
  • Read textbook section 1.6
  • Think about the relationship between the logic we know and the basic operations of set theory.

• Basic Logic and Sets
  • Natural Deduction
• Homework:
  • Complete these exercises (Due: 10 February 2020)
  • Enjoy the Superb Owl! (more information here if you're unfamiliar)

• Elementary Properties of Divisibility
  • Some careful mathematical proofs
• Homework:
  • Read textbook section 4.3; pay special attention to sections 4.3.2, 4.3.4, and 4.3.7-4.3.8.
  • Attempt problems from the textbook.
• Add\Drop Deadline is TODAY!

• Modular Arithmetic
  • Constructed $\mathbb{Z}/n\mathbb{Z}$
  • Studied more basic properties of divisibility
• Homework:
  • Read textbook section 4.4; pay special attention to sections 4.4.2 and 4.4.5.
  • Attempt problems from the textbook.

• sNOw Classes
  • Homework is still due on Monday.
  • Also still do the reading for Monday.

• Greatest Common Divisor
  • Euclid's Algorithm
• Modular Arithmetic
  • Units in $\mathbb{Z}/n\mathbb{Z}$
  • Solving Equations in $\mathbb{Z}/n\mathbb{Z}$
• Homework:
  • Collected Homework 1
  • Due Wednesday: Prove the following proposition.
    • Let $a \in \mathbb{Z}$ and $m \in \mathbb{Z}^+$. Integer $a$ is a unit modulo $m$ if and only if $\gcd(a, m) = 1$.
  • Attempt problems from the textbook.

• Primes and Factorization
  • Prime numbers and prime sieves
  • Fundamental Theorem of Arithmetic
• Homework:
  • Read textbook section 4.6
  • Watch this video from KhanAcademy.org.
  • Attempt problems from the textbook.

• Application:
  • RSA Cryptography
  • RSA Problems
• Homework:
  • Read textbook section 5.1.
  • Attempt problems from the textbook.

• Mathematical Induction
  • Introduction (with dominoes!)
  • Many simple examples
• Homework:
  • Attempt problems from the textbook.

• Mathematical Induction
  • Fibonacci Numbers
  • More proofs by induction
• Homework:
  • Attempt problems from the textbook.

• Review Session for Exam 1
  • Student questions only
• Homework: Study!!!

• Midterm Exam 1 (In Class)

• Mathematical Induction
  • Review of Weak Induction
  • Strong Induction
• Homework:
  • Read textbook section 5.2
  • Watch this video on strong induction examples.
  • Attempt problems from the textbook.

• Mathematical Induction
  • More Strong Induction
  • The Well Ordering Principle
• Homework:
  • Due Monday: Find (with proof!) all integers of the form $n = 5s + 9t$ for some $s, t \in \mathbb{N}$.
  • Read textbook section 5.3
  • Watch this video on comparing weak induction, strong induction, and well ordering (you can stop watching around the 5:45 marker).
  • Attempt problems from the textbook.

• Recursion
  • Some interesting relationships among on Fibonacci numbers
  • NB: Recursion is an extremely important concept; much of what we do in the rest of the course requires understanding this fundamental topic…
• Homework:
  • Due Wednesday: Prove that every Fibonacci number with odd index (i.e. $f_{2k+1}$ for $k \in \mathbb{N}$) can be expressed as a sum of squares of Fibonacci numbers.
  • Read textbook section 6.1
  • Attempt problems from the textbook.

• Enumeration
  • Cardinality of Sets
  • Basic Counting Techniques
    • Product Principle: If $A$ and $B$ are finite sets, then $\#(A \times B) = \#A \cdot \#B$.
    • Sum Principle: If $A$ and $B$ are disjoint finite sets, then $\#(A \cup B) = \#A + \#B$.
      • NB: Take note that $A$ and $B$ must be disjoint!
    • Correspondence Principle: Let $A$ and $B$ be finite sets. If there is a rule of assignment $R \subseteq A \times B$ such that both $A = \{a : (a, b) \in R \text{ for some } b \in B\}$ and $\#\{b : (a, b) \in R\} = 1$ for all $a \in A$, and $B = \{b : (a, b) \in R \text{ for some } a \in A\}$ and $\#\{a : (a, b) \in R\} = 1$ for all $b \in B$, then $\#A = \#B$.
  • Many Examples
• Homework:
  • Read textbook sections 6.3 and 6.4
  • Attempt problems from the textbook.

• No Class (Winter Break)

• Enumeration
  • Binomial Coefficients
    • Proved several identities via counting
  • Binomial Theorem: Let $n \in \mathbb{N}$. For all $x, y \in \mathbb{R}$ we have $(x + y)^n = \sum_{k = 0}^n \binom{n}{k} x^k y^{n-k}$.
• Homework:
  • Read section 8.5 (NB: Yes, I mean “8.5”; it is not a typo)
  • Due Wednesday Give two proofs that for all $n \in \mathbb{Z}^+$ we have $\sum_{k = 0}^n (-1)^k \binom{n}{k} = 0$.
    • Use the Binomial Theorem.
    • Use a direct counting argument (Hint: move the negative terms to the other side before you start counting).
  • Attempt problems from the textbook.

• Enumeration
  • Inclusion-Exclusion Principle: For all finite sets $A$ and $B$ we have $\#(A \cup B) = \#A + \#B - \#(A \cap B)$.
    • NB: Compare this with the Sum Principle…
• Homework:
  • Attempt problems from the textbook.

• Enumeration
  • NB: This lecture taught over Zoom.
  • Problem session on enumeration.
• Homework:
  • Attempt problems from the textbook.

In response to the COVID-19 pandemic, the remainder of the course went online. I have grouped the remainder of the semester by week (because this is more natural for an online course).

Here are lecture notes taken and plain-text typed by students–with editing and further LaTeX formatting done by me–for lectures before the class went online.

• Lecture Notes: Divisibility.
• Lecture Notes: Modular Arithmetic.
• Lecture Notes: Weak Induction.
• Lecture Notes: Strong Induction.
• Lecture Notes: Primes and Factorization.
• Lecture Notes: Fibonacci Numbers.
• Lecture Notes: Counting Techniques.
• Lecture Notes: Binomial Coefficients.

• Topics: Enumeration
  • Pigeonhole Principle and Generalized Pigeonhole Principle
    • Textbook section 6.2.
    • Lecture notes on the Pigeonhole Principle.
    • Video on the Generalized Pigeonhole Principle.
    • Lecture notes on the Generalized Pigeonhole Principle.
  • Anagrams
    • Textbook section 6.5.
    • Lecture notes.
    • Video on counting anagrams.
  • Counting Poker Hands (for practice; this is a different kind of counting cards…).
• Homework:
  • Submit a PDF to Gradescope with the text “This is a test homework. I took this opportunity to familiarize myself with Gradescope and making PDF submissions.” (Due 23 March 2020)
    • See the homework section for more information.
  • Complete these counting problems (Due 27 March 2020).

• Topics: Functions and Relations.
  • Introduction to Relations
    • Textbook sections 9.1 and 9.3.
    • Lecture notes.
    • Video on relations: reflexive, symmetric, and transitive (PS. this guy's videos are pretty great!).
  • Equivalence Relations and Closures
    • Textbook sections 9.5 and 9.4.
    • Lecture notes.
    • Video on equivalence relations (this YouTube channel is also pretty nice!).
  • Functions
    • Textbook section 2.3.
    • Notes on functions and relations.
    • Video on injective functions.
    • Video on surjective functions.
• Homework:
  • Complete these homework problems (Due 13 April 2020).

• Topics: Graph Theory.
  • Introduction to Graphs
    • Textbook sections 10.1 – 10.3 (just for reference, see the lecture first).
    • Lecture Notes: Introduction to Graphs.
    • Lecture Notes: Proof of the Handshake Lemma.
    • Lecture Notes: Subgraphs and Counting Subgraphs of $K_n$.
  • Connection in Graphs
    • Textbook section 10.4.
    • Lecture Notes: Graph Connection.

• No Scheduled Meetings.

• Topics: Graph Theory
  • Eulerian and Hamiltonian Graphs
    • Textbook section 10.5.
    • Lecture Notes on Eulerian and Hamiltonian Graphs.
  • Graph Coloring
    • Textbook section 10.8.
    • Lecture Notes on Graph Coloring.

• Topics: Trees
  • Characterizing Trees
    • Textbook section 11.1.
    • Lecture Notes: Characterizing Trees.
  • Spanning Trees
    • Textbook sections 11.4 and 11.5.
    • Lecture Notes: Spanning Trees.
  • Storing Labeled Trees
    • Lecture Notes: Pruefer Code.
• Homework:
  • Complete these graph theory problems (Due 8 May 2020).
  • Optional: Implement the Pruefer code algorithm and its inverse in your favorite programming language.

• Topics: Models of Computation
  • Finite State Machines
    • Textbook section 13.2.
    • Lecture Notes.
  • Deterministic Finite State Automata
    • Textbook section 13.3.
    • Lecture Notes.
  • Noneterministic Finite State Automata
    • Textbook section 13.4.
    • Lecture Notes.

• Review for Final.

Due to the COVID-19 pandemic, final exams will be administered orally over Zoom.

Here a list of topics to guide your studying for your oral final.