The

CMSC 27100-1 (9:30 class) at SHFE 146

CMSC 27100-2 (11:30 class) at Kent 101

and the final on

If this is an unresolvable conflict please email me ASAP.

337 Crerar Library

**Office Hours:** TBA

- Gökalp Demirci
- Taylor Friesen
- Jesse Stern
- Goutham Rajendran
- Tiago Royer
- Joseph Tsang

Section 1 MWF 9:30 - 10:20 Harper 130

Section 2 MWF 11:30 - 12:20 Ry 276

Please come to the correct section, as room capacities are limited.

You should plan to attend one every week.

If you need special accommodations, please see me ASAP.

L. Babai: Discrete Mathematics Lecture Notes (in particular, Ch 2., Asymptotic Notation, Ch. 4, Basic Number Theory, and Ch. 7, Finite Probability Spaces).

Preliminary version here

Other useful (ambitious) sources:

- J. Matousek, J. Nesetril, An Invitation to Discrete Mathematics, Oxford University Press, 2009.
- L. Lovász, Combinatorial Problems and Exercises, AMS Chelsea Publishing, 2007.
- S. Jukna, Extremal Combinatorics, Springer-Verlag, 2011. (electronic version available from the Library)
- N. Alon, J. Spencer, The Probabilistic Method, Wiley-Interscience, 2008.
- R. Motwani, P. Raghavan, Randomized Algorithms, Cambridge University Press, 2007.
- Cormen, Leiserson, Rivest and Stein: Introduction to Algorithms, MIT Press, (3rd ed, 2009)
- Euler's paper about the Konigsberg Bridges. here.

If your Latin is rusty, there is a translation (behind a paywall, but available through the Library in Scientific American v.189, Issue 1, and a student account here.

My plan for grading is to base it on weekly homework assignments (35%), a midterm (30%) and a final (35%).

I assume you know most of the material in the first 2 chapters. Please review them: feel free to come to recitations with questions about them, if any.

- Definitions, proofs and techniques. Illustration through facts from Number Theory
- Basic Number Theory. Divisibility, gcd, lcm. Euclidean Algorithm (and its analysis). Congruences.
- Proofs by Induction. Induction and recursion. Applications.
- Counting. Applications of inductive proofs. Pigeonhole principle. Binomial coefficients. Basic combinatorial analysis.
- Discrete Probability (notions-we will start with Prof. Babai's notes.) Applications of counting. Bayes' Theorem
- Solving recurrence relations. Induction, generating functions. Priciple of inclusion-exclusion. Nonhomogeneous linear recurrence relations.
- Some Graph Theory: basic definitions and concepts. Paths, connectivity, distance.
- Trees. Rooted trees, binary trees, tree traversal.

- First Assignment Due Wednesday October 10 Second Assignment Due Wednesday October 17.
- Third Assignment Due Wednesday October 24
- Fourth Assignment Due Wednesday October 31
- Do Exercises - Sections 6.4, 6.5
- Fifth Assignment Due Wednesday November 14.