~~NOTOC~~ ====== Discrete Maths Section 1 (Spring 2020) ====== This is the official website of math314-01-s20.((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:coronavirus_syllabus_math314-01-s20.pdf|syllabus}}... Due to the COVID-19 pandemic, our course has gone entirely online. Please carefully read the updated syllabus and the site below. **THIS PAGE NO LONGER RECEIVES UPDATES** ===== General Information ===== **Meetings**: Meetings take place during our old class time (08:00 - 09:30 on MWF). **Office Hours**: By appointment on [[https://binghamton.zoom.us/|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 {{:people:grads:eppolito:coronavirus_syllabus_math314-01-s20.pdf|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 upload videos to replace some lectures. You are to watch these videos, take notes, and answer any questions posed in them.((If you have trouble viewing the videos through Safari, you can either [[https://brave.com/|use another browser]] or [[https://www.reddit.com/r/apple/comments/40b3y3/this_is_how_you_can_play_webm_in_safari/|try this solution from reddit]].)) **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 [[https://binghamton.zoom.us/|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 [[https://www.gradescope.com/|Gradescope]]; the company has made their service free-to-use for this semester. See the [[https://gradescope-static-assets.s3.amazonaws.com/help/submitting_hw_guide.pdf|Gradescope guide for students]] and watch the [[https://www.youtube.com/watch?v=KMPoby5g_nE&feature=youtu.be|Gradescope video on submitting homework]]. //I will not accept homework in any form other than PDF.// //I will not accept homework via email. Use [[https://www.gradescope.com/|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 {{:people:grads:eppolito:how_to_latex_math314-01-s20.pdf|how to use LaTeX}}; you can use its {{:people:grads:eppolito:how_to_latex_math314-01-s20.tex|source code}} as a startup template. The easiest way to get started is to make an account on [[https://www.overleaf.com/|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 [[https://play.google.com/store/apps/details?id=com.appxy.tinyscanner&hl=en_US|Android]] or [[https://apps.apple.com/us/app/scanner-app-scan-pdf-document/id595563753|iOS]]. 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 reference. ==== Participation ==== 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. ===== 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 === * Basic Logic and Sets * Sets and Set Operations * Rules of Inference * **Homework**: * Read textbook section 1.6 * Think about the {{:people:grads:eppolito:set_interpretations_math314-01-s20.pdf|relationship between the logic we know and the basic operations of set theory}}. === 31 January 2020 F === * Basic Logic and Sets * Natural Deduction * **Homework**: * {{:people:grads:eppolito:hw1_math314-01-s20.pdf|Complete these exercises (Due: 10 February 2020)}} * Enjoy the [[http://www.brainlesstales.com/images/2016/Feb/superb-owl.jpg|Superb Owl]]! (more information [[https://www.reddit.com/r/Superbowl/|here]] if you're unfamiliar) === 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**: * {{:people:grads:eppolito:hw1_math314-01-s20.pdf|Collected Homework 1}} * **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 [[https://www.khanacademy.org/computing/computer-science/cryptography/modern-crypt/v/diffie-hellman-key-exchange-part-1|this video]] from KhanAcademy.org. * Attempt problems from the textbook. === 14 February 2020 F === * Application: * RSA Cryptography * {{:people:grads:eppolito:rsa_math314-01-s20.pdf|RSA Problems}} * **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 [[https://www.youtube.com/watch?v=TUueMeRooBk|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 [[https://www.youtube.com/watch?v=K8ZfzNN1miQ|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). ==== Old Lecture Notes ==== 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. * {{notes_divisibility_math314-01-s20.pdf|Lecture Notes: Divisibility}}. * {{notes_modular_arithmetic_math314-01-s20.pdf|Lecture Notes: Modular Arithmetic}}. * {{notes_weak_induction_math314-01-s20.pdf|Lecture Notes: Weak Induction}}. * {{notes_strong_induction_math314-01-s20.pdf|Lecture Notes: Strong Induction}}. * {{notes_primes_and_factorization_math314-01-s20.pdf|Lecture Notes: Primes and Factorization}}. * {{notes_fibonacci_numbers_math314-01-s20.pdf|Lecture Notes: Fibonacci Numbers}}. * {{notes_counting_techniques_math314-01-s20.pdf|Lecture Notes: Counting Techniques}}. * {{notes_binomial_coefficients_math314-01-s20.pdf|Lecture Notes: Binomial Coefficients}}. ==== Week 9 (15 March 2020 -- 22 March 2020)==== * **Topics**: Enumeration * Pigeonhole Principle and Generalized Pigeonhole Principle * Textbook section 6.2. * {{pigeonhole_principle_math314-01-s20.pdf|Lecture notes on the Pigeonhole Principle}}. * {{http://people.math.binghamton.edu/grads/eppolito/generalized_pigeonhole_principle_video_math314-01-s20.webm|Video on the Generalized Pigeonhole Principle}}. * {{generalized_pigeonhole_principle_math314-01-s20.pdf|Lecture notes on the Generalized Pigeonhole Principle}}. * Anagrams * Textbook section 6.5. * {{counting_anagrams_math314-01-s20.pdf|Lecture notes}}. * {{http://people.math.binghamton.edu/grads/eppolito/counting_anagrams_video_math314-01-s20.webm|Video on counting anagrams}}. * {{counting_poker_hands_math314-01-s20.pdf|Counting Poker Hands}} (for practice; this is a different kind of [[https://www.youtube.com/watch?v=G_So72lFNIU|counting cards]]...). * **Homework**: * Submit a PDF to [[https://www.gradescope.com/|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 [[people/grads/eppolito/math314-01-s20#Homework|homework section]] for more information. * Complete these {{hw2-counting_math314-01-s20.pdf|counting problems}} (Due 27 March 2020). ==== Week 10 (22 March 2020 -- 28 March 2020) ==== * **Topics**: Functions and Relations. * Introduction to Relations * Textbook sections 9.1 and 9.3. * {{notes4_relations_math314-01-s20.pdf|Lecture notes}}. * [[https://www.youtube.com/watch?v=q0xN_N7l_Kw|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. * {{notes5_operations_on_relations.pdf|Lecture notes}}. * [[https://www.youtube.com/watch?v=Wrm1QO6Nc-4|Video on equivalence relations]] (this YouTube channel is also pretty nice!). * Functions * Textbook section 2.3. * {{functions_and_relations_math314-01-s20.pdf|Notes on functions and relations}}. * {{http://people.math.binghamton.edu/grads/eppolito/video_injective_functions_math314-01-s20.webm|Video on injective functions}}. * {{http://people.math.binghamton.edu/grads/eppolito/video_surjective_functions_math314-01-s20.webm|Video on surjective functions}}. * **Homework**: * Complete these {{hw3-functions_and_relations_math314-01-s20.pdf|homework problems}} (Due 13 April 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). * {{notes6_graph_theory_introduction_math314-01-s20.pdf|Lecture Notes: Introduction to Graphs}}. * {{notes7_handshake_lemma_math314-01-s20.pdf|Lecture Notes: Proof of the Handshake Lemma}}. * {{notes8_subgraphs_math314-01-s20.pdf|Lecture Notes: Subgraphs and Counting Subgraphs of $K_n$}}. * Connection in Graphs * Textbook section 10.4. * {{notes9_graph_connection_math314-01-s20.pdf|Lecture Notes: Graph Connection}}. ==== Spring Break (5 April 2020 -- 11 April 2020) ==== * **No Scheduled Meetings**. ==== Week 12 (12 April 2020 -- 18 April 2020) ==== * **Topics**: Graph Theory * Eulerian and Hamiltonian Graphs * Textbook section 10.5. * {{notes10_eulerian_and_hamiltonian_graphs_math314-01-s20.pdf|Lecture Notes on Eulerian and Hamiltonian Graphs}}. * Graph Coloring * Textbook section 10.8. * {{notes11_graph_coloring_math314-01-s20.pdf|Lecture Notes on Graph Coloring}}. ==== Week 13 (19 April 2020 -- 25 April 2020) ==== * **Topics**: Trees * Characterizing Trees * Textbook section 11.1. * {{notes12_tree_characterizations_math314-01-s20.pdf|Lecture Notes: Characterizing Trees}}. * Spanning Trees * Textbook sections 11.4 and 11.5. * {{notes13_spanning_trees_math314-01-s20.pdf|Lecture Notes: Spanning Trees}}. * Storing Labeled Trees * {{notes14_pruefer_code_math314-01-s20.pdf|Lecture Notes: Pruefer Code}}. * **Homework**: * Complete these {{hw4-graph_theory_math314-01-s20.pdf|graph theory problems}} (Due 8 May 2020). * //Optional//: Implement the Pruefer code algorithm and its inverse in your favorite programming language. ==== Week 14 (26 April 2020 -- 2 May 2020) ==== * **Topics**: Models of Computation * Finite State Machines * Textbook section 13.2. * {{notes15_finite_state_machines_math314-01-s20.pdf|Lecture Notes}}. * Deterministic Finite State Automata * Textbook section 13.3. * {{notes16_automata_math314-01-s20.pdf|Lecture Notes}}. * Noneterministic Finite State Automata * Textbook section 13.4. * {{notes17_nondeterministic_automata_math314-01-s20.pdf|Lecture Notes}}. ==== Week 15 (3 May 2020 -- 9 May 2020) ==== * **Review for Final**. ----- ==== FINAL EXAM ==== Due to the COVID-19 pandemic, final exams will be administered orally over Zoom. {{final_practice_math314-01-s20.pdf|Here a list of topics to guide your studying for your oral final}}.