News

1. Test 2 is moved to March 2.
2. Amgad will have office hours Jan 28, 3-4 pm in Las 2013.
3. One of the TAs, Amgad Rady will have office hours 3-4 pm Jan 25 in LAS 2013.
4. The Moodle page has a sample test for practice to help you prepare for Test 1. The format and the length of Test 1 will be very similar to the sample.
5. Tutorial 1 solutions are on Moodle.
6. The marks and the solutions for the background quiz are on Moodle.
7. There will a quiz in the tutorial sections this week (Jan 8). Please go to your own tutorial section as the TA will not be able to enter grades otherwise. The quiz is based on a small subset of high school topics. There is no need to prepare for it. It is 1 hour long and you can leave once you are done. Regular tutorials (i.e., problem solving) will start next week.
8. Welcome to Math/EECS 1028!

General Information

Grades

1. Tests (35%)
   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 31). Syllabus: Ch 1.1, 1.3 (leave out pages 31-34), 1.6 (leave out pages 76-77), 2.1, 2.2, 2.3, 2.4, and everything on the slides covered up to and including Jan 26. A sample test and its solutions are on Moodle.
   2. Test 2 (Mar 2, changed from Feb 28): Predicate Logic, Inference in Predicate Logic. Proofs. A sample test and its solutions are on Moodle.
   3. Test 3 (Mar 21): Proofs, PigeonHole Principle and Counting. A sample test and its solutions are on Moodle. Syllabus: 1.7, 1.8, Ch 6.1-6.5, 5.1-5.3 (We did not do structural induction), Ch 8.5.
2. Tutorials (10%): Every second tutorial will have a short quiz (making a total of 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.
3. Homework (15%):
4. Final (40%):  date/time TBA by the registrar's office. Syllabus - everything covered. All sections listed for tests 1,2,3 and 10.1, 10.2, 11.1. You must be able to use the graph theory results to infer facts about given graphs.

Lectures

• Lecture 1 (Jan 5): Intro to Discrete Math. My slides are here. We covered slides 1 to 9.
• Lecture 2 (Jan 8): Intro to Discrete Math - continued. We covered slides 9 to 22.
• Lecture 3 (Jan 10): Two sample proofs. My slides are here. Functions. My slides are here. We covered the first 6 pages of this set.
  Practice problems: Pg 125-6 Q 11, 18, 20c,d, 23c, 26, 38; Pg 136-8 Q 48, 50, 59.
• Lecture 4 (Jan 12): Power sets (done on the board), Functions - continued. We covered slides 6-10 in the previous set.
  Practice problems: Pg 152-5 Q12, 14, 21, 23, 32.
• Lecture 5 (Jan 15): Functions - continued.
• Lecture 6 (Jan 17): Sequence and Series. My slides are here.
• Lecture 7 (Jan 19): Introduction to Propositional Logic. Ch 1.1, 1.3, My slides are here.
• Lecture 8 (Jan 22): Introduction to Propositional Logic - continued.
• Lecture 9 (Jan 24): Inference in Propositional Logic. Ch 1.6, pg 71-75 only, My slides are here.
• Lecture 10 (Jan 26): Inference in Propositional Logic.
• Lecture 11 (Jan 29): Problem solving for test 1. We did some of these problems.
• Lecture 12 (Feb 2): Introduction to Predicate Logic. My slides are here.
• Lecture 13 (Feb 5): Predicate logic continued.
• Lecture 14 (Feb 7): Predicate logic continued.
• Lecture 15 (Feb 9): Finish Predicate logic. Proof techniques. My slides are here.
• Lecture 16 (Feb 12): Proof techniques.
• Lecture 17 (Feb 14): Proof techniques.
• Lecture 18 (Feb 16): Proof techniques.
• Lecture 19 (Feb 26): Recursion. My slides are here.
• Lecture 20 (Feb 28): Midterm review.
• Lecture 21 (Mar 5): Finish recursion. Start Combinatorics. My slides are here.
• Lecture 22 (Mar 7): Combinatorics. No new slides.
• Lecture 23 (Mar 9): Combinatorics. No new slides.
• Lecture 24 (Mar 12): Combinatorics. No new slides.
• Lecture 25 (Mar 14): Combinatorics. No new slides. Cardinality of infinite sets.
• (Mar 16): Quiz, no lecture
• Lecture 26 (Mar 19): Cardinality of infinite sets. My slides are here.
• Lecture 27 (Mar 23): Cardinality of infinite sets - continued.
• Lecture 28 (Mar 26): Introduction to graphs. My slides are here.
• Lecture 29 (Mar 28): Graphs - continued. More slides are here.
• Lecture 30 (Apr 2): Graphs - continued.
• Lecture 31 (Apr 4): Graphs - continued.
• (Apr 6): Quiz.

Assignments

1. Assignment 1 (2%) -- High school topics. Do this assignment if you did not get 72% or above on the background quiz. Published on Moodle on Jan 19.
2. Assignment 2 (4%) -- Functions, Logic, Inference. Released on Moddle on Feb 9.
3. Assignment 3 (5%) -- Proofs, Combinatorics. Released on Moddle on Mar 5.
4. Assignment 4 (4%) -- Combinatorics. Released on Moddle on Mar 23.

Learning objectives and list of topics

• Basic tools and techniques in discrete mathematics
  • Set Theory, Functions and Relations
  • Propositional and Predicate logic
  • Induction, recursion
  • Series and series sums
  • Introductory Graph Theory
• Precise and rigorous mathematical reasoning -- Writing proofs

We will cover the following topics (if time permits).

• Ch 1: Logic and Proofs. (Omit the subsection on page 51 called "Logic programming".
• Ch 2: Sets, functions, sequences, sums. (Omit 2.6: Matrices)
• Ch 5: Induction and recursion. (Omit 5.4, 5.5)
• Ch 6: Counting
• Ch 8: Advanced counting techniques (8.1 - 8.3)
• Ch 9: Relations
• Ch 10: Graphs (10.1-10.5).
• Ch 11: Trees (11.1, 11.2)

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.
• Bernard Kolman, Robert C. Busby and Sharon Cutler Ross. Discrete Mathematical Structures. Pearson, 2004.
• Daniel Solow. How to Read and Do Proofs: An Introduction to Mathematical Thought Processes. Wiley, 2002.

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 (from here)

• Jan 4: First day of class
• Feb 17-23: Reading week (no classes or tests)
• Mar 30: Good Friday
• Apr 6: Classes end
• April 5, 7, 8: Study days
• Apr 9-23: Exam period

Missed test/exam

If you miss an assignment or test for medical reasons, 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. If you miss a test or final for some non-medical reasons, please contact the instructor. These will be dealt with a case-by-case basis.