• The final  will be on Wednesday, April 16, 2008 in SUR 5140, 5240.
  -It is three hours: 15:30-18:30.
  -For cheating sheet you can choose between just one of these options:
         1- You can bring only a one-sided page of any size that is prepared by yourself and use it during the
             exam (from beginning to the end).
       OR,
         2- You can open your book or any other source ONLY in the last hour of the exam.
  -While the exam will cover all you have seen in this course (Listed in Required Reading bellow) more emphases is on the materials covered after the midterm.
  -The level of difficulty of the questions will be the same as assignments and harder than midterm.
  -I will have office hours on Wednesday from 11:00 to 15:00.
   
• The midterm will cover, counting, propositional logic, quantifiers, induction and set theory.
  -There is no question on functions. You do not need to know any thing more than required reading stated bellow.
  -You can copy up to 2 pages from the book and take it to the exam, moreover one cheating sheet is allowed
  as long as you prepare it by yourself.
  -The level of difficulty of the questions will be the same as assignments except for some bonus ones.
  -I will extend my office hour on Monday from 11:30 to 3:00. On Tuesday Javad has his regular office hour.
• Change in TAs: Louisa is replaced by Mahdi.
• The midterm will be on Wednesday Feb 27 in the class.
• The assignments will be collected in the tutorials.
• No tutorials in the first week
• First lecture: Monday Jan 7 10:30-11:20, SUR 3090.

• Habil Zare
  PHD student, School of Computing Science, SFU
  E-mail: hzare AT cs DOT sfu DOT ca

Class

• Mondays, Wednesdays and Fridays: 10:30-11:20, SUR 3039 

Teaching Assistants

• Javad Safaei Mehranpour
  E-mail: jsa AT sfu DOT ca
• Mahdi Javadi
  E-mail: sjavadiATcsDOTsfuDOTca

Tutorial sessions:

•  Fridays 9:30-10 or 11:30-12:20 or 12:30- 1:20, SUR 3120

Office Hours

• Office hours by Professor: Mondays and Wednesdays 11:30-12:30, SUR 4064
• Office hours by TA:  Tuesdays  12:30-13:20, SUR 5302

Topics:

    Look at course outlines.

• Counting:
  For a summary of counting techniques,  look at the table on page 41. If any of those four basic formulas is not fluent for you, refer to the relevant blue box and examples in the book.

• Propositional Logic:
  You need to understand the table on page 49 and the Laws of Logic on page 58, well enough to solve the problems such as examples 2.7 and 2.16. If you have any difficulties read the pages  47-65.

• Quantifiers:
  If you had seen use of quantifiers before, make sure you understand the tables on pages 92 and 96. Otherwise read pages 86-100.

• Induction:
  This is the most important part of this course. We will cover pages 193-207. The examples you need to work with are not harder than homework 4.

• Set Theory:
  You need to understand the concept of sets explained on pages 123-128. (We will talk about power set.) Well known sets of numbers are defined on page 133 and the operations on sets appear on page 133. You need to understand, know how to prove and use the laws of logic (page 139). Finally, if you have any problem understanding Venn diagrams look at pages148-149.

• Functions:
  From page 247 to 258 you need to review the product of two sets, how a function is defined formally, and what it means for a function to be one-to-one. Onto functions are explained on pages 260-261. Then we jump to page 278 to read about composition and inverse of functions. When you finish page 282, then you will have seen all the basic concepts about functions but you can continue to page 288 to see more examples and theorems. To make sure you have understood this chapter fully, check if you can follow up the proofs for these theorems.

• Pigeonhole principle: The principle is on page 273 and there are some examples till page 275.

• Big Oh Notation: pages 290-293.

• Induction  (more advanced applications): We prove the formula for base case.
  Then assuming  it is true for k, we prove it is for k+1.

• Recursive definitions: It is an easy concept. Examples are on pages: 210-218.

• Number theory: On pages 221-237, Division Algorithm, Prime Numbers, gcd,
  Euclidean Algorithm  and  Fundamental  Theorem of arithmetic are explained.
  

• Homework 1
  page 12: 11 - page 13: 22,24 -  page 25:25e (look at page 23) - page 35: 12 - (look at page 29) - page 44:22.
  Due date: Friday Jan 18

• Homework 2
  page 54: 4,6,7,8f - page 67: 19,20.
  Due date: Friday Jan 25

• Homework 3
  from page 100: 1f, 2a(ii), 3e,7,9a(i,iv).
  Due date: Friday Feb 1

• Homework 4
  from page 102: 18c-d, 21d - from page 208: 1,2.

  Due date: Friday Feb 8

• Homework 5
  from page 134: 1,2,4,5,10bcd - from page 146: 1cg,2 (look at thef table on page 134, part m), 5acf, 8, 14a, 17a.

  Due date: Friday Feb 15

• Homework 6
  from page 134: 6af - from page 146: 1ef, 4a(i,vi)b(i,v,vi), 7ab, 13, 14c, 17bc, 19f - from page190: 9.

  [Bonus] from page 189: 4.

  Due date: Friday Feb 22

• Homework 7
  from page 252: 7 - from page 258: 1ad, 15ef - from page288: 10c.

  Due date: Friday Feb 29

• Homework 8
  -page 252: 13a,
  -page 258: 2, 7abe, 21,

  15c (You may draw a diagram to get intuition, but it is not enough to prove anything)
  -page 288: 3,9
  -page 307: 30 (Look at page 282, Def 5.19)
  -Prove the Fibonacci formula on page 457 by induction.

  Due date: Friday March 14

• Homework 9
  page 230: 2,4, 9, 10, 11, 28
  Due date: Friday March 21

• Homework 10
  page 236: 1,3,4,5,,8,11,20.

  Due date: Friday March 28

• Homework 11
  -page 277: 2,3,7
  -page 293: 1,3.
   Due date is on Friday April 4.

Textbook:

• Ralph P. Grimaldi, Discrete and Combinatorial Mathematics, Addison-Wesley, 2004 (Fifth Edition)

• Homework assignments (the best 10)                              20%

• Quizzes (the best 10)                                                      20%

• Midterm                                                                         20%

• Final exam                                                                      40%

• Bonus marks (for those who wan to get an A+)
  There are several ways to get them including: contribution in the class,

  solving extra assignments, solving the problems in the tutorials, etc.

   You can always check your marks at: Gradebook.