Discrete Structures: MATH 221 (3)
Application of formal methods to discrete analysis—mathematical induction, the correctness of loops, relations and functions, combinatorics, analysis of algorithms. Application of formal methods to the modeling of discrete structures of computer science—sets, binary trees.
Prerequisite: MATH 220
| Hours | Topic |
|---|---|
| Set Theory (5 hours) | |
| 1.0 | Set comprehension and membership |
| 2.0 | Set cardinality, subset, complement, union, intersection, difference, power set |
| 1.5 | Properties of set operations |
| 0.5 | Families of sets, axiom of choice, paradoxes |
| Mathematical Induction (6 hours) | |
| 1.5 | Induction over the natural numbers |
| 1.5 | Inductive definitions |
| 1.0 | Binary trees |
| 2.0 | Correctness of loops |
| Relations and Functions (11 hours) | |
| 1.0 | Tuples and cross products |
| 2.0 | Relations, domain, range, product, inverse |
| 1.5 | Properties—reflexive, irreflexive, symmetric, antisymmetric, asymmetric, transitive |
| 1.5 | Equivalence relations, equivalence classes |
| 1.5 | Functions—determinate, total, one-to-one, onto |
| 1.5 | Function inverse |
| 2.0 | Partial orders, posets, glb, lub |
| Combinatorial Analysis (4 hours) | |
| 2.0 | Sum and product rules, permutations and combinations |
| 2.0 | Pigeonhole principle, applications |
| Recurrence Relations (3 hours) | |
| 1.5 | Homogeneous difference equations |
| 1.5 | Closed solutions of inductive definitions |
| Analysis of Algorithms (6 hours) | |
| 2.0 | Space/time complexity |
| 4.0 | Asymptotic behavior: big oh, big omega, big theta |
Total: 35.0 hours, excluding holidays, review sessions, and exams
*Fifty-minute class hours