User Tools

Site Tools


people:grads:eppolito:math314-02-s19

Discrete Math (Spring 2019)

This is the official website of math314-02-s19.1) Please read our syllabus

Our Midterm Exam is scheduled for 15 March 2019.

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

General Information

Meetings: Monday, Wednesday, Friday 8am - 9:30am in WH G02

Office Hours: Tuesday 10am - 1pm in WH236 (or by appointment in WH310)

Textbook: Mathematics for Computer Science (Lehman, Leighton, Meyer)

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.

Schedule

W 23 Jan 2019: (Class 1)

  • Discussed Syllabus
  • Brief introduction to propositional logic (what is meant by the terms statement, connective, etc.)
  • HW: Read textbook section 3.1 (4 pages)

F 25 Jan 2019: (Class 2)

  • Translation of English statements into the formal language
  • Truth tables (optional: read textbook section 3.2)
  • Practice: problem set 1
  • HW: Read textbook sections 3.3 and 3.4 (2 pages and 5 pages)

M 28 Jan 2019: (Class 3)

  • Quiz: Truth table construction
  • Validity, satisfiability, and logical equivalence
  • Developed several basic equivalences of propositional statements.

W 30 Jan 2019: (Class 4)

F 1 Feb 2019: (Class 5)

  • Quantified predicate logic (textbook section 3.6)

M 4 Feb 2019: (Class 6)

  • Basics of sets (textbook section 4.1)
  • Example proofs involving sets (direct proof)

W 6 Feb 2019: (Class 7)

  • More proofs of set theoretic identities (proof by cases, proof via a string of equivalent statements).
  • Introduced general relations (lots of examples)
  • Defined equivalence relations
  • HW: Read about functions and relations for Friday's class (caution: I'm NOT following the textbook here!)

F 8 Feb 2019: (Class 8)

  • Equivalence relations (many examples)
  • Introduction to functions (defined injective, surjective, and bijective)
  • Written Homework 1: Complete this list of problems (Due 15 Feb 2019)

M 11 Feb 2019: (Class 9)

  • Quiz: Equivalence relations
  • Images and preimages, right and left inverses (many examples)
  • Various propositions, examples, and practice problems concerning functions
  • HW: Read textbook section 5.1 through section 5.1.4 (5 pages)

W 13 Feb 2019: (Class 10)

  • Quiz: Functions and equivalence relations
  • Relationship between functions inverses and injectivity, surjectivity, and bijectivity
  • Introduction to the Principle of Mathematical Induction (textbook section 5.1.1-5.1.4)

F 15 Feb 2019: (Class 11)

  • Quiz: Induction and Well Ordering
  • More proofs by induction
  • A false proof by induction (to illustrate the importance of the base case)!
  • Number Theory: Properties of Divisibility (textbook section 9.1.1)

M 18 Feb 2019: (Class 12)

  • Recursion and the relationship to induction
  • Fibonacci numbers and relations therebetween (more induction proofs!)
  • Here is a list of cool problems involving Fibonacci numbers!

W 20 Feb 2019: (Class 13)

  • The Quotient-Remainder Theorem (i.e. the Division Algorithm, i.e. textbook Theorem 9.1.4 “The Division Theorem”)
  • Proof of the Quotient-Remainder Theorem (for the case n and d are natural numbers)
  • HW: Finish the proof of the Quotient-Remainder Theorem for n and d integers.

F 22 Feb 2019: (Class 14)

M 25 Feb 2019: (Class 15)

  • Greatest common divisor
  • Bezout's Identity (one proof given in this pdf)
  • Euclid's (Extended) Algorithm
  • Examples involving Euclid's Algorithm

W 27 Feb 2019: (Class 16)

  • Quiz: Modular Arithmetic and Euclid's Algorithm
  • Using Euclid's Algorithm to solve modular equations
  • Prime numbers
    • Definition
    • Prop: Every natural number n > 1 is divisible by some prime number.
    • Prop: There are infinitely many prime numbers.

F 1 Mar 2019: (Class 17)

  • Proved Euclid's Lemma
  • Proved the Fundamental Theorem of Arithmetic via Strong Induction (Exercise: Translate the proof into a Well Ordering Principle type of proof)
  • Introduced the Sieve of Eratosthenes
  • NB: I updated the number theory notes.

M 4 Mar 2019: (Class 18)

  • Collected Written Homework 2.
  • Computed the list of primes not exceeding 50 via the Seive of Eratosthenes.
  • Briefly discussed some ways of improving the Seive of Eratosthenes.
  • Discussed the RSA Cryptosystem (including a small example).
  • HW: Read textbook section 9.11 (on RSA Cryptography)

W 6 Mar 2019: (Class 19)

  • More work on RSA (try these problems).
  • HW (assigned in class, sent also by email): Let p = 11, q = 19, and e = 13.
    • What is the corresponding public key?
    • Encrypt m = 19 using RSA encryption.
    • Compute the private key d in this encryption scheme.
    • Decrypt an encoded message m' = 47 using RSA.
  • Question: Why does RSA work? (Answer: Euler's Totient Theorem!)
  • Set the stage to study Euler's Totient Function

F 8 Mar 2019: (Class 20)

  • Studied Euler's Totient Function, laying groundwork for the proof
  • Proof of Correctness of RSA (assuming Euler's Totient Theorem)
  • HW: Study for our Midterm Exam
    • Material for the Midterm stops at RSA
    • Know definitions and major theorems and be ready to use them
    • Be sure to look over your notes
    • By popular request, here is a practice midterm.
      • Disclaimer: The practice midterm DOES NOT pretend to be comprehensive, and I make no claims about its fitness as a study guide.

M 11 Mar 2019: (Class 21)

  • Exam Review (questions from students)
  • Proof of Euler's Totient Theorem
    • Remember that this implies correctness of the RSA Cryptosystem

NB: I leave for a visit to the IAS early Tuesday morning–I return after the midterm.

W 13 Mar 2019: (Class 22)

F 15 Mar 2019: Midterm Exam (in class)

  • Happy Spring Break! :/
    • HW: Read textbook sections 15.1 - 15.3 on basic counting techniques

HEADS UP: There might be some approximation error in anything labeled “Future”.

M 25 Mar 2019: (Class 23–Future)

  • Returned Midterm Exams
  • Basics of counting
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…
people/grads/eppolito/math314-02-s19.txt · Last modified: 2019/03/23 11:06 by eppolito