Read the problem of the day.

News

1. Solutions to quiz 5 are here.
2. Solutions to quiz 4 are here, here and here.
3. Solutions to quiz 3 are here.
4. 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.
5. Optional problem solving session today (Friday) during class hours.
6. Assignment 1 marks are on ePost.
7. 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 2-colourable, 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.
8. Regular classes have ended. Quiz on Wednesday in class for all students on Tutorials 3 and 5 (Logic only, not sequences).
9. Test 3 marks are on ePost.
10. Test 2 marks are on ePost.
11. 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.
12. The deadline for assignment 2 is extended to April 6 because of your other deadlines and tests.
13. Study session today (March 24) 2:30-4pm at BC 203.
14. 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.
15. Test 3 is postponed by a week to Mar 27.
16. I have been told that classes resume on March 11 (details here).
17. 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.
18. 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.
19. The solution to assignment 1 is here.
20. As mentioned in class the due date of assignment 1 is Feb 25th, not 23rd.
21. 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.
22. An announcement from your class representatives is here.
23. Assignment 1 is online. The deadline is Feb 23 not Feb 21.
24. Minor updates to the test 1 syllabus, as discussed on Jan 26 in class.
25. 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.
26. An announcement from your class representatives is here.
27. You are invited to participate in the York Programming contests. The first one is on Thursday January 15, 16:00-18:00 in Lassonde 1004. For more details click here.
28. Consider being a class representative: see here for details.
29. Welcome to Math/EECS 1028!

General Information

Grades

1. Three in-class tests (15% each). [Note that the test in which a student gets her/his minimum mark will be weighted down to 5%]
   
   1. 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 16-17), 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.
   2. 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.
   3. 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.
2. Homework (15%): Three sets, 5% each
3. 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.
4. 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.7-1.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

• 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

1. The first assignment is here. The deadline is Feb 25, 1:15 pm, not Feb 21.
   The solution to assignment 1 is here.
2. The second assignment is here.
   The solution to assignment 2 is here.
3. The last assignment is here.
   The solution to assignment 3 is here.

List of Topics

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. 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.

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

• Jan 5: First day of class
• Feb 14-20: Reading week
• Mar 6: Last day to drop courses without receiving a grade
• Apr 6: Classes end
• Apr 7: Study day
• Apr 8-24: Exam period

Missed test/exam

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.