# Math 221 – Discrete Mathematics, Spring 2013

Instructor: Anatolii Grinshpan
Office hours:  MWF 10-10:50, Korman 247, or by appointment, Korman 253.

Apr 1.   Introduction to the course.  Three examples: Steiner’s problem, the Tower of Hanoi, set partitions.

Apr 3.   Set notation. Empty set. Propositional logic. Reading and exercises: 2.1-2.4, 3.1-3.3.

Apr 5.   Logical equivalences. Propositional calculus. Reading and exercises: 3.4-3.7.

Apr 8.   Polynomials associated to statements. Induction. Reading and exercises: 4.1-4.3.

Apr 10. Quiz 1 (propositional logic). Induction and recursive definitions. Reading and exercises: 4.4, 4.5.

Apr 12. Solving problems using induction. Reading and exercises: 4.6-4.9.

Apr 15. The Tower of Hanoi. Functions and sets. Reading and exercises: 5.1-5.5.

Apr 17. Functions and counting. Size of a set. The pigeonhole principle. Reading and exercises: 6.1, 6.2.

Apr 19. Quiz 2 (functions). Example from class.

Apr 22. Applications of the pigeonhole principle. Example from class. Reading and exercises: 6.4.

Apr 24. Counting problems. Infinite sets. Reading and exercises: 6.3, 6.5, 6.6.

Apr 26. Quiz 3 (counting). Examples and questions. Exercises: 6.7.

Apr 29. Midterm 1 (Chapters 1-6).

May 1.  Midterm discussion. Relations on a set. Equivalence relations.

May 3.  Equivalence relations. Reading and exercises: 7.1-7.3.

May 6.   Representation of integers. Divisors. The Euclidean algorithm. Reading and exercises: 8.1-8.4.

May 8.   The Fundamental Theorem of Arithmetic. Reading and exercises: 8.5-8.7.

May 10. Quiz 4 (Euclidean algorithm). Fermat’s little theorem.

May 13. Rational numbers. Reading and exercises: 9.1, 9.2.

May 15. Counting rationals: Cantor’s pairing. Example from class.

May 17. Quiz 5 (rational numbers). Decimal expansions. Reading and exercises: 9.3.

May 20. Rational approximations. Rational approximations to square roots. Counting reals. Reading and exercises: 9.4-9.8.

May 22. Addition and product rules. Generalized pigeonhole principle. Euler’s function. Reading and exercises: 10.1-10.3.

May 24. Quiz 6 (countable and uncountable sets). Counting functions. Permutations. Reading and exercises: 10.4, 10.5.

May 27. Memorial day.

May 29. Midterm 2 (7.1 – 10.5).

May 31. Permutations and cycles. Binomial coefficients. Reading and exercises: 10.6, 10.7, 11.1.

June 3.  Binomial identities. Inclusion-exclusion (sieve) principle. Reading and exercises: 11.3, 11.4.

June 5.  The number of surjections. Partitions into a fixed number of parts. Example. Recurrence. Reading and exercises: 12.1.

June 7.  Quiz 7 (partitions). The number of partitions. Partitions and equivalence relations. Reading and exercises: 12.2.

June 10. Questions session.

June 12. Final exam (all lectures): 10:30-12:30, PISB 108.