Mathematics for Computer Science

5-0-7 units. REST · Undergraduate

Elementary discrete mathematics for science and engineering, with a focus on mathematical tools and proof techniques useful in computer science. Topics include logical notation, sets, relations, elementary graph theory, state machines and invariants, induction and proofs by contradiction, recurrences, asymptotic notation, elementary analysis of algorithms, elementary number theory and cryptography, permutations and combinations, counting tools, and discrete probability.

Spring 2024

This course covers elementary discrete mathematics for science and engineering, with a focus on mathematical tools and proof techniques useful in computer science. Topics include logical notation, sets, relations, elementary graph theory, state machines and invariants, induction and proofs by contradiction, recurrences, asymptotic notation, elementary analysis of algorithms, elementary number theory and cryptography, permutations and combinations, counting tools, and discrete probability.

Readings

The text for this course is Lehman, Eric, Thomson Leighton, and Albert Meyer. Mathematics for Computer Science (PDF) . The textbook is available under a CC BY-SA license. ↗
Listed reading
These are the recommended lecture readings to accompany the course. All readings are taken from Eric Lehman, Tom Leighton, and Albert Meyer, Mathematics for Computer Science (PDF) . The textbook is available under a CC BY-SA license. ↗
Listed reading
Lecture 01 - Predicates, Sets, and Proofs: Sections 1.0–1.7, 3.1–3.3, 3.6 Lecture 02 - Contradiction and Induction: Sections 1.8–1.9, 4.1, and 5.1 Lecture 03 - Casework and Strong Induction: Sections 5.2–5.3 Lecture 04 - State Machines: Updated State Machines Chapter
Listed reading
Lecture 11 - Graphs and Coloring: Sections 12.1–12.3, 12.6 Lecture 12 - Matching: Sections 12.5–12.5.1, and the Updated State Machines chapter, section 4 Lecture 13 - Connectivity and Trees: 12.7–12.9, 12.11 Lecture 14 - Digraphs and DAGs: 10–10.2, 10.5
Listed reading
Lecture 18 - Probability: Section 17 (can skip 17.4) Lecture 19 - Conditional Probability: Sections 18.0–18.6 Lecture 20 - Independence: Sections 18.7–18.9, 17.4 Lecture 21 - Random Variables: Sections 19–19.3 Lecture 22 - Expectation: Sections 19.4–19.6 Lecture 23 - Expectation and Variance: Chapter 20 (reading shared with lecture 24) Lecture 24 - Large Deviations: Chebyshev and Chernoff Bound, Wrap Up: Chapter 20 (reading shared with lecture 23)
Listed reading

Prerequisites & course information

Same subject as 18.062[J] Prereq: Calculus I (GIR) U (Fall, Spring) 5-0-7 units. REST

Sources

Course catalogue ↗2026–2027
MIT OpenCourseWare ↗Spring 2024
MIT OCW syllabus ↗
MIT OCW readings ↗
Historical MIT OpenCourseWare offering. Named reading entries and schedule topics are automatically extracted from the linked source pages.