MATH 2001: Introduction to Discrete Mathematics (Fall 2020)

Final Exam:

• T 2:15-3:00 pm
• W 9:15-10:00 am
• W 1:30 - 2:15 pm

• You are allowed to use lecture notes and the textbook. Still prepare for the exam like for the closed book midterms.
• You are NOT allowed to discuss the problems with other people or search the internet.
• You can start the exam on Canvas any time between Wednesday, 12/09, 4 pm, and Saturday, 12/12, 1:30 pm.
• Once you start the exam, you have 150 minutes to solve the problems on paper, scan the solutions and upload them to Canvas.
• Before starting, read these explanations on how to take a timed take-home exam on Canvas: link
• In case you lose internet connectivity or any other problem occurs before you can upload the solutions, email me the scanned solutions as soon as possible.

Schedule

1. 08/24: Gauss formula for 1+2+...+n, Euclid's proof for infinitely many primes
2. 08/26: sets and elements, equality by Axiom of Extensionality (1.1), subsets (1.3), empty set is a subset of any set
3. 08/28: set builder notation, Axiom of Specification (1.1), Russell's paradox (1.10), Axiom of Replacement, cardinality (size) of sets (1.1)
4. 08/31: unordered and ordered pairs (Axiom of Pairing), Cartesian products of 2 and more sets (1.2)
5. 09/02: Axiom of Power Set, size of power set of a finite set (1.4), union (Axiom of Unions), intersection, difference, (1.5) complements (1.6), Venn diagrams (1.7)
6. 09/04: laws of set operations, proving inclusion between sets
7. 09/09: proving equality between sets, indexed unions and intersections (1.8)
8. 09/11: review of Zermelo-Fraenkel set theory, logical statements, and, or, not (2.1), truth tables
9. 09/14: implication, different formulations and negation (2.3), logical equivalence (2.5)
10. 09/16: if and only if (2.4), truth tables and Boolean functions
11. 09/18: universal and existential quantifiers and their negations (2.7)
12. 09/21: introduction to LaTeX, OverLeaf, first documents [tex], [pdf]
13. 09/23: logic review, worksheet on negations
14. 09/25: multiple quantifiers as game with spoiler and duplicator, counting lists with and without repetition of elements (3.1, 3.2)
15. 09/28: review for midterm [pdf]
16. 09/30: MIDTERM 1
17. 10/02: review of midterm, permutations, factorial (3.4)
18. 10/05: counting k-element subsets by binomial coefficients (3.5), Poison
19. 10/07: Binomial Theorem (3.6), inclusion-exclusion (3.7)
20. 10/09: integer solutions of x1+x2+...+xn = k, counting k-element multisets (3.8)
21. 10/12: combinatorics review, lists with/without repetition where order matters/does not matter
22. 10/14: divisibility for integers (4.2), direct proof, greatest common divisor
23. 10/16: Euclidean algorithm (4.2), Bezout's identity (Prop 7.1), Die Hard
24. 10/19: least common multiple, division algorithm, proof by contradiction
25. 10/21: primes, Euclid's lemma, contrapositive proof, weighing coins
26. 10/23: proof strategies (direct, contrapositive, contradiction, see handout `Proof strategies'), irrationality of the square root of 2 (6.1)
27. 10/26: integers modulo n, Diffie-Hellman key exchange (Section 7 of handout `Integers')
28. 10/28: induction proofs: sum 1+3+...+(2n-1), Binomial Theorem, Bernoulli's inequality (10.1)
29. 10/30: strong induction, minimal counterexample: prime factorization of integers (10.1 and Section 8 of handout `Integers')
30. 11/02: gcd and lcm via prime factorization (10, Section 8 of handout `Integers'), review for midterm [pdf]
31. 11/04: MIDTERM 2
32. 11/06: discussion of midterm, strong induction, unstacking boxes
33. 11/09: relations: functions, reflexive, symmetric, antisymmetric, transitive relations, partial orders, equivalence relations (11.1, 11.2, 11.5 and Section 1 of handout `Relations')[pdf]
34. 11/11: equivalence classes and partitions (11.3 and Section 2 of handout `Relations') [pdf]
35. 11/13: integers modulo n, addition, multiplication well-defined (11.4) [pdf]
36. 11/16: functions, domain, codomain, range (12.1), image, preimage of a set (12.6), injective, surjective, bijective functions (12.2, Section 1 of handout `Functions') [pdf]
37. 11/18: pigeonhole principle (12.3) (Section 2 of handout `Functions') [pdf]
38. 11/20: counting all/injective/surjective functions on finite sets, composition (12.4) (Sections 3 of handout `Functions') [pdf]
39. 11/23: inverse relations and functions (12.5) (Section 4 of handout `Functions') [pdf]
40. 11/25: inverse functions
41. 11/30: cardinality of sets via bijections, |N| = |Z| (14.1), |R| = |[0,1]|, countably and uncountably infinite, Cantor's diagonal argument, |N| = |Q| (14.2), Continuum Hypothesis (14.4) [pdf]
42. 12/02: Review: Zermelo-Fraenkel Set Theory, Axiom of Choice [pdf], worksheet on sets
43. 12/04: Review: proving and disproving quantified statements [pdf]
44. 12/07: Review: Integers mod n, invertible elements [pdf], worksheet on equivalences

Homework

0. due 08/26 [pdf] [tex]
1. due 09/04 [pdf] [tex], solutions [pdf]
2. due 09/11 [pdf] [tex], solutions [pdf]
3. due 09/18 [pdf] [tex], solutions [pdf]
4. due 09/25 [pdf] [tex], solutions [pdf]
5. due 10/02 [pdf] [tex] part preparation for midterm 1, solutions [pdf]
6. due 10/09 [pdf] [tex], solutions [pdf]
7. due 10/16 [pdf] [tex], solutions [pdf]
8. due 10/23 [pdf] [tex], solutions [pdf]
9. due 10/30 [pdf] [tex], solutions [pdf]
10. due 11/06 [pdf] [tex] part preparation for midterm 2, solutions [pdf]
11. due 11/13 [pdf] [tex], solutions [pdf]
12. due 11/20 [pdf] [tex], solutions [pdf]
13. due 12/04 [pdf] [tex], solutions [pdf]

Writing assignments

0. due Monday 09/28, upload source code *.tex and compiled file *.pdf to Canvas [pdf]
1. first draft due 10/12 [pdf] [tex], final draft due 10/19, see comments [pdf]
2. first draft due 10/28 [pdf] [tex], final draft due 11/02, see comments [pdf]
3. first draft due 11/13 [pdf] [tex], final draft due 11/18
4. first draft due 11/30 [pdf] [tex], final draft due 12/04, see comments [pdf]

Texts

• Paul Halmos. Naive Set Theory. Springer, 1974. Available via CU library link

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

• Installing LaTeX on your own computer
• Math symbols
• LaTeX template [tex]