people:grads:eppolito:math314-02-s19
Differences
This shows you the differences between two versions of the page.
|
people:grads:eppolito:math314-02-s19 [2019/03/29 16:21] eppolito Updated classes 22-26 |
people:grads:eppolito:math314-02-s19 [2022/08/21 14:28] (current) eppolito [Discrete Math (Spring 2019)] final update |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| + | ====== Discrete Math (Spring 2019) ====== | ||
| + | |||
| + | This is the official website of math314-02-s19.((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...)) Please read our {{:people:grads:eppolito:syllabus.pdf|syllabus}}... | ||
| + | |||
| + | **Our Final Exam is scheduled for 13 May 2019.** | ||
| + | |||
| + | Here are documents on {{:people:grads:eppolito:inference_rules.pdf|basic proof techniques}} and {{:people:grads:eppolito:proof_style.pdf|proof-writing style}} for your own reference. | ||
| + | |||
| + | |||
| + | **THIS PAGE NO LONGER RECEIVES UPDATES** | ||
| + | ===== 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**: [[https://courses.csail.mit.edu/6.042/spring18/mcs.pdf|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 (C1) ==== | ||
| + | * 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 (C2) ==== | ||
| + | * Translation of English statements into the formal language | ||
| + | * Truth tables (optional: read textbook section 3.2) | ||
| + | * **Practice**: {{:people:grads:eppolito:practice1.pdf|problem set 1}} | ||
| + | * **HW**: Read textbook sections 3.3 and 3.4 (2 pages and 5 pages) | ||
| + | |||
| + | ==== M 28 Jan (C3) ==== | ||
| + | * Quiz: Truth table construction | ||
| + | * Validity, satisfiability, and logical equivalence | ||
| + | * Developed several basic equivalences of propositional statements. | ||
| + | |||
| + | ==== W 30 Jan (C4) ==== | ||
| + | * Disjunctive Normal Form and Conjunctive Normal Form | ||
| + | * Algebra of propositions (textbook section 3.4) | ||
| + | * {{:people:grads:eppolito:logical_equivalence.pdf|Basic rules of equivalence}} | ||
| + | * **Practice**: {{:people:grads:eppolito:practice2.pdf|problem set 2}} | ||
| + | * **HW**: Read textbook section 3.6 (5 pages) | ||
| + | |||
| + | ==== F 1 Feb (C5) ==== | ||
| + | * Quantified predicate logic (textbook section 3.6) | ||
| + | |||
| + | ==== M 4 Feb (C6) ==== | ||
| + | * Basics of sets (textbook section 4.1) | ||
| + | * Example proofs involving sets (direct proof) | ||
| + | |||
| + | ==== W 6 Feb (C7) ==== | ||
| + | * 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 {{:people:grads:eppolito:functions_and_relations.pdf|functions and relations}} for Friday's class (caution: I'm NOT following the textbook here!) | ||
| + | |||
| + | ==== F 8 Feb (C8) ==== | ||
| + | * Equivalence relations (many examples) | ||
| + | * Introduction to functions (defined injective, surjective, and bijective) | ||
| + | * **Written Homework 1**: Complete this {{:people:grads:eppolito:hw1.pdf|list of problems}} (Due 15 Feb 2019) | ||
| + | |||
| + | ==== M 11 Feb (C9) ==== | ||
| + | * Quiz: Equivalence relations | ||
| + | * Images and preimages, right and left inverses (many examples) | ||
| + | * Various {{:people:grads:eppolito:functions_and_relations.pdf|propositions, examples, and practice problems}} concerning functions | ||
| + | * **HW**: Read textbook section 5.1 through section 5.1.4 (5 pages) | ||
| + | |||
| + | ==== W 13 Feb (C10) ==== | ||
| + | * 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 (C11) ==== | ||
| + | * Collected {{:people:grads:eppolito:hw1.pdf|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 (C12) ==== | ||
| + | * Recursion and the relationship to induction | ||
| + | * Fibonacci numbers and relations therebetween (more induction proofs!) | ||
| + | * Here is a {{:people:grads:eppolito:fibonacci_numbers.pdf|list of cool problems}} involving Fibonacci numbers! | ||
| + | |||
| + | ==== W 20 Feb (C13) ==== | ||
| + | * 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 (C14) ==== | ||
| + | * Quiz: Quotient-Remainder Theorem | ||
| + | * Using the Quotient-Remainder Theorem | ||
| + | * Modular Arithmetic | ||
| + | * **HW**: Read my {{:people:grads:eppolito:number_theory.pdf|notes on basic number theory}} | ||
| + | * **Written Homework 2**: Complete this {{:people:grads:eppolito:hw2.pdf|list of problems}} (Due 4 Mar 2019) | ||
| + | |||
| + | ==== M 25 Feb (C15) ==== | ||
| + | * Greatest common divisor | ||
| + | * Bezout's Identity (one proof given in {{:people:grads:eppolito:number_theory.pdf|this pdf}}) | ||
| + | * Euclid's (Extended) Algorithm | ||
| + | * Examples involving Euclid's Algorithm | ||
| + | |||
| + | ==== W 27 Feb (C16) ==== | ||
| + | * 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 (C17) ==== | ||
| + | * 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 {{:people:grads:eppolito:number_theory.pdf|number theory notes}}. | ||
| + | |||
| + | ==== M 4 Mar (C18) ==== | ||
| + | * Collected {{:people:grads:eppolito:hw2.pdf|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 (C19) ==== | ||
| + | * More work on RSA ({{:people:grads:eppolito:rsa.pdf|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 (C20) ==== | ||
| + | * 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 {{:people:grads:eppolito:practice_midterm.pdf|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 (C21) ==== | ||
| + | * 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 (C22) ==== | ||
| + | * Exam Review (led by guest lecturer David Cervantes Nava) | ||
| + | * Student questions on the Practice Exam | ||
| + | * {{:people:grads:eppolito:practice_midterm_solutions.pdf|Here are solutions to the practice midterm}} | ||
| + | |||
| + | ==== F 15 Mar--Midterm Exam (in class) ==== | ||
| + | * Happy Spring Break! :-/ | ||
| + | * **HW**: Read textbook sections 15.1 - 15.3 on basic counting techniques | ||
| + | |||
| + | ==== M 25 Mar (C23) ==== | ||
| + | * Returned Midterm Exams | ||
| + | * {{:people:grads:eppolito:counting_principles.pdf|Basics of counting}} | ||
| + | * Addition Principle | ||
| + | * Product Principle | ||
| + | * Bijective Counting | ||
| + | |||
| + | ==== W 27 Mar (C24) ==== | ||
| + | * More counting (with many examples and some recursive counting) | ||
| + | |||
| + | ==== F 29 Mar (C25) ==== | ||
| + | * Problem session on basic counting techniques | ||
| + | * Counting with binomial coefficients | ||
| + | * **HW**: Finish the in-class problems for Monday | ||
| + | * **HW**: Complete {{:people:grads:eppolito:counting_poker_hands.pdf|these problems}} for 5 Apr. | ||
| + | |||
| + | ==== M 1 Apr (C26) ==== | ||
| + | * More counting with binomial coefficients | ||
| + | * Algebraic Formula for the binomial coefficients | ||
| + | * Counting anagrams of a word | ||
| + | * Learned the methods "Count Dracula" and the method of Monte Cristo((APRIL FOOLS!)) | ||
| + | |||
| + | ==== T 2 Apr--Withdrawal Deadline ==== | ||
| + | |||
| + | ==== W 3 Apr (C27) ==== | ||
| + | * Quiz: Binomial coefficients and counting | ||
| + | * {{:people:grads:eppolito:counting_principles.pdf|More advanced counting techniques}} | ||
| + | * Inclusion-Exclusion Principle | ||
| + | * Pigeonhole Principle | ||
| + | * More counting! | ||
| + | |||
| + | ==== F 5 Apr (C28) ==== | ||
| + | * Quiz: Pigeonhole principle | ||
| + | * Collected Homework on counting poker hands | ||
| + | * Simple graphs (textbook chapter 12) | ||
| + | * Basic definitions | ||
| + | * Many examples (the Petersen graph is my favorite) | ||
| + | * Handshake Lemma | ||
| + | |||
| + | ==== M 8 Apr (C29) ==== | ||
| + | * Quiz: examples of simple graphs | ||
| + | * {{:people:grads:eppolito:graph_matchings.pdf|Matchings in graphs}} | ||
| + | * Examples | ||
| + | * Basic results | ||
| + | * Hall's Marriage Theorem for bipartite graphs | ||
| + | * Statement | ||
| + | * Proof of sufficiency | ||
| + | |||
| + | ==== W 10 Apr (C30) ==== | ||
| + | * Quiz: perfect matchings | ||
| + | * Hall's Marriage Theorem | ||
| + | * Proof of necessity | ||
| + | * **Written Homework 3**: Complete this {{:people:grads:eppolito:hw3.pdf|list of problems}} (due 26 Apr 2019) | ||
| + | |||
| + | ==== F 12 Apr (C31) ==== | ||
| + | * Quiz: Hall's Marriage Theorem | ||
| + | * Algorithms to compute matchings in bipartite graphs | ||
| + | * Algorithm suggested by Hall's Marriage Theorem | ||
| + | * Augmenting Paths Algorithm | ||
| + | * Connection in graphs | ||
| + | |||
| + | ==== M 15 Apr (C32) ==== | ||
| + | * Quiz: Augmenting Paths Algorithm | ||
| + | * Graph coloring | ||
| + | * Many examples | ||
| + | * Basic properties | ||
| + | |||
| + | ==== W 17 Apr (C33) ==== | ||
| + | * Quiz | ||
| + | * More graph coloring | ||
| + | * Brooks's Theorem | ||
| + | * Every finite simple graph has chromatic number bounded above by one more than its maximum degree. | ||
| + | |||
| + | ==== F 19 Apr No Classes :/ ==== | ||
| + | |||
| + | ==== M 22 Apr (C34) ==== | ||
| + | * {{:people:grads:eppolito:graph_theory_quiz.pdf|Group Quiz}} (discussion led by guest lecturer Kunle Abawonse) | ||
| + | * {{:people:grads:eppolito:graph_theory_quiz_solutions.pdf|Solutions to these problems}} | ||
| + | |||
| + | ==== W 24 Apr (C35) ==== | ||
| + | * Quiz: Graph coloring | ||
| + | * More on connection in graphs | ||
| + | * Reducing problems on graphs to problems on their connected components | ||
| + | * **Exercise**: Prove that the chromatic number of a graph is the maximum of the chromatic numbers of its components. | ||
| + | * Eulerian graphs (short introduction) | ||
| + | |||
| + | ==== F 26 Apr (C36) ==== | ||
| + | * Quiz: Euler trails | ||
| + | * {{:people:grads:eppolito:hw3.pdf|Collected Homework 3}} | ||
| + | * Eulerian graphs | ||
| + | * Proved Euler's characterization of Eulerian graphs | ||
| + | * A graph has an Euler trail if and only if it has at most one component with edges and at most two vertices of odd degree. | ||
| + | * Hamiltonian graphs | ||
| + | * No nice equivalent conditions are known | ||
| + | * **Homework**: Does the Petersen graph have a Hamilton cycle? | ||
| + | * {{:people:grads:eppolito:petersen_is_not_hamiltonian.pdf|Solution is in this pdf}} | ||
| + | * [[https://en.wikipedia.org/wiki/Leonhard_Euler|You should read about Leonhard Euler...]] | ||
| + | |||
| + | ==== M 29 Apr (C37) ==== | ||
| + | * Quiz | ||
| + | * Trees (Textbook section 12.11) | ||
| + | * Equivalent descriptions of trees | ||
| + | * Spanning trees | ||
| + | * Minimum weight spanning trees | ||
| + | * Kruskal's Algorithm | ||
| + | |||
| + | ==== W 1 May (C38) ==== | ||
| + | * Quiz: Kruskal's Algorithm | ||
| + | * Algorithms and state machines (Textbook chapter 6) | ||
| + | * State machine definitions and examples | ||
| + | * Evaluations | ||
| + | * Preserved Invariant Lemma (Textbook "Preserved Invariant Principle") | ||
| + | * Here are {{:people:grads:eppolito:state_machines_and_algorithms.pdf|my notes on state machines}}. | ||
| + | ==== F 3 May (C39) ==== | ||
| + | * Quiz | ||
| + | * More algorithms and state machines | ||
| + | * Examples encoding algorithms into state machines | ||
| + | * Examples interpreting state machines as algorithms | ||
| + | |||
| + | ==== M 6 May (C40) ==== | ||
| + | * The fast exponentiation algorithm | ||
| + | * State machine model | ||
| + | * Proof of correctness | ||
| + | |||
| + | ==== W 8 May (C41) ==== | ||
| + | * Review for Final | ||
| + | * Student questions | ||
| + | * Gave comment forms | ||
| + | |||
| + | ==== F 10 May (C42) ==== | ||
| + | * Review for Final | ||
| + | * Student questions | ||
| + | * I will hold extra office hours today! | ||
| + | * **Room**: WH 236 | ||
| + | * **Time**: 11am - 4pm | ||
| + | |||
| + | ---- | ||
| + | |||
| + | ==== FINAL EXAM ==== | ||
| + | * **Date**: Monday 13 May 2019 | ||
| + | * **Time**: 8am - 10am | ||
| + | * **Room**: S1 149 | ||