DS. Discrete Structures (37 core hours)

DS1. Functions, relations, and sets (core -- 6 hours)

  Functions (surjections, injections, inverses, composition)
  Relations (reflexivity, symmetry, transitivity, equivalence relations)
  Sets (Venn diagrams, complements, Cartesian products, power sets)
  Pigeonhole principle
  Cardinality and countability

DS2. Basic logic (core -- 10 hours)

  Propositional logic
  Logical connectives
  Truth tables
  Validity
  Implication, converse, inverse, negation, contradiction
  Predicate logic
  Limitations of predicate logic
  Universal and existential quantification
  Modus ponens and modus tallens

DS3. Proof techniques (core -- 12 hours)

  The structure of formal proofs
  Direct proofs
  Proof by counterexample
  Proof by contraposition
  Proof by contradiction
  Mathematical induction
  Strong induction
  Recursive mathematical definitions
  Well orderings

DS4. Basics of counting (core -- 5 hours)

  Counting arguments
  Permutations and combinations
  Solving recurrence relations

DS5. Graphs and trees (core -- 4 hours)

  Trees
  Undirected graphs
  Directed graphs
  Spanning trees