**Problem of the Week**

**Math Club**

**BUGCAT 2019**

**DST and GT Day**

**Number Theory Conf.**

**Zassenhaus Conference**

**Hilton Memorial Lecture**

You are here: Homepage » People » Graduate Students » Christopher Eppolito » Discrete Maths Section 1 (Spring 2020)

people:grads:eppolito:math314-01-s20

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

**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.^{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.

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

- Basic Logic and Sets
- Natural Deduction

**Homework**:- 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**:**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

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

**Topics**: Enumeration- Pigeonhole Principle and Generalized Pigeonhole Principle
- Textbook section 6.2.

- 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)
- 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.
- 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.
- Video on equivalence relations (this YouTube channel is also pretty nice!).

- Functions
- Textbook section 2.3.

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

- Connection in Graphs
- Textbook section 10.4.

**No Scheduled Meetings**.

**Topics**: Graph Theory- Eulerian and Hamiltonian Graphs
- Textbook section 10.5.

- Graph Coloring
- Textbook section 10.8.

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

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

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

people/grads/eppolito/math314-01-s20.txt · Last modified: 2020/05/04 23:36 by eppolito

Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Noncommercial-Share Alike 3.0 Unported