EECS-1019C
Discrete Mathematics for Computer Science

York University
Fall 2015
Class Homepage
Instructor: Parke Godfrey
Office: #2050 LAS
Office Hours: We 3–5pm
& by appointment / availability
Ph#: 416-736-2100 x66671
e-mail: godfrey@yorku.ca
T.A.'s: To be announced...
Office:  
Office Hours:  
e-mail:  
Term: Fall 2015
Time: Mondays 7:00–10:00pm
Place: LAS C
Textbook: Kenneth H. Rosen
Discrete Mathematics and Its Applications
Seventh Edition, 2012
McGraw Hill
ISBN: 0–07–338309–0
URL: Discrete Mathematics and Its Applications Information Center
Note: or the electronic edition via McGraw Hill Connect
Class URL: http://www.eecs.yorku.ca/course/1019/

Welcome to the course Discrete Mathematics for Computer Science, EECS-1019 (cross-listed as MATH-1019) for fall term 2015. Materials, instructions, and notices for the course will accumulate here over the semester.

 
  Announcements

Class announcements will accumulate here over the term. Be certain to check here regularly.

Also, be certain to refresh this page via your browser when you visit to ensure that you are not looking at an old, cached copy. Otherwise, you can miss the latest message.

Marks will accumulate on ePost (for if you have an EECS account).

  • Final exam preparation guide.

  • Tutorial 6-8pm Thursday 17 December in #3033 Lassonde Builing.

  • Tutorial 6-8pm Thursday 10 December in #3033 Lassonde Builing.

  • Final exam is 7:00pm–10:00pm Tuesday 22 December at TC VIVA.

  • Tutorial 4-6pm Friday 20 November in #3033 Lassonde Builing.

  • Test #2 is the first half of lecture time on Monday 23 November.

    It is closed notes, closed books. It covers the material from §2.4 & 2.5, §3.1–3.3, §5.1–5.3, and what we cover in class on Monday 16 November, which was §6.1 & 6.3, as in the textbook and as we covered in lecture.

    Problems will be very similar to those in the book and in the assignments. See these “test #1's” from previous terms as examples.

    Of course, each of the tests from above from different terms had slightly different coverage of material. So only pay attention to those questions that are from the sections that our test #2 covers.

  • Test #1 is the first half of lecture time on Monday 19 October.

    It is closed notes, closed books. It covers the material from §1.1–1.8 and §2.1–2.3 as in the textbook and as we covered in lecture. (Know just the basic definitions for functions from §2.3; the test will not do into depth on this, as we covered it briefly.)

    Problems will be very similar to those in the book and in the assignments. See these “test #1's” from previous terms as examples.

  • The Lassonde Student Government offers free tutoring via Excellassonde.

  • Tutorials (i.e., review sessions) start this week on 6-8pm Thursday 1 October. They will be weekly each week ending with 6-8pm Thursday 3 December. They will take place in CFA #312. They are not obligatory.

  • Apologies. No tutorial for Thursday night 24 September; I could not get a room scheduled for it.

    We should be scheduled for next week onward, though, so will start with a tutorial on 6-8pm Thursday on 1 October.

  • Welcome to the class!

 
  Syllabus
About the Course
The Topic (from the academic calendar)

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.

Course Content (from the academic calendar)

A detailed list of topics is as follows.

  1. proof techniques (without using a formal system)

    • proof by contradiction

    • proof by cases

    • proving implications

    • proving statements with quantifiers

    • 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)

    • strings

  3. functions and relations

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

    • equivalence relations

  4. asymptotic notation

    • big-O, big-Omega, big-Theta

    • proving f is in O(g), proving f is not in O(g)

    • classifying functions into a hierarchy of important classes

  5. recursive definitions & solving recurrences

    • recursive definitions of mathematical objects

    • solving simple recurrences

    • bounding divide-and-conquer recurrences of the form 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

Required Textbook / Reading

Course materials will be drawn from the assigned readings from the course textbook

Or you can sign up for additional study materials & the electronic edition via McGraw Hill Connect.

McGraw Hill Connect Notes for our class: PDF, PPT. (Thanks to Michele Peach of McGraw Hill.)

Grading Criteria & Course Requirements
 
what % when
Homework Assignments 1–10 20% ten, due weekly over the term
Test #1 20% Mo 19 Oct
Test #2 20% Mo 23 Nov
Final Exam 40% ? Dec

There will be 10 homework assignments altogether, one per week. The first two are to be done using McGraw Hill Connect. (See the bottom of this page for instructions.)

The tests will be held in the class's lecture room during the first 90 minutes of the lecture time on the days as stated. The final exam will be during the fall-term examination period. The date will be announced.

If you miss one of the tests for a justified reason (e.g., medical), the credit for that test will be transfered to the final exam. In that case, your final exam's weight will be 60%.

See the section on Polices below.

Schedule
 
week# day topic reading due
I. Logic
#1 Mo 14 Sep introduction
propositional logic
predicates & quantifiers
§1.1–1.3  
#2 Mo 21 Sep predicates & quantifiers
nested quantifiers
 
§1.4 & 1.5 A-1
A-2
#3 Mo 28 Sep rules of inference
introduction to proofs
proof methods & strategies
§1.6–1.8 A-3
#4 Mo 5 Oct sets
set operations
functions
§2.1–2.3 A-4
Thanksgiving (12 October)
II. Counting & Complexity
#5 Mo 19 Oct Test #1 sequences & summations
cardinality of sets
the growth of functions
§2.4, 2.5
§3.1
A-5
#6 Mo 26 Oct the growth of functions
complexity of algorithms
§3.2 & 3.3 A-6
#7 Mo 2 Nov mathematical induction
strong induction & well-ordering
recursive definitions & structural induction
§5.1—5.3 A-7
#8 Mo 9 Nov the basics of counting
permutations & combinations
binomial coefficients & identities
§6.1, 6.3, & 6.4 A-8
#9 Mo 16 Nov applications of recurrence relations
solving linear recurrence relations
divide-and-conquer algorithms & recurrence relations
§8.1—8.3 A-9
III. Relations & Graphs
#10 Mo 23 Nov Test #2 relations and their properties
n-ary relations & their applications
representing relations
§9.1—9.3 A-10
#11 Mo 30 Nov closures of relations
equivalence relations
 
§9.4 & 9.5  
#12 Mo 7 Dec graphs & graph models
graph terminology & special types of graphs
representing graphs & graph isomorphism
§10.1–10.3  
exam period (9–23 Dec)
  ? Dec Final Exam

 

The homework assignments (the A-#'s) are due before the next class lecture. For example, A-3 is due by Monday 5 October before 7pm (lecture).

A-4 is not due until Monday 19 October (before 7pm) due to Thanksgiving intervening.

A-1 and A-2 are both due by Monday 28 September (before 7pm). This is just to give some buffer on A-1 as term is starting.
Caution: Do not put it off!

 
  Class Materials
Lecture Notes
  1. introduction &propositional logic

  2. propositional logic continued, predicate logic

  3. arguments & proofs

  4. sets & functions

  5. sequences, summations, & cardinalities

  6. algorithms: basics, growth of functions, & algorithmic complexity

  7. induction & recursion

  8. counting / combinatorics

  9. advanced counting techniques: solving recurrence relations

  10. relations

Tests

  1. Test #1 (PDF), w/ answers (PDF)
  2. Test #2 (PDF), w/ answers (PDF)
  3. Final Exam

Homework Assignments

Assignments A-1 & A-2 must be done online. You need to register for a free trial of Connect and submit the homeworks electronically. McGraw-Hill Connect is a learning tool that allows, among other things, automatic homework submission and evaluation. You will find the instructions on where to find Connect here. Make sure you register for appropriate section. When you register for Connect, remember to include your first and last name exactly as they appear in York's records; otherwise, we will not be able to identify your homework, and you will not receive credit for it.

For Assignments A-3 through A-10, you may either keep submitting homeworks online via Connect (given you decided to purchase it), or you may submit them in hardcopy.

week# problems due
#1 On Connect.
§1.1: 2a–f, 12a–f, 24a–h (choose 10 of 20, 2pt each)
§1.2: 10, 16 (5pt each)
§1.3: 6, 8a–d, 10a–d, 30, 34a–c (choose 10 of 13, 2pt each)
Due before lecture on Monday 28 Sept
A1 (PDF)
#2 On Connect.
§1.4: 8a–d, 20a–e, 24a–e (2pt each)
§1.5: 6a–f (2pt each)
Due before lecture on Monday 28 Sept
A2 (PDF)
#3 §1.6: 8, 14, & 24
§1.7: 6, 8, 16, 24, & 26
§1.8: 4 & 14
Each will be graded out of 4 marks: 40pt total.
Due before lecture on Monday 5 Oct
A3 (PDF)
#4 §2.1: 6 (4pt), 20a–d (1pt each), 32 (4pt), 44 a–c (2pt each)
§2.2: 16a–e (2pt each), 50a–d (2pt each),
§2.3: 12, (4pt), 34 (5pt), 36 (5pt)
50pt total.
Due before lecture on Monday 19 Oct
A4 (PDF)
#5 §2.4: 10a–e, 30a–d
§2.5: 2a–f
2pt each: 30pt total.
Due before lecture on Monday 26 Oct
A5 (PDF)
#6 §3.1: 4 & 12 (5pt each)
§3.2: 18 (5pt) & 30a–e (2pt each)
25pt total.
Due before lecture on Monday 2 Nov
A6 (PDF)
#7 §3.3: 8, 14a, 14b, & 18
(5pt each: 20pt total.)
Due before lecture on Monday 9 Nov
A7 (PDF)
#8 §5.1: 20, 22, & 32
§5.2: 12
§5.3: 12 & 44
(5pt each: 30pt total.)
Due before lecture on Monday 16 Nov
A8 (PDF)
#9 §6.1: 8, 12, 32b, d, & f, & 64
§6.3: (4), 14 & 26a, b, & c
§6.4: 4, 6, & 14
(2pt each)
Due before lecture on Monday 30 Nov
(Amnesty for week of Test #2.)
A9 (PDF)
#10 §8.1: 11a–c
§8.2: 4a–e, 8a&b, 12 (4pt), 24a–c;
(2pt each, except as noted)
Due before lecture on Monday 7 Dec
A10 (PDF)

Homework assignments in hardcopy must be readable and should show the work that led to your answer. All hardcopy homework assignments must be dropped off at the drop-box for EECS-1019 in the lobby of the Lassonde Building (which houses the EECS department) adjacent to room #1003 by 7:00pm (before the class lecture) of the day they are due. No late assignments will be accepted. Any discussion about the grading should be conducted with the TA.

Tutorials

Tutorials start with 6-8pm Thursday 1 October. They will be weekly each week, ending with 6-8pm Thursday 3 December. They will take place in CFA #312. They are not obligatory.

Resources & References
Other References
  • Norman L. Biggs. Discrete Mathematics. Oxford University Press, 2002.
  • Alan Doerr and Kenneth Lavasseur. Applied Discrete Structures for Computer Science. Science Research Associates, 1985.
  • Gary Haggard, John Schlipf and Sue Whitesides. Discrete Mathematics for Computer Science. Thomson, 2006.
  • Rod Haggarty. Discrete Mathematics for computing. Addison-Wesley, 2002.
  • Bernard Kolman, Robert C. Busby and Sharon Cutler Ross. Discrete Mathematical Structures. Pearson, 2004.
  • Edward Scheinerman. Mathematics: A Discrete Introduction. Thomson, 2006.
  • Daniel Solow. How to Read and Do Proofs: An Introduction to Mathematical Thought Processes. Wiley, 2002.
  • Andrew Wohlgemuth. Introduction to Proof in Abstract Mathematics. Saunders College Publishing, 1990.
 
  Policies
Exams & Attendance

Tests and the Final Exam must be taken when scheduled unless the student has a medical documentation or can demonstrate special circumstances for a need for a rescheduled exam. The student must obtain approval from the instructor. As stated above, one missed test (with proper justification) will be shifted onto the weight of the Final Exam.

Class attendance is useful and highly encouraged, as the student will have an opportunity to ask for clarification of course and text material. There will be problem solving sessions during class period so that students gain experience applying the theory in practice. However, class attendance will not be monitored and is not part of the grade.

E-mail Policy

On e-mail from students with questions regarding course materials.

  • I will not answer these e-mails by e-mail reply, in general.

    My time is spent more productively for the class's sake in different ways. For pertinent questions on the materials that students send me by e-mail — or for questions that many people seem to be having — I will try to address them in class.

    If you have an urgent question I have not addressed, come see me during my office hours, or make an appointment if you need to. Many students do this already; it is a good use of my time and theirs. I can usually answer a question a student asks in person in about a tenth the time than by an e-mail exchange. Writing it out takes much longer. And for many of the questions people send me, the question is often unclear. It then requires a back and forth by e-mail several times.

On e-mail from students with issues regarding administrative matters.

  • For administrative requests (e.g., “I cannot make the test,”), e-mail is fine, of course, and I will attempt to answer you directly.

Please use a York University account when e-mailing me (with regards to the course), so that I can know who it is. Please include [1019] at the beginning of the subject line so I am able to sort it. Send messages in plain text, without attachments.

I do not mind students sending questions by e-mail. Just do not necessarily expect a direct reply. I do read them, and I try to address the issues and questions people raise. If your question or issue remains after some time, do let me know.

Academic Integrity, Honesty, & Plagiarism

The Department of Electrical Engineering & Computer Science's Academic Honesty Guidelines are in effect for this course, as, indeed, they are for any EECS course.

Plagiarism is defined as taking the language, ideas, or thoughts of another, and representing them as your own. If you use someone else's ideas, cite them. If you use someone else's words, clearly mark them as a quotation. Note that plagiarism includes using another's computer programs or pieces of a program. All noted instances of plagiarism will be reported.

These policies are not intended to keep students from working with other students. One can learn much working with others, so this is to be encouraged. Should you encounter any situations for which you are uncertain whether the collaboration is permitted or not, please ask.