CMSC 27100 Discrete Mathematics
This is a common website for both sections of the course
Both the midterm and the final will be given at night, not during normal class periods.
The midterm will be on Tuesday, November 6, 6:30-8:30
CMSC 27100-1 (9:30 class) at SHFE 146
CMSC 27100-2 (11:30 class) at Kent 101
and the final on Tuesday of Finals Week, 6:30-8:30
If this is an unresolvable conflict please email me ASAP.
Study Guide for Final
Study Guide here
What we covered so far
What we may cover next class
Assignments and Handouts
Please not that we will use Piazza extensively for communication.
337 Crerar Library
email: discr271 (at) gmail (dot) com
Office Hours: TBA
Tutorials, TAs and their office hours
- 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.
Office hours will have problem-solving lectures, as well as question-answering.
You should plan to attend one every week.
If you need special accommodations, please see me ASAP.
Textbook:K. H. Rosen: Discrete Mathematics and Its Applications, 7th ed.
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
- Entertaining material on Ramsey numbers Erdős and Moore
My plan for grading is to base it on weekly homework assignments (35%), a midterm (30%) and a final (35%).
We will cover much of the first 11 chapters of the Rosen text. We will use parts of
Babai's notes, especially for the material in chapters 4-8. We will not cover Chapter 9
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.
This is an overall plan for the course. I will surely not follow it in every detail.
- Definitions, proofs and techniques. Illustration through facts from Number Theory
- Basic Number Theory. Divisibility, gcd, lcm. Euclidean Algorithm (and its
- 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,
- Trees. Rooted trees, binary trees, tree traversal.
Material covered so far
Material to be covered next: here
Please look at the Homework section of the Rules for instructions on format and handing in homework.