EECS/MATH 1019: Discrete Math for Computer Science

## Lecture Schedule ( Fall 2019):

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

## Course Description:

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

1. Proof techniques (without using a formal system)
• propositional and predicate logic
• proof techniques and strategies
• mathematical induction on natural numbers
2. 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)
3. Functions and relations
• review of basic definitions: relation, function, domain, range, 1-1 correspondence, function composition, closures of relations, etc.
• equivalence relations
4. 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
5. 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
6. Sums
• summation notation
• computing and bounding simple sums
7. Elementary graph theory
• basic definitions of graphs
• proving simple facts about graphs
• trees 