CMPSC 360: Discrete Mathematics

Fall 2026

About this course

CMPSC 360 is an introduction to the mathematics that underpins computer science: the art of reasoning precisely about discrete structures—the finite, countable objects that computation is built from. The course has two aims. The first is to make you fluent in the language mathematicians and computer scientists use to state ideas exactly. The second is to give you the reasoning tools to establish when those ideas are true.

We begin by setting up that language—sets, logic, functions, and relations—and the core toolkit for establishing truth: proof techniques and mathematical induction. With the language and the toolkit in hand, we spend the rest of the term in four substantial modules where those tools are put to work: counting and combinatorics, probability, graph theory, and number theory. Each module revisits the language in a new setting, so the foundations are reinforced rather than left behind.

By the end of the course you should be able to translate informal statements into precise mathematical language, choose and carry out an appropriate proof strategy, count and reason about complex arrangements, model problems with graphs, and reason quantitatively about uncertainty. These are the habits of thought that later courses in algorithms, theory, and systems assume—and that make you a sharper problem-solver anywhere in computing.

Reference books

Welcome games Lecture 1

  1. Game 1: Knights & Knaves
  2. Game 2: Trace It in One Stroke
  3. Game 3: A Sky Full of Shapes

Tentative schedule

Fifteen weeks, organized as six modules. Weeks are approximate and subject to change.

The Language

· 2 weeks

Sets and set operations; propositional and predicate logic with quantifiers; functions (injective, surjective, bijective, composition, inverse); relations, equivalence relations, and partial orders.

Proofs & the Toolkit

· 2 weeks

Reading and writing proofs; direct proof, contrapositive, contradiction, and proof by cases; reasoning with definitions and quantifiers; mathematical induction (weak and strong) and recurrences.

Counting & Combinatorics

· 3 weeks

The product and sum rules; permutations and combinations; the pigeonhole principle; the binomial theorem and combinatorial identities; inclusion–exclusion; solving recurrences.

Probability

· 2 weeks

Discrete sample spaces and events; conditional probability and independence; the union bound; random variables and expectation; linearity of expectation and indicator variables; variance and basic concentration.

Graph Theory

· 3 weeks

Graphs, degree, and the handshake lemma; paths, cycles, connectivity, and isomorphism; trees and spanning trees; bipartite graphs and matchings; Eulerian and Hamiltonian paths; planarity and graph coloring.

Number Theory

· 2 weeks

Divisibility, primes, and the division algorithm; modular arithmetic and congruences; the Euclidean algorithm and Bezout's identity; modular inverses and linear congruences; the Chinese Remainder Theorem and Fermat's little theorem.

Synthesis & Review

· 1 week

Connections across the modules, and review.

This schedule is tentative and may be adjusted as the term progresses.