MPCS 50103 Mathematics for Computer Science: Discrete Mathematics (Winter 2026)

Course Overview [Watch Video]

Syllabus PDF: Please look at the attached syllabus (Winter 2025 version) for full details about the class. 

Course Description:

This course is an introduction to ideas and techniques from discrete mathematics that are commonly used in computer science. It emphasizes mathematical proof and problem solving, employed on a variety of useful and interesting topics: combinatorics, discrete probability, graphs, and basic number theory. 

On completion of the course, students will be practiced in using mathematical concepts and techniques to solve problems, and in expressing mathematical notions precisely. They will be able to use ideas and techniques from discrete mathematics in subsequent courses in computer science, in particular courses in the design and analysis of algorithms, networks, numerical methods, software engineering, data analysis, and machine learning.

Course Contents:

• Mathematical reasoning and proofs: An introduction to mathematical reasoning, common logical fallacies, mathematical proofs and various proof techniques including, most importantly, mathematical induction.
• Combinatorics: Counting, permutations, combinations, binomial theorem, pigeon hole principle, inclusion-exclusion principle, bijective counting, recurrences. 
• Number Theory: Divisibility, Euclid's division algorithm, prime numbers, modular arithmetic, Fermat's little theorem.
• Discrete Probability: conditional probability, independence, Bayes rule, random variables, expected value, linearity of expectation, variance, Markov's inequality, the probabilistic method as a proof technique.
• Graphs: Directed and undirected graphs, various representations of graphs, graph isomorphism, , graph colouring, paths, connectivity, Eulerian and Hamiltonian paths, trees, bipartite graphs, matchings.
  
  

Course Activities:

• Classes: Classes will typically consist of a lecture on the topic interspersed with problem solving/ related activities.
• Office Hours: Regular office hours will be held by the course instructor as well as TAs. Attendance is optional but highly reccomended.
• Problem Solving Sessions: Regular problem solving sessions will be held for the purpose of giving the students guided problem solving practice. Attendance is optional but highly reccomended.
  
  

Course Materials:

The course textbook is: Discrete Mathematics and its Applications (7th edition) (McGraw-Hill) by Kenneth H. Rosen (ISBN 978-0073383095). 
The MIT Open Courseware textbook for their Mathematics for Computer Science course is also a good resource: MIT OCW textbook.
The class is intended to be self contained. Complete lecture notes will be provided for all the lectures. All problems in the problem sets will also be stated in full.

Evaluation:

The course grade will be based on homework, quizzes, a midterm and a final exam. 

• Homework: There will be weekly homework to be submitted online. You will have a Homework Score out of 100%
• Quizzes (30%): There will be two pre-announced in class quizzes.
• Midterm (25%)
• Final (45%)

The quizzes/ exams will be closed-book/notes.

You will thus have a homework score out of 100% and an Exam Score out of 100% and these will be combined as per the table in the syllabus document.

Prerequisites: 

Pre-calculus (especially familiarity with exponentials and logarithms) is a prerequisite. High school level familiarity with sets and functions, as well as common mathematical notation, will be assumed. 

MPCS 50101 Concepts of Programming (completed or concurrently taking), or a PASS on MPCS Programming Placement Exam I, or a Core Waiver for Programming.

Course request information for non-MPCS students: https://masters.cs.uchicago.edu/student-resources/non-mpcs-student-course-requests/

This class is scheduled at a time that conflicts with these other classes:

• MPCS 55001-2 -- Algorithms
• MPCS 54001-1 -- Networks
• MPCS 51250-1 -- Entrepreneurship in Technology
• MPCS 51044-1 -- C/C++ for Advanced Programmers

MS in Computational Analysis in Public Policy (Year 2) MS in Molecular Engineering MA in Computational Social Science (Year 1) MA in Computational Social Science (Year 2) Bx/MS in Computer Science (Option 3: Profesionally-oriented - Non-CS Majors) Masters Program in Computer Science Masters Program in Computer Science (new) Placement: Pass I Masters Program in Computer Science (new) Placement: Pass I + II Masters Program in Computer Science (new) Placement: Pass I + II (w/ Advanced) Masters Program in Computer Science (Immersion)