• ES Español
• EN English

3.3. Discrete Mathematics and Combinatorics (DMC)

This area covers the mathematics of finite and countable structures, including combinatorial enumeration, graph theory, discrete optimization, and the logical foundations of computer science. It is core to algorithm design, formal languages, type systems, and compiler theory.

Knowledge Area (KA)	CS Core	KA Core
3.3.1 Enumerative Combinatorics	Elective
3.3.2 Graph Theory	Elective
3.3.3 Discrete Optimization	Elective
3.3.4 Mathematical Logic and Set Theory	Elective

3.3.1. DMC/Enumerative Combinatorics ↑ Back to top

Systematic counting of discrete structures using bijections, recursions, generating functions, and the principle of inclusion-exclusion.
Topics:
Core

• Basic counting principles: permutations, combinations, and the binomial theorem
• Principle of inclusion-exclusion and applications to derangements and Euler's totient function
• Ordinary and exponential generating functions; solving recurrences
• Integer partitions, Young tableaux, and the hook-length formula

Learning Outcomes:
Core:

1. Apply basic counting principles and inclusion-exclusion to enumeration problems [Familiarity]
2. Construct ordinary and exponential generating functions to enumerate combinatorial structures [Usage]
3. Derive closed-form formulas for combinatorial sequences using bijections and recurrences [Assessment]

3.3.2. DMC/Graph Theory ↑ Back to top

Structure and properties of graphs: connectivity, colorings, matchings, planarity, and spectral graph theory, with applications to networks and algorithms.
Topics:
Core

• Graphs: definitions, isomorphism, degree sequences, trees, and spanning trees
• Connectivity, Menger's theorem, and network flows (max-flow min-cut)
• Matchings (Hall's theorem), graph colorings, and the chromatic polynomial
• Planar graphs, Euler's formula, Kuratowski's theorem, and the four-color theorem
• Adjacency and Laplacian matrices, eigenvalues, and expander graphs

Learning Outcomes:
Core:

1. Identify structural properties of graphs (connectivity, planarity, bipartiteness) and apply Euler's formula [Familiarity]
2. Apply Hall's marriage theorem and network flow algorithms to matching and routing problems [Usage]
3. Analyze a graph's spectrum to bound its chromatic number and connectivity properties [Assessment]

3.3.3. DMC/Discrete Optimization ↑ Back to top

Integer programming, network flows, matroids, matching algorithms, and the theory of NP-completeness, foundational for algorithm design in computing.
Topics:
Core

• Integer linear programming: branch and bound, cutting planes, and totally unimodular matrices
• Network flow algorithms: shortest paths, max-flow, min-cost flow
• Matroid theory: independent sets, greedy algorithm, and matroid intersection
• Complexity theory: P vs. NP, NP-completeness, and reductions
• Approximation algorithms and the polynomial-time approximation scheme (PTAS)

Learning Outcomes:
Core:

1. Explain the relationship between linear programming relaxations and integer programming bounds [Familiarity]
2. Apply network flow and matroid algorithms to solve combinatorial optimization problems [Usage]
3. Prove NP-completeness of a combinatorial problem via polynomial reduction [Assessment]

3.3.4. DMC/Mathematical Logic and Set Theory ↑ Back to top

Propositional and first-order logic, proof systems, Gödel's theorems, and computability, forming the logical foundation of programming languages and formal verification.
Topics:
Core

• Propositional logic: syntax, semantics, satisfiability, and resolution
• First-order logic: models, soundness, and the Gödel completeness theorem
• Gödel's incompleteness theorems and their implications for formal systems
• Axiomatic set theory (ZFC): ordinals, cardinals, and the axiom of choice
• Computability: Turing machines, decidability, and the halting problem

Learning Outcomes:
Core:

1. State Gödel's completeness and first incompleteness theorems and explain their significance for computing [Familiarity]
2. Construct formal proofs in first-order logic and determine the satisfiability of formulas [Usage]
3. Analyze the undecidability of problems by reduction to the halting problem [Assessment]