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.
- 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.
- An introductory programming course (COMS 1004/1007)
- Mathematical maturity past single-variable calculus is strongly recommended
List of Topics
- Course introduction; propositional logic
- Direct proofs; proof by cases, contrapositive, counterexample
- Intro to sets
- Set operations, relations
- Equivalence relations, proof by contradiction
- Proof by induction, smallest counterexample
- Applications of induction
- Pigeonhole principle
- Modular arithmetic
- GCD, Euclid’s algorithm
- Prime numbers and factoring
- Fermat’s little theorem
- Cryptography, RSA
- Lists and counting
- Binomial coefficients
- Graph theory
- Graph connections
- Eulerian graphs
- Graph coloring