CMSC 27100: Discrete Mathematics (Autumn 2025)

General information

Instructor

Timothy Ng (timng@uchicago.edu)

Lectures

Section	Day	Time	Location
2	MWF	10:30–11:20	Ryerson 276
3	MWF	11:30–12:20	Ryerson 276

Discussions

Section	Day	Time	Location
2D01	Wed	4:30–5:50	SS 401
2D02	Thurs	5:00–6:20	Cobb 302
3D01	Thurs	3:30–4:50	Cobb 304
3D02	Thurs	5:00–6:20	Cobb 304

Links

Overview

Discrete mathematics is the study of discrete mathematical structures. This includes things like integers and graphs, whose basic elements are discrete or separate from one another. This is in contrast to continuous structures, like curves or the real numbers. We will investigate a variety of topics in and proof techniques common to discrete math. This course provides the mathematical foundations for further theoretical study of computer science, which itself can be considered a branch of discrete mathematics.

Communication

There are a number of different tools we'll be using to communicate about the class.

Course materials: Lecture notes will be made available via this course webpage. The course website also contains basic information about the course (i.e. you can treat it like a syllabus).
Discussion and announcements: We will use Ed Discussion for course discussion and announcements. Restricted course materials will also be posted here.
Coursework and grades: Gradescope will be used for distributing and receiving coursework, such as problem sets and exams.; PrairieLearn will be used for administering discussion session work, such as quizzes and groupwork.
Office hours: Office hours are times when the course staff are available for you. The instructor and teaching assistants will have scheduled office hours in-person and/or online. While most students typically use this as an opportunity to ask about coursework, you're welcome to ask about or discuss things that are related directly or indirectly with the course.

Class meetings

Lectures: Lectures are often the first point at which students will be exposed to new ideas and material. They will cover material that is necessary for success in the course. However, lectures alone may not be sufficient for all students. It is not expected that students will master the material learned in lecture without significant review, inquiry, and practice outside of lecture.
Discussions: Discussion sessions are intended to give students an opportunity to practice and get feedback in a more active setting than lecture. Discussion sessions consist of two components: proctored quizzes and collaborative problem solving.

Course material

The following is a list of topics that will be covered in the course.

Proof and Logic: The language and rules of mathematical reasoning: propositional and predicate logic, proofs and proof rules, induction and recursion
Elementary Number Theory: The structure of the integers: divisibility, modular arithmetic, prime numbers
Combinatorics: Enumerating discrete structures: counting, permutations and combinations, pigeonhole principle, the binomial theorem
Graph Theory: The structure of relations: graphs, paths, connectivity, trees
Probability Theory: Describing the likelihood of discrete events: probability axioms, conditioning, independence, expectation

Text

There is no required textbook for this course and lecture notes will be provided. However, there are a number of alternate resources. Note that definitions and notation may differ slightly across these. When in conflict, the primary source for definitions and notation in this course is the lecture notes.

The recommended textbook is Mathematics for Computer Science, by Lehman, Leighton, and Meyer. The linked draft of this book is freely available.
Another comprehensive resource for this course is Discrete Mathematics and Its Applications, 8th ed. by Kenneth H. Rosen. An electronic copy is available through the UChicago Library.

Evaluation

Your computed grade in this course will be determined by the following coursework components.

Problem sets, roughly weekly, worth $\frac 1 4$.
Participation in collaborative problem solving, roughly weekly, worth $\frac 1 {12}$.
Quizzes, roughly weekly, worth at most $\frac 1 6$.
One midterm examination, held on Thursday October 30, worth at most $\frac 1 4$.
One final examination, to be scheduled by the Registrar, worth at least $\frac 1 4$. Furthermore, the portion of the grade not earned apportioned to quizzes and the midterm examination are assigned to the final examination.

Problem sets

Problem sets will be distributed and submitted via Gradescope and will be due on Fridays at 7:00 pm (19:00) Central.

Document preparation

Submissions must be typed. No handwritten submissions of any kind will be accepted—this includes digitally handwritten submissions, such as those prepared on a tablet.

Though $\LaTeX$ is the preferred and recommended method for preparing your submission, it is not required.
Take the opportunity to learn how to typeset mathematics with $\LaTeX$! The UChicago Library has a $\LaTeX$ guide with links to resources.
All of the $\LaTeX$ commands used in the lecture notes is easily accessible by right-clicking on any formula, and selecting "Show Math As" $\rightarrow$ "TeX Commands" from the context menu. You can try this out with the $\LaTeX$ on this page.

Collaboration and citation

The purpose of problem sets is to give you the opportunity to practice working through the process of solving problems and to receive feedback on that process. The work that you hand in to be graded is expected to be your own. Why is this important?

When you submit a piece of work, you are claiming that it is a product of your understanding of the material.
Your work is subject to critique. It is important that your work represents your understanding so that the feedback you receive will be useful.
Authorship is not only about receiving credit for work, but it is also a claim of accountability. You should not submit any work for which you do not want to be held responsible.

Be sure to acknowledge your collaborators and any sources beyond course materials that you may have used.

If you choose to work with others, you must list your collaborators. You may only work with other students in the class. Your collaboration should be to a degree that your writeups are substantially different. It is not acceptable that solutions are largely copies of each other.
Do not look up solutions to assigned problems, online or otherwise. This includes question and answer forums, homework websites, and other publicly available materials from other courses in the department or at other institutions. Be aware that if you can find a solution online, the course staff can too.
Do not try to use language models to generate your solutions and submissions, in part or in whole. The purpose of the problem sets is to give you the opportunity to practice working through the process of solving problems and writing mathematics.
If you are not sure about whether something is permissible, you should err on the side of caution and ask the instructor for clarification.

It is your responsibility to be familiar with the University’s policy on academic honesty. Instances of academic dishonesty will be referred to the Office of College Community Standards for adjudication. Following the guidelines above on collaboration and citation should be sufficient, but if you have any questions, please ask the instructor.

Resubmission

Part of the learning process is identifying and correcting mistakes. After your submissions have been graded and returned to you, you will have the opportunity to use the feedback you receive to revise and resubmit your work.

Instructions for preparing your revisions will be provided after the first problem sets have been graded and returned.

Regrade requests

You may submit a regrade request in the event of an error by the grader. That is, if the feedback provided by the grader is a factual error, you may request a review of the grading. Please indicate the source of the error in this case.

We will not consider regrade requests concerning disagreement with a grader’s evaluation of your work. In such cases, you should consider the feedback that was given and apply it towards revision and resubmission of your work.

Accessibility

Students with disabilities who have been approved for the use of academic accommodations by Student Disability Services (SDS) and need reasonable accommodation to participate fully in this course should follow the procedures established by SDS for using accommodations. Timely notifications are required in order to ensure that your accommodations can be implemented. Please discuss your access needs in this class with the instructor after you have completed the SDS procedures for requesting accommodations.

Lectures

Lecture notes are put up after class. Readings are taken from Lehman, Leighton, and Meyer.

September 29: Discrete mathematics and computer science (7.1)
October 1: Induction, logic (5.1.1, 1.1–1.3, 3.1, 3.6)
October 3: Proof, Divisbility (1.4–1.6, 3.6, 9.1.0)
October 6: Proof, Divisibility, Induction (5.1.3, 9.1.0)
October 8: Division (9.1.2)
October 10: The greatest common divisor and Euclid's algorithm (9.2.1)
October 13: Bézout's lemma, Fibonacci numbers (9.2.2, 5.2.2)
October 15: Strong induction, Lamé's theorem (5.2.1)
October 17: Prime numbers and the Fundamental Theorem of Arithmetic (9.3)
October 20: Modular arithmetic (9.6–7)
October 22: Inverses, Fermat's little theorem (9.9)
October 24: Chinese Remainder Theorem, Rivest—Shamir—Adleman (9.61, 9.11)
October 27: Sets (4.1–4.2, 4.4)
October 29: Functions, cardinality, counting (4.3, 4.5, 8.1, 15.1)
October 31: Product and sum rules, permutations (15.2–15.3)
November 3: Division rule, combinations (15.4–15.6)
November 5: Binomial theorem, pigeonhole principle (15.8, 15.10)
November 7: Graphs (12.1–12.2, 12.4)
November 10: Connectivity (12.7–12.8)
November 12: Trees (12.10–12.11)
November 14: Matchings (12.5)
November 17: Discrete probability (17.3, 17.5)
November 19: Conditioning (18.2–18.4)
November 21: Independence, random variables (18.7, 19.1–19.3)
December 1: Binomial distributions, expectation (19.3–19.5)
December 3: Expectation (19.4–19.5)
December 5: Q&A