# 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