### Sidebar

people:grads:eppolito:math314-01-s20

# Discrete Maths Section 1 (Spring 2020)

This is the official website of math314-01-s20.1) 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.

## General Information

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.

### Content Delivery

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

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.

### Homework

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

#### Submission

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.

#### Miscellany

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.

### Participation

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.

## Schedule

#### 22 January 2020 W

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

#### 24 January 2020 F

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

#### 27 January 2020 M

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

#### 29 January 2020 W

• Basic Logic and Sets
• Sets and Set Operations
• Rules of Inference
• Homework:
• Read textbook section 1.6

#### 31 January 2020 F

• Basic Logic and Sets
• Natural Deduction
• Homework:

#### 3 February 2020 M

• 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!

#### 5 February 2020 W

• 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.

#### 7 February 2020 F

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

#### 10 February 2020 M

• Greatest Common Divisor
• Euclid's Algorithm
• Modular Arithmetic
• Units in $\mathbb{Z}/n\mathbb{Z}$
• Solving Equations in $\mathbb{Z}/n\mathbb{Z}$
• Homework:
• 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.

#### 12 February 2020 W

• 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.

#### 14 February 2020 F

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

#### 17 February 2020 M

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

#### 19 February 2020 W

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

#### 21 February 2020 F

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

#### 24 February 2020 M

• Midterm Exam 1 (In Class)

#### 26 February 2020 W

• 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.

#### 28 February 2020 F

• 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.

#### 2 March 2020 M

• 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.

#### 4 March 2020 W

• 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.

#### 6 March 2020 F

• No Class (Winter Break)

#### 9 March 2020 M

• 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.

#### 11 March 2020 W

• 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.

#### 13 March 2020 F

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

#### Note on Coronavirus Changes

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).

### Old Lecture Notes

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.

### Week 9 (15 March 2020 -- 22 March 2020)

• Topics: Enumeration
• Pigeonhole Principle and Generalized Pigeonhole Principle
• Anagrams
• Textbook section 6.5.
• 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)
• Complete these counting problems (Due 27 March 2020).

### Week 11 (29 March 2020 -- 4 April 2020)

• Topics: Graph Theory.
• Introduction to Graphs
• Textbook sections 10.1 – 10.3 (just for reference, see the lecture first).
• Connection in Graphs
• Textbook section 10.4.

### Spring Break (5 April 2020 -- 11 April 2020)

• No Scheduled Meetings.

### Week 12 (12 April 2020 -- 18 April 2020)

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

### Week 13 (19 April 2020 -- 25 April 2020)

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

### Week 14 (26 April 2020 -- 2 May 2020)

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

### Week 15 (3 May 2020 -- 9 May 2020)

• Review for Final.

### FINAL EXAM

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

1) If you have an idea to improve this space, please email eppolito-at-math-dot-binghamton-dot-edu with your suggestion; I would like this space to be as useful to students as possible…
2) If you have trouble viewing the videos through Safari, you can either use another browser or try this solution from reddit.
people/grads/eppolito/math314-01-s20.txt · Last modified: 2020/05/04 23:36 by eppolito