CMSC 250: Discrete Structures
The main focus of CMSC 250 is proofs. All of the topics below should be understood with that in mind.
- Relations: binary and n-ary relations; graphs of binary relations; reflexive, symmetric, transitive, equivalence relations and partial order relations.
- Functions and algorithms: (1-1) injective, onto (surjective) and 1-1-and-onto (bijective) functions; composition; associative and commutative property of binary operations; distinctions between functions and algorithms; simple proofs.
- Naive set theory: unions, intersections, disjoint sets, symmetric difference, Venn diagrams, DeMorgan’s laws, power sets; cardinality, countability, uncountability of the reals, functions that are not computable
- Logic: symbolic notation, propositional and predicate logic, truth and falsity of statements, Demorgan’s law, validity and invalidity of arguments, truth tables and formal proofs.
- Mathematical induction: weak and strong induction; easy proofs by induction, proofs about summations and recurrences.
- Combinatorics: Permutations, combinations, probability.
- Techniques of Proof: induction, strong induction, contradiction, direct.
- Number Theory: mod arithmetic, primes, rationals and irrationals, floors and ceilings.
- Sets: union, interesection, complement, subset, cross product, venn diagrams, powerset.
