COMS 3203, Discrete Mathematics

The study of discrete mathematics provides an important foundation for basic theoretical principles in computer science. The first third of the course builds a strong background in logic, formal proofs, and mathematical induction, followed by a theoretical examination of functions and relations. With this knowledge in hand, we will then cover number theory and modular arithmetic, counting and combinatorics, discrete probability, recurrence relations, and finally foundations of graph theory. Throughout the course, we will also see computer science applications and practice writing implementations in Python.

Course Objectives

  • Understand fundamental and rigorous ideas underlying discrete mathematics, namely that of theorems, proofs, and propositional logic.
  • Apply rigorous proof techniques, including direct proofs, proof by counterexample, proof by contradiction, and proof by induction.
  • Manipulate and describe relationships between sets of objects using relations and functions.
  • Understand basic concepts in number theory, such as gcd, factoring, and modular arithmetic, and apply them to applications such as cryptography.
  • Count various sets or operations on objects, write combinatorial proofs, and characterize limits of countability.
  • Solve discrete probability problems, compute properties of random variables, and apply common probability distributions.
  • Understand basic concepts in graph theory, including Eulerian and planar graphs, and their usage in modeling a variety of CS problems.


  • An introductory programming course (COMS 1004/1007)
  • Mathematical maturity past single-variable calculus is strongly recommended

List of Topics

  1. Set theory
  2. Propositional and predicate logic
  3. Rules of inference
  4. Direct proofs; proof by cases, contrapositive, counterexample
  5. Mathematical induction, strong induction
  6. Functions
  7. Relations, equivalence relations
  8. Number theory, divisibility
  9. Modular arithmetic
  10. GCD, Euclid’s algorithm
  11. Prime numbers and factoring
  12. Cryptography, RSA
  13. Permutations and combinations
  14. Combinations with repetition, binomial coefficients
  15. Discrete probability and random variables
  16. Joint and conditional distributions
  17. Special probability distributions
  18. Graph theory, special graphs
  19. Graph connectedness and trees
  20. Eulerian trails and cycles
  21. Hamiltonian trails and cycles
  22. Graph isomorphism, planarity