COMS 3203: Discrete Mathematics
Fall 2026 — Columbia University
Course Information
| Instructors | Gabriel Chuang (gtc2117@columbia.edu) and Styopa Zharkov (sz3295@columbia.edu) |
|---|---|
| Lecture | Section 001: Mon/Wed, 4:10 – 5:25pm, Pupin 301 Section 002: Mon/Wed 11:40am – 12:55pm, Math 317 |
| Office Hours | See the Office Hours page for the calendar |
| Recitations | Fridays, sections A–I (9am – 6pm). See the Recitations page for times and locations |
| Links | Gradescope | Courseworks | EdStem |
Welcome to Discrete Math! I'm very excited for us to be going on a mathematical adventure together.
What is (discrete) math for? There are two aspects:
- Precise communication — math gives us the language to speak precisely about intuitive ideas (like "infinite," "probably," "prove," and "contradictory"), and about useful CS notions like "efficiency," "fairness," and "privacy".
- Problem-solving — math gives us the tools to find out facts about those precise definitions.
These correspond to the two objectives of this course: learning the language of math (logic, sets, functions, relations, graph theory, number theory, probability, combinatorics), and learning to do proofs — formal arguments that certain statements are true or false. Full details, learning objectives, and course policies are on the Syllabus page.
Lecture Schedule (tentative)
All textbook readings are optional; if you learn well from a textbook, we suggest one of these:
- Newstead, An Infinite Descent into Pure Mathematics — free online here.
- Scheinerman, Mathematics: A Discrete Introduction.
- Rosen, Discrete Mathematics and Its Applications.
| Date | Topic | Readings (optional) | Homework | Recitation |
|---|---|---|---|---|
| Introduction; Proofs and Logic | ||||
| We 9/9 | Introduction. Logical connectives, quantifiers. lecture notes, slides. | Newstead 1.1–1.3, Scheinerman 1.1–1.2, 1.5, Rosen 1.1–1.3 | HW 0 out (due Tues 9/15) HW0 solutions |
problems solutions |
| Mo 9/14 | Direct proof and proof by contradiction. Negation. lecture notes, slides. | Newstead 1.1–1.3, Scheinerman 1.3–1.4, Rosen 3.1 |
||
| We 9/16 | Logical equivalences and more proofs. lecture notes, slides. | HW 1 out (due Tues 9/22) HW1 solutions |
problems solutions |
|
| Mo 9/21 | Sequences and induction. lecture notes, slides. | Newstead 4.2, Scheinerman 4.19, Rosen 3.2 | ||
| We 9/23 | Strong induction; sets. lecture notes, slides. | Newstead 2.1, 4.3, Scheinerman 4.18, 8.1, Rosen 1.4, 3.2 | HW 2 out (due Tues 9/29) |
problems solutions |
| Sets and Functions | ||||
| Mo 9/28 | Set operations; power sets; double containment. lecture notes. | Newstead 2.2, Scheinerman 2.10, Rosen 1.5 | ||
| We 9/30 | Functions. | |||
| Mo 10/5 | Functions, inverses, injective/surjective/bijective. | |||
| We 10/7 | Relations, equivalence relations, partial orders. | |||
| Midterm 1 | ||||
| Mo 10/12 | MIDTERM 1 (in class) | |||
| Graph Theory | ||||
| We 10/14 | Graph theory 1. | |||
| Mo 10/19 | Graph theory 2. | |||
| Countability, Combinatorics | ||||
| We 10/21 | Combinatorics 1. | |||
| Mo 10/26 | Combinatorics 2. | |||
| We 10/28 | Counting in two ways. | |||
| Mo 11/2 | ELECTION DAY — no class | |||
| We 11/4 | Countability, finiteness, pigeonhole principle. | |||
| Midterm 2 | ||||
| Mo 11/9 | Midterm 2 review. | |||
| We 11/11 | MIDTERM 2 (in class) | |||
| Probability | ||||
| Mo 11/16 | Probability. | |||
| We 11/18 | Events. Bayes' theorem. Binomials. | |||
| Mo 11/23 | Random variables, linearity of expectation. | |||
| We 11/25 | THANKSGIVING BREAK — no class | |||
| Number Theory | ||||
| Mo 11/30 | Division, GCD, Euclidean algorithm. | |||
| We 12/2 | Primes, modular arithmetic. | |||
| Mo 12/7 | Euler's theorem, FLT. | |||
| We 12/9 | Means and inequalities. | |||
| Final Exam | ||||
| Mo 12/14 | Final exam review. | |||