
Instructor: Anatolii Grinshpan
Office hours: MF 12 & W 23, Korman 247, or by appointment, Korman
253.
Syllabus Academic calendar Math resource center
Jan 9. Introduction to the course. Examples of problems.
Propositions and their truth values.
Jan 11. Logical connectives. Truth tables.
Homework 1: due January 18. (answers)
Jan 13. Propositional equivalences. Propositional functions. Quantifiers.
Jan 16. MLK day.
Jan 18. Sets. Operations on sets. Cardinality. Binary strings. Power set.
Homework 2: due January 25. (answers)
Jan 20. Set identities. Membership tables. Functions. Domain and range.
Jan 23. Onetoone and onto. The graph. The inverse and composite functions.
Jan 25. Composition. The identity and indicator functions. The inverse image of a set.
Homework 3: due February 1. (answers)
Jan 27. Counting functions on a finite set. Iteration.
Jan 30. Sequences. Examples. Arithmetic and geometric progressions.
Feb 1. Triangular numbers. Averaging of a sequence. Summations. Exercises.
Homework 4: none
Feb 3. Discusssion.
Feb 6. Midterm 1 (lectures of January 9 – February 1). (answers)
Feb 8. Cardinality of sets.
Homework 5: due February 15. (answers)
Feb 10. Countable and uncountable sets. Cantor’s theorem.
Feb 13. The Cantor pairing function. Properties of countable sets.
Feb 15. Examples of correspondences between sets. The SchroderBernstein theorem.
Homework 6: due February 22. (answers)
Feb 17. The method of induction. Examples from computational geometry.
Feb 20. Strong induction. Examples.
Feb 22. Wellordering and division of integers. The idea of recursion.
Homework 7: due February 29. (answers)
Feb 24. Recursive definitions. Structural induction.
Feb 27. The towers of Hanoi. Basics of counting: product and sum rules, inclusionexclusion.
Feb 29. Discussion. Example from class.
Homework 8: none
Mar 2. Midterm 2 (lectures of February 8 – February 27). (answers)
Mar 5. Permutations and combinations. The binomial theorem.
Mar 7. Properties of binomial coefficients. Pascal’s triangle, a recurrence.
Homework 9: due March 14. (answers)
Mar 9. Proof of inclusionexclusion. The number of onto functions.
Mar 12. Stirling’s numbers, a recurrence. The number of partitions of a set. Example.
Mar 14. Solving recurrence relations. Example.
Mar 16. Solving recurrence relations. Example.
Mar 19. Discussion. An example on strings and recursion.
Mar 22. Final Exam: 10:3012:30, CAT 61 (answers)