Math/EECS1028: Discrete Math for Engineers
Winter 2015
News
 Solutions to quiz 5 are here.
 Solutions to quiz 4 are here, here and here.
 Solutions to quiz 3 are here.
 An old final for EECS 1019 is here
and the solutions are here.
Note that graphs were not included but algorithm analysis was for that course.
 Optional problem solving session today (Friday) during class hours.
 Assignment 1 marks are on ePost.
 From Ch 10, 11 you need to know definitions of a graph, a tree, bipartite graphs, complete graphs, subgraphs, induced subgraphs, planar graphs, cycles, graph colorings, graph isomorphism and matching. You should be able to determine if a given graph is 2colourable, argue why not (if it is not), and find maximum matchings in small bipartite graphs. You should be able to determine if two given small graphs are isomorphic.
 Regular classes have ended. Quiz on Wednesday in class for all students on Tutorials 3 and 5 (Logic only, not sequences).
 Test 3 marks are on ePost.
 Test 2 marks are on ePost.
 I am away or 2 days and Professor Eric Ruppert will teach in my place on April 1. I will not have office hours on Thursday.
 The deadline for assignment 2 is extended to April 6 because of your other deadlines and tests.

Study session today (March 24) 2:304pm at BC 203.
 As announced in class last week tutorials will run as normal this week. There will be a quiz for the Friday section but not for the Monday sections this week. The quiz will be on the problems from Tutorial 5 and 7.
 Test 3 is postponed by a week to Mar 27.
 I have been told that classes resume on March 11 (details here).
 Tutorial problems due to be covered this week are uploaded. Also I am starting a problem of the day to get you to think about Math as we wait for classes to resume. Go to the problem of the day by clicking here. Solutions will typically appear a day later.

Due to the strike, all classes and labs are suspended at York until further notice. Official York U announcements regarding the strike are
here. If you use Twitter, you can also monitor this feed.
 The solution to assignment 1 is here.

As mentioned in class the due date of assignment 1 is Feb 25th, not 23rd.
 You need not complete Q4 of assignment 1. You can hand it in with the next assignment. If you have done it and prefer to hand it in, that is ok too.
 An announcement from your class representatives is here.
 Assignment 1 is online. The deadline is Feb 23 not Feb 21.
 Minor updates to the test 1 syllabus, as discussed on Jan 26 in class.
 I will be present at the study session organized by your class representatives, in Bethune 105B on Wednesday, January 28th, 2015 from 2:30 pm to 4:30 pm.

An announcement from your class representatives is here.
 You are invited to participate in the York Programming contests. The first one is on Thursday January 15, 16:0018:00 in Lassonde 1004. For more details click here.
 Consider being a class representative: see here for details.
 Welcome to Math/EECS 1028!
General Information
Instructor: Suprakash Datta
Office: CSEB, room 3043
Telephone: (416) 7362100 ext. 77875
Facsimile: (416) 7365872
Lectures: Monday, Wednesday, Friday 1:302:30 pm in Curtis Lecture Hall (CLH) G
Office Hours: Tuesday, Thursday: 1  3 pm or by appointment, in CSEB 3043.
Email: [lastname]@cs.yorku.ca (While you are free to send me email from
any account, please realize that email from domains other than yorku.ca
have a higher chance of entering my spam folder. I do check my spam folder
irregularly , but to be safe, consider using your cs account when sending
me email.)
Grades
Grades can be checked online by clicking here
 Three inclass tests (15% each). [Note that the test in
which a student gets her/his minimum mark will be weighted down to 5%]

Test 1: Jan 30 (at class time). Syllabus: Everything covered upto and including Jan 23, i.e., Sections 1.1, 1.2 (only the section titled "Translating English Sentences" (pg 1617), 1.3, 2.1, 2.2, 2.3, 2.4. Omit the section on Page 15, and the part on Recurrence relations and Special integer sequences starting at the bottom of page 157 and ending on the bottom of page 162.
Logarithms  Appendix 2. Inference in Propositional Logic, Sec 1.6, upto and including Pg 75.
Some sample problems are here and the solutions are here.
Solutions to test 1 are here and here.

Test 2  Feb 27, at class time.
Syllabus: Everything covered from Jan 26 upto and including Feb 11.
Sections 1.3 (skip the part titled "Propositional satisfiability" on page 30 to page 34),1.4 (omit pages 50,51,52),1.5.1.6,1.7,1.8 (omit pages 103,104,105),5.1.
Some sample problems are here and the solutions are here.
Solutions to test 2 are here and here.

Test 3: Mar 27 (postponed by a week from Mar 20)
Syllabus: Everything covered from Feb 13 upto and including Mar 20.
Strong Induction (5.2), Cardinality (2.5), Pigeohole Principle (6.2), Counting (6.1, 6.3, 6.4).
Solutions to test 3 are here and here.
 Homework (15%): Three sets, 5% each
 Tutorials (10%): Every second tutorial will have a short quiz (making a total of about 5 quizzes). These will carry a weight of 2% each. If you get all questions correct, you get 2%, If you do not but have attended both tutorials then you get 1% extra subject to a max score of 2%. If you do not attend the quiz you get no marks, except if you have a documented medical reason.
 Final (45%): (set by the registrar's office).
Syllabus  everything covered.
Time/date: Thu, 23 Apr 2015, 9:00 12 noon in ACW 006, ACW 005
Lectures
 Lecture 1 (Jan 5): My slides are here. Introduction to Discrete Mathematics. Preliminaries.
 Lecture 2 (Jan 7): Preliminaries continued. Same slides as before.
 Lecture 3 (Jan 9): Sets and Functions. My slides are here.
 Lecture 4 (Jan 12): Set operations and Functions. No new slides.
 Lecture 5 (Jan 14): Functions continued. Reading so far: Ch 2.1, 2.2, 2.3.
Some special functions. My slides are here.
 Lecture 6 (Jan 16): Functions continued. Arithmetic and Geometric Series.
My slides are here.
 Lecture 7 (Jan 19): Arithmetic and Geometric Series  continued. No new slides.
 Lecture 8 (Jan 21): Propositional Logic (Ch 1). My slides are here.
 Lecture 9 (Jan 23): Propositional Logic (Ch 1) continued  no new slides. We covered upto slide 27 in the last set of slides
 Lecture 10 (Jan 26): Propositional Logic (Ch 1) continued  no new slides. Predicate Logic. My slides are here.
 Lecture 11 (Jan 28): Problem solving for test practice.
 Lecture 12 (Feb 2): Predicate logic continued. My slides are here.
 Lecture 13 (Feb 4): Predicate logic continued.
 Lecture 14 (Feb 6): Predicate logic continued. Introduction to Proof techniques (Ch 1.71.8) My slides are here.
 Lecture 15 (Feb 9): Proof techniques continued.
 Lecture 16 (Feb 11): Proof techniques continued. Mathematical Induction. My slides are here.
 Lecture 17 (Feb 13): Proof techniques continued. Strong Induction; the Pigeonhole Principle. My slides are here.
 Lecture 18 (Feb 23): Cardinality (Ch 2.5). My slides are here.
 Lecture 19 (Feb 23): Problem solving for the second test.
 Lecture 20 (Mar 2): Cardinality continued.
 Lecture 21 (Mar 11): Finish Cardinality. No new slides.
 Lecture 22 (Mar 13): Introduction to counting (Ch 6).
My slides are here.
 Lecture 23 (Mar 16): Introduction to counting (Ch 6) continued. Permutations. No new slides.
 Lecture 24 (Mar 18): Introduction to counting (Ch 6) continued. Combinations. No new slides.
 Lecture 25 (Mar 20): Introduction to counting (Ch 6) continued. The Binomial Theorem. No new slides.
 Lecture 26 (Mar 23): More complex counting (Ch 6.5). No new slides.
 Lecture 27 (Mar 25): Test 3 review.
 Test 3: (Mar 27)
 Lecture 28 (Mar 30): More complex counting (Ch 6.5). My slides are here. Introduction to graphs.
 Lecture 29 (Apr 1): Graphs. Guest lecture by Professor Eric Ruppert.
 Lecture 30 (Apr 3): Graphs. My slides are here.
 Lecture 31 (Apr 6): Graphs. No new slides.
Tutorials
The tutorial times are:
Tutorial Section 1 : M 14:3016:30 TEL 1005
Tutorial Section 2 : M 19:3021:30 CLH 110
Tutorial Section 3 : F 14:3016:30 CLH 110
 Tutorial session 1: Week of Jan 12. Attendance is mandatory, no quiz.
The problems covered are here and the solutions are here.
 Tutorial session 2: Week of Jan 19. Attendance is mandatory, quiz.
The problems covered are here and the solutions are here.
 Tutorial session 3: Week of Jan 26. Attendance is mandatory, no quiz.
The problems covered are here and the solutions are here.
 Tutorial session 4: Week of Feb 2. Quiz for Friday tutorial students only.
The problems covered are the problems on test 1.
 Tutorial session 5: Week of Feb 9. Quiz for Monday tutorial students only. The problems covered are here and the solutions are here.
Note that all these problems may not have been covered in the tutorial.
 Tutorial session 6: Week of Feb 23. No quiz.
The problems covered are the sample problems for test 2.
 Tutorial session 7: Week of Mar 2. The problems covered are here and the solutions are here.
 Tutorial session 8: Week of Mar 16. The problems covered are here. There will be a quiz for the Friday section but not for the Monday sections this week. The quiz will be on the problems from Tutorial 5 and 7.
 Tutorial session 9: Week of Mar 23. The problems covered are here.
 Tutorial session 10: Week of Mar 30. (No tutorial on Friday because it is a holiday). The problems covered are here.
 Tutorial session 11: Week of Apr 6. There will be a quiz on Tutorials 8 and 9.
Assignments
 The first assignment is here. The deadline is Feb 25, 1:15 pm, not Feb 21.
The solution to assignment 1 is here.

The second assignment is here.
The solution to assignment 2 is here.

The last assignment is here.
The solution to assignment 3 is here.
List of Topics
A list of topics and expected learning outcomes is here.
Resources
Textbook
Kenneth H. Rosen. Discrete Mathematics and Its Applications, Seventh
Edition. McGraw Hill, 2012.
Available from the University bookstore. Textbook
web site.
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.
AddisonWesley, 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.
Academic Honesty
It is important that you look at the departmental guidelines
on academic honesty.
Although you may discuss the general approach to solving a problem with
other people, you should not discuss the solution in detail. You must not
take any written notes away from such a discussion. Also, you must list on
the cover page of your solutions any people with whom you have discussed
the problems. The solutions you hand in should be your own work. While
writing them, you may look at the course textbook and your own lecture
notes but no other outside sources.
Important Dates
See this page for the full list.
 Jan 5: First day of class
 Feb 1420: Reading week
 Mar 6: Last day to drop courses without receiving a grade
 Apr 6: Classes end
 Apr 7: Study day
 Apr 824: Exam period
There are no classes on Feb 16 (Family day) and April 3 (Good Friday).
Missed test/exam
If you miss a test or the final due to medical reasons you are required to contact the instructor within 7 days of the scheduled exam with documentation. York University has a new form that your doctor should fill out. You can download it by clicking here.
If you miss an assignment or test the weight will be transferred to the final. If you miss the final, you have to get the instructor to sign a deferred standing agreement within 7 days of the scheduled exam (the instructor has the right to refuse to agree, and in that case the student can petition to take the deferred examination). The department will arrange for a deferred examination at the beginning of the following term.