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 |
recitation 0, 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 |
recitation 1, 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 18, 8.1, Rosen 1.4, 3.2 |
HW 2 out (due Tues 9/29) HW2 solutions |
recitation 2, solutions |
| Sets and Functions | ||||
| Mo 9/28 | Set operations; power sets; double containment. lecture notes, slides. | Newstead 2.2, Scheinerman 2.10, Rosen 1.5 |
||
| We 9/30 | Functions: well-definedness, injections, surjections, bijections. lecture notes, slides. | Newstead 3.1, 3.2, Scheinerman 5.20, 5.22, Rosen 1.6 |
HW 3 out (due Tues 10/6) HW3 solutions |
recitation 3, solutions |
| Mo 10/5 | Function inverses. lecture notes, slides. | |||
| We 10/7 | Finite, countable, and uncountable sets. lecture notes, slides, supplementary note. | Newstead 6.1-6.2 | Midterm review | |
| Midterm 1 | ||||
| Sat 10/10 | Exam review session: 3 - 5pm in CSB 451. |
practice exam and
solutions
practice problems and solutions. |
||
| Mo 10/12 | MIDTERM 1 (in class). Topics: logic, proofs, induction, sets, functions (no inverses/countability). | |||
| Combinatorics | ||||
| We 10/14 | Countable and uncountable sets. lecture notes, slides. | Newstead 6.1-6.2, 8.1 Rosen 4.1-4.3 Scheinerman 3.13-14 |
HW 4 out (due Tues 10/20) HW4 solutions |
recitation 4, solutions |
| Mo 10/19 | Permutations and combinations; partitions; sequential decision procedures. lecture notes, slides. | Newstead 8.1 Rosen 6.1, 6.3 Scheinerman 3.17 (kinda) |
counting example | |
| We 10/21 | Stars and bars, inclusion-exclusion, overcounting. lecture notes, slides. | Rosen 5.5 Scheinerman 3.15-16 |
HW 5 out (due Tues 10/27) HW5 solutions |
recitation 5, solutions |
| Mo 10/26 | Counting in two ways. The pigeonhole principle. lecture notes, slides. | Newstead 8.1 (pg. 286-) Rosen 4.2 Scheinerman 5.21 |
||
| Graph theory. | ||||
| We 10/28 | Graphs and subgraphs. lecture notes, slides. | Rosen 7.1-7.2 Scheinerman 9.43-44 |
HW 6 out (due Fri 11/6) |
recitation 6, solutions |
| Mo 11/2 | ELECTION DAY — no class | |||
| We 11/4 | Paths and cycles; trees; Eulerian paths. lecture notes | Rosen 7.4-7.5; 8.1 Scheinerman 9.45-47 |
||
| Sat 11/7 | Exam review session: 3 - 5pm in CSB 451. | |||
| Mo 11/9 | Coloring, planarity, isomorphism. | Rosen 7.3, 7.7-8 Scheinerman 9.48-49 |
||
| Midterm 2 | ||||
| We 11/11 | MIDTERM 2 (in class). Topics: Function inverses; countability; combinatorics; graph theory (up to 11/4). | |||
| 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 | |||
| Mo 11/30 | Random graphs and random walks. | |||
| Number Theory | ||||
| We 12/2 | Equivalence relations, modular arithmetic. | |||
| Mo 12/7 | Euler's theorem, FLT. | |||
| Bonus Topics | ||||
| We 12/9 | Means and inequalities; partial orders. | |||
| Mo 12/14 | Catalan numbers. | |||
| Final Exam | ||||
| Mo 12/21 | Final Exam: 3:30-6:30pm in Havemeyer 309.
Cumulative, with more emphasis on probability and number theory. |
|||