| |
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
| 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
close this window
|
 |
