COMS 3203, Discrete Mathematics
The study of discrete mathematics provides an important foundation for basic theoretical principles in computer science. We first build a strong foundation in logic, formal proofs, and mathematical induction. We then examine the discrete structures of functions, relations, and graphs, which provide different ways of representing relationships, connections, and networks. Finally, we move onto numerical and computational aspects: number theory and modular arithmetic, counting and combinatorics, and discrete probability. Throughout the course, we will also see computer science applications and practice writing implementations in Python.
Course Objectives
- Build a strong foundation for all of mathematics in proofs and 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 graph theory, including Eulerian and planar graphs, and their usage in modeling a variety of CS problems.
- 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.
Prerequisites
- An introductory programming course (COMS 1004/1007)
- Mathematical maturity past single-variable calculus is strongly recommended
General List of Topics
- Propositional and predicate logic
- Rules of inference
- Set theory
- Direct proofs; proof by cases, contrapositive, counterexample
- Mathematical induction, strong induction
- Functions
- Relations; order and equivalence relations
- Graph theory, special graphs and trees
- Eulerian and Hamiltonian graphs
- Graph isomorphisms
- Number theory, divisibility
- Modular arithmetic, fast exponentiation
- GCD, Euclid’s algorithm
- Primality tests, RSA algorithm
- Combinatorics
- Permutations and combinations
- Binomial coefficients, pigeonhole principle