Instructor: Anatolii Grinshpan
Office hours: MF 1-2 & W 2-3, Korman 247, or by appointment, Korman 253.
Jan 9. Introduction to the course. Examples of problems.
Propositions and their truth values.
Jan 11. Logical connectives. Truth tables.
Jan 13. Propositional equivalences. Propositional functions. Quantifiers.
Jan 16. MLK day.
Jan 18. Sets. Operations on sets. Cardinality. Binary strings. Power set.
Jan 20. Set identities. Membership tables. Functions. Domain and range.
Jan 23. One-to-one and onto. The graph. The inverse and composite functions.
Jan 25. Composition. The identity and indicator functions. The inverse image of a set.
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.
Feb 13. The Cantor pairing function. Properties of countable sets.
Feb 15. Examples of correspondences between sets. The Schroder-Bernstein theorem.
Feb 17. The method of induction. Examples from computational geometry.
Feb 20. Strong induction. Examples.
Feb 22. Well-ordering and division of integers. The idea of recursion.
Feb 24. Recursive definitions. Structural induction.
Feb 27. The towers of Hanoi. Basics of counting: product and sum rules, inclusion-exclusion.
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.
Mar 9. Proof of inclusion-exclusion. The number of onto functions.
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:30-12:30, CAT 61 (answers)