User Tools

Site Tools


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: One problem session will be announced weekly; unless otherwise noted, these meetings take place during our old class time (08:00 - 09:30 on MWF).

Office Hours: Monday, Friday 10:00 - 13:00 on Zoom (or by appointment on Zoom).

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 soon begin uploading videos to replace our lectures. I expect you to watch these videos, to take notes, and to answer any questions posed in them. Video updates should be relatively frequent (at least twice a week).2)

Notes: I will sometimes post a PDF for you to read. You are to treat this as 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.

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

31 January 2020 F

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

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

Week 10 (22 March 2020 -- 28 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.
    • Eulerian and Hamiltonian Graphs
      • Textbook section 10.5.
  • Homework:

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

  • No Scheduled Meetings.

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

  • Topics: Graph Theory
    • [Spill-over of topics from Week 11]
    • Graph Coloring
      • Textbook section 10.8.
    • Shortest Paths
      • Textbook section 10.6 (time permitting).
    • Planar Graphs
      • Textbook section 10.7 (time permitting).
  • Homework:

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.
    • Applications of Trees
      • Textbook sections 11.2 and 11.3.
  • Homework:

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

  • Topics: Finite State Machines and Algorithms
    • Finite State Machines
      • Textbook sections 13.2 and 13.3.
    • Turing Machines
      • Textbook section 13.5.
  • Homework:

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

  • Review for Final.

FINAL EXAM

Due to the COVID-19 pandemic, the final exam is TBA. I will provide details as soon as possible.

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/03/28 19:18 by eppolito