Skip Navigation
York U: Redefine the PossibleHOME | Current Students | Faculty & Staff | Research | International
Search »FacultiesLibrariesCampus MapsYork U OrganizationDirectorySite Index
Future Students, Alumni & Visitors
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
Last modified:
2019/05/13 14:07