Discrete math for CS
Undergraduate · CS / Programming
Syllabus focus
Topics typically covered
Standard syllabus
Logic and proof
- Propositional logic and truth tables
- Predicates, quantifiers, and inference rules
- Direct proof, contrapositive, and contradiction
- Mathematical induction and strong induction
- Sets, functions, and cardinality (intro)
Combinatorics and graphs
- Counting: permutations, combinations, binomial theorem
- Pigeonhole principle and inclusion–exclusion (intro)
- Recurrence relations and generating functions (intro)
- Graphs: paths, cycles, trees, connectivity
- Euler/Hamilton paths; planarity (intro)
CS applications of discrete math
- Logic for program correctness and assertions
- Counting arguments for algorithm analysis
- Graphs in networking, compilers, and social data
- Modular arithmetic in hashing and crypto intros
- Recurrences for divide-and-conquer algorithms
- Discrete probability for randomized algorithms (intro)
Theoretical / proof-based
Proof depth
- Proof by cases and constructive vs existential proofs
- Well-ordering and structural induction
- Bijections and counting proofs
- Graph isomorphism and coloring arguments
- Intro to Ramsey theory (optional)
CS theory connections
- Big-O notation tied to counting arguments
- Boolean algebra and logic circuits
- Regular languages preview (automata intro)
- Pigeonhole arguments in hashing and compression
- Problem sets mirroring qualifying-exam discrete topics
Proof practice for CS
- Direct, contradiction, and contrapositive proofs
- Strong induction on recursive structures
- Invariant proofs for loops and algorithms
- Bijection and pigeonhole arguments
- Graph induction and tree properties
- Writing clear proofs that graders can follow
Notes
Gateway course for algorithms and theory. Overlap with math department discrete courses varies.