1. The best way to discuss the course content with me is to see me during my office hours.
   

2. For other requests, such as appointment arrangement or “I cannot make the test”, you may contact me by emails.
   

3. I will NEVER answer emails sent from non-York accounts. Please start your subject line with “[1019]” and sign the email with the name you used to register for the class. Send the email in plain text, without attachments.
   

Course Description

Introduction to abstraction; use and development of precise formulations of mathematical ideas; informal introduction to logic; introduction to naïve set theory; induction; relations and functions; big O-notation; recursive definitions, recurrence relations and their solutions; graphs and trees.

The detailed list of topics includes

1. 1.Proof techniques (without using a formal system)
   

2. proof by contradiction
   

3. proof by cases
   

4. proving implications
   

5. proving statements with quantifiers
   

6. mathematical induction on natural numbers
   

2. 2.Naïve set theory
   

3. proving that one set is a subset of another
   

4. proving equality of two sets
   

5. basic operations on sets (union, intersection, Cartesian product, power sets, etc.)
   

6. cardinality of sets (finite and infinite)
   

7. strings
   

3. 3.Functions and relations
   

4. review of basic definitions (relation, function, domain, range, functions, 1-1 correspondence, function composition, closures of relations, etc.)
   

5. equivalence relations
   

4. 4.Asymptotic notation
   

5. big-O, big-Ω, big-Θ notation
   

6. proving f is in O(g), proving f is not in O(g)
   

7. classifying functions into a hierarchy of important classes, e.g., O(1), O(log n), O(√n), O(n), O(n2), O(nO(1)), O(2n)
   

5. 5.Recursive definitions and solving recurrences
   

6. recursive definitions of mathematical objects
   

7. solving simple recurrences
   

8. bounding divide-and-conquer recurrences of the form f(n) = af(n/b) + g(n), for constants a and b.
   

9. using structural induction on recursively defined objects
   

6. 6.Sums
   

7. summation notation
   

8. computing and bounding simple sums
   

7. 7.Elementary graph theory
   

8. basic definitions of graphs
   

9. proving simple facts about graphs
   

10. trees
    

Textbook: Kenneth H. Rosen. Discrete Mathematics and Its Applications, Sixth Edition. McGraw-Hill, 2007. There is a list of errata on this site.

Important Dates

Evaluation

Note: Missed tests with good reason (normally medical, and well documented) will have their weight transferred to the final exam. There are no “make up”tests. Tests missed for no reason are deemed to have been written and failed and are marked “0”(F).

Follow these links to familiarize yourselves with Senate’s expectations regarding Academic Honesty, but also with other Senate policies, in particular, with those about Academic Accommodation for Students with Disabilities, Religious Accommodation and Repeating Passed or Failed Courses for Academic Credit.