# Math 221 – Discrete Mathematics, Winter 2012

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.

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. 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.

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 13. The Cantor pairing function. Properties of countable sets.

Feb 15. Examples of correspondences between sets. The Schroder-Bernstein theorem.

Homework 6: due February 22. (answers)

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.

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, 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.

Homework 9: due March 14. (answers)

Mar 9. Proof of inclusion-exclusion. 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:30-12:30, CAT 61 (answers)