Math 2001 Spring 20

MATH 2001: Introduction to Discrete Mathematics (Spring 2020)

Syllabus and details on accomodations, honor code, etc

Online meetings via Zoom

Starting Friday, March 13, all lectures and office hours for the foreseeable future will be held at their regular time via Zoom. See Canvas for the link.

Assignments

Update on grading (as of April 2, 2020)

Because of our change to remote teaching for the remaining semester and in order to avoid complications with taking exams remotely in fixed time periods, we will make the following changes: All these contributions add up to 60 points (instead of the original 100) and will then be used to determine the final grade.

Office hours:

Tuesday 3-4 pm, Wednesday 10-11 am

Schedule

Numbers refer to sections in Hammack, Book of Proof.
  1. 01/13: Gauss formula for 1+2+...+n, Euclid's proof for infinitely many primes
  2. 01/15: sets and elements, equality by Axiom of Extensionality (1.1), subsets (1.3), set builder notation (Axiom of Specification) (1.1)
  3. 01/17: Russell's paradox (1.10), Axiom of Replacement, cardinality (size) of sets (1.1)
  4. 01/22: unordered and ordered pairs (Axiom of Pairing), Cartesian products of 2 and more sets (1.2)
  5. 01/24: union (Axiom of Unions), intersection, difference, (1.5) complements (1.6), Venn diagrams (1.7)
  6. 01/27: proving inclusion and identities between sets, distributive law, de Morgan
  7. 01/31: indexed unions and intersections (1.8), power set (Axiom of Power Set), size of power set of a finite set (1.4)
  8. 02/03: logic statements, and, or, not (2.1), truthtables and logical equivalence (2.5)
  9. 02/05: implication, different formulations and negation (2.3)
  10. 02/07: if and only if (2.4), truthtables and Boolean functions
  11. 02/10: introduction to LaTeX, OverLeaf, first documents [tex], [pdf]
  12. 02/12: universal and existential quantifiers and their negations (2.7)
  13. 02/14: lists with and without repetition of elements, permutations, factorial (3.1, 3.2),
  14. 02/17: review for midterm [pdf]
  15. 02/19: MIDTERM
  16. 02/21: counting k-element subsets, binomial coefficients (3.5), Poison
  17. 02/24: Pascal's triangle (3.6), combinatorial proof (3.10)
  18. 02/26: Binomial Theorem (3.6), inclusion-exclusion (3.7)
  19. 02/28: integer solutions of x1+x2+...+xn = k, counting k-element multisets (3.8)
  20. 03/02: divisibility for integers (4.2), direct proof
  21. 03/04: greatest common divisor, least common multiple, Euclidean algorithm (4.2)
  22. 03/06: Bezout's identity, Die Hard, weighing coins
  23. 03/09: division algorithm, proof by contradiction
  24. 03/11: primes, Euclid's lemma, contrapositive proof
  25. 03/13: proof strategies (direct, contrapositive, contradiction, see handout `Proof strategies'), irrationality of the square root of 2 (Section 6 of handout `Integers')
  26. 03/16: integers modulo n, Diffie-Hellman key exchange (Section 7 of handout `Integers', [mp4])
  27. 03/18: induction proofs: sum 1+3+...+(2n-1), Binomial Theorem, Bernoulli's inequality (10.1) [pdf], [mp4]
  28. 03/20: strong induction, minimal counterexample: prime factorization of integers (10.1 and Section 8 of handout `Integers') [pdf], [mp4]
  29. 03/30: gcd and lcm via prime factorization (10, Section 8 of handout `Integers', last 2 slides on [pdf]), unstacking boxes[pdf], [mp4]
  30. 04/01: relations; functions, reflexive, symmetric, antisymmetric, transitive relations; partial orders, equivalence relations (11.2) (11.1, 11.2, 11.5 and Section 1 of handout `Relations')[pdf], [mp4]
  31. 04/03: equivalence classes and partitions (11.3 and Section 2 of handout `Relations') [pdf], [mp4]
  32. 04/06: integers modulo n, addition, multiplication well-defined (11.4) [pdf], functions, domain, codomain, range (12.1)

Homework

  1. due 01/15 [pdf] [tex]
  2. due 01/24 [pdf] [tex] [solution]
  3. due 01/31 [pdf] [tex] [solution]
  4. due 02/07 [pdf] [tex] [solution]
  5. due 02/14 [pdf] [tex] [solution]
  6. due 02/21 [pdf] [tex] part preparation for midterm 1 [solution]
  7. due 02/28 [pdf] [tex] [solution]
  8. due 03/06 [pdf] [tex] [solution]
  9. due 03/13 [pdf] [tex] [solution]
  10. due 03/20 [pdf] [tex] [solution]
  11. due 04/03 [pdf] [tex] [solution]
  12. due 04/10 [pdf] [tex]

Writing assignments

  1. due Monday 02/17 [pdf]
  2. first draft due 02/28 [pdf] [tex], final draft due 03/04, see comments [pdf]
  3. first draft due 03/16 [pdf] [tex], final draft due 03/20, 6 pm, see comments [pdf]
  4. first draft due 04/06 [pdf] [tex], final draft due 04/10

Texts

Richard Hammack. The Book of Proof. Creative Commons, 3rd edition, 2018. Available for free
Additional reading:

Handouts

  1. Axioms of Zermelo-Fraenkel set theory [pdf] [tex]
  2. How to show two sets are equal [pdf] [tex]
  3. Sets vs Logic [pdf] [tex]
  4. Combinatorics [pdf] [tex]
  5. Integers [pdf]
  6. Proof strategies [pdf] [tex]
  7. Relations [pdf] [tex]
  8. Functions [pdf] [tex]

Scientific writing

There is a variety of word-processing software for writing Mathematics. LaTeX is the most widespread. You can use it with many text editors or via some cloud-based service, like OverLeaf.

How to succeed in this class

  1. Go to class! It seems obvious, but learning the material in small portions 3 times a week is easier than reading up on it in some book by yourself. Always keep up with the topics. You also get nerdy Math jokes.
  2. Ask questions early and often! If you are not sure about something, ask about it immediately -- no matter whether in class, in office hours, or by mail. Do not assume that you can skip or figure out things later that you do not understand now. If you are missing the basics, you may fall behind and struggle with more complicated concepts later in class.
  3. Do the work! The only way to learn stuff is to try it yourself. Strive to do all the homework assignments. Some will be more challenging than others. If you are stuck on the hard ones, discuss them with colleagues or ask for possible hints in office hours or by mail.
  4. Learn from mistakes! Look at all feedback you get on graded homework, quizzes, exams, etc. Make sure you understand where you went wrong and how to get the correct solution. In particular revise all relevant graded work before exams.
  5. Organize in study groups! Meet with classmates a couple of times a week to discuss lectures and homework. Still write up your solutions to assignments when you are alone, never in a group.
  6. Take advantage of office hours! If you cannot make it to the official hours, ask to meet at some other time. Office hours are an additional resource for you to discuss stuff for which there is no time during class. Come prepared! Try to solve homework problems alone before you ask for help and be ready to explain your thoughts and where you are stuck.