COMS 3203, Discrete Mathematics

The study of discrete mathematics provides an important foundation for basic theoretical principles in computer science. This course starts by building a strong background in logic and formal proofs, particularly those constructed by induction. After developing the ability to write coherent, rigorous proofs, we will study topics relating to functions, number theory, group theory, counting, and graph theory. Applications in cryptography, error correcting codes, and other areas of computer science will be considered as time permits.

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 find relationships between sets of objects and functions.
  • Understand basic concepts in number theory, such as gcd, factoring, and modular arithmetic, and apply them to applications such as cryptography and encryption.
  • Count various sets or operations on objects, write combinatorial proofs, and characterize limits of countability.
  • Understand basic concepts in graph theory, including Eulerian and planar graphs, and their usage in modeling a variety of CS problems.

Prerequisites

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

List of Topics

  1. Course introduction; propositional logic
  2. Direct proofs; proof by cases, contrapositive, counterexample
  3. Intro to sets
  4. Set operations, relations
  5. Equivalence relations, proof by contradiction
  6. Proof by induction, smallest counterexample
  7. Applications of induction
  8. Functions
  9. Pigeonhole principle
  10. Modular arithmetic
  11. GCD, Euclid’s algorithm
  12. Prime numbers and factoring
  13. Fermat’s little theorem
  14. Cryptography, RSA
  15. Lists and counting
  16. Binomial coefficients
  17. Multisets
  18. Inclusion-exclusion
  19. Graph theory
  20. Graph connections
  21. Trees
  22. Eulerian graphs
  23. Graph coloring