Discrete Structures: MATH 221 (3) | Pepperdine University | Seaver College

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

close this window