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
- Set theory
- Propositional and predicate logic
- Rules of inference
- Direct proofs; proof by cases, contrapositive, counterexample
- Mathematical induction, strong induction
- Functions
- Relations; order and equivalence relations
- Graph theory, special graphs and trees
- Eulerian trails and cycles
- Hamiltonian cycles, graph isomorphisms
- Number theory, divisibility
- Modular arithmetic
- GCD, Euclid’s algorithm
- Prime numbers and factoring
- Primality tests, RSA algorithm
- Counting and pigeonhole principle
- Permutations and combinations
- Combinations with repetition, binomial coefficients
- Discrete probability and random variables
- Joint and conditional distributions
- Special probability distributions