**Section:**A.**Lectures:**5:30 - 7 pm, Mondays & Thursdays, at LAS C**Instructor:**Andy Mirzaian

Introduction to abstraction; use and development of precise formulations of mathematical ideas; informal introduction to logic; naïve set theory; induction; relations and functions; asymptotic notation; recursive definitions, recurrence relations and their solutions; graphs and trees. The detailed list of topics includes

**Proof techniques**(without using a formal system)- propositional and predicate logic
- proof techniques and strategies
- mathematical induction on natural numbers

**Naïve set theory**- proving that one set is a subset of another
- proving equality of two sets
- basic operations on sets (union, intersection, Cartesian product, power sets, etc.)
- cardinality of sets (finite and infinite)

**Functions and relations**- review of basic definitions: relation, function, domain, range, 1-1 correspondence, function composition, closures of relations, etc.
- equivalence relations

**Asymptotic notation**- big-O, big-Ω , big-Θ notation
- proving f is in O(g), proving f is not in O(g)
- classifying functions into a hierarchy of important complexity classes

**Recursive definitions and solving recurrences**- recursive definitions of mathematical objects
- solving simple recurrences
- bounding divide-and-conquer recurrences, using structural induction on recursively defined objects

**Sums**- summation notation
- computing and bounding simple sums

**Elementary graph theory**- basic definitions of graphs
- proving simple facts about graphs
- trees

Last modified:

2019/05/13 14:07

2019/05/13 14:07