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.
Prerequisites
- An introductory programming course (COMS 1004/1007)
- Mathematical maturity past single-variable calculus is strongly recommended
List of Topics
- Set theory
- Propositional and predicate logic
- Rules of inference
- Direct proofs; proof by cases, contrapositive, counterexample
- Mathematical induction, strong induction
- Functions
- Relations, equivalence relations
- Number theory, divisibility
- Modular arithmetic
- GCD, Euclid’s algorithm
- Prime numbers and factoring
- Cryptography, RSA
- Permutations and combinations
- Combinations with repetition, binomial coefficients
- Discrete probability and random variables
- Joint and conditional distributions
- Special probability distributions
- Graph theory, special graphs
- Graph connectedness and trees
- Eulerian trails and cycles
- Hamiltonian trails and cycles
- Graph isomorphism, planarity