**Problem of the Week**

**Math Club**

**BUGCAT 2018**

**DST and GT Day**

**Number Theory Conf.**

**Zassenhaus Conference**

**Hilton Memorial Lecture**

You are here: Homepage » People » Graduate Students » Christopher Eppolito » Discrete Math (Spring 2019)

people:grads:eppolito:math314-02-s19

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.

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

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

- Disjunctive Normal Form and Conjunctive Normal Form
- Algebra of propositions (textbook section 3.4)
**Practice**: problem set 2**HW**: Read textbook section 3.6 (5 pages)

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

- Collected Written Homework 1
- 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)

- Quiz: Quotient-Remainder Theorem
- Using the Quotient-Remainder Theorem
- Modular Arithmetic
**HW**: Read my notes on basic number theory**Written Homework 2**: Complete this list of problems (Due 4 Mar 2019)

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

- Exam Review (led by guest lecturer David Cervantes Nava)
- Student questions on the Practice Exam

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

people/grads/eppolito/math314-02-s19.txt · Last modified: 2019/03/23 11:06 by eppolito

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