Math 221 – Discrete Mathematics, Winter 2012

Description: Description: Description: Description: Description: Description: image004.jpg

Instructor: Anatolii Grinshpan
Office hours:  MF 1-2 & W 2-3, 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. 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 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 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)