MACM 101-D2: Discrete Mathematics (Spring 2014)

Classroom: K9500 (Mon, Fri); BLU9660 (Wed)

Instructor: Binay Bhattacharya Office: TASC I 8017, e-mail: binay@cs.sfu.ca

Office hours (Binay): MF 1:00pm-2:30pm


TA: Kamyar Khodamoradi (e-mail) kka50@sfu.ca

TA: Vladyslav Sokol (e-mail)vsokol@sfu.ca

Office hours (TA): (Room ASB 9838) 2pm-3pm (Tuesday, Wednesday and Friday); 10am-11am (Friday)

You can find the tutorial schedule here.
The information on the classrooms can be found here.

Messages/Hand-outs


  • Final Exam Date: April 14, Time: 12 noon-3:00pm, Room: AQ 3182
  • 10/04/2014: Solution to homework 8 can be found here
  • 09/04/2014: Materials covered in the lectures are discussed here
  • 09/04/2014: Sample exams can be found here
  • 05/04/2014: Solution to homework 6 can be found here
  • 02/04/2014: Homework #8 is assigned; due date 03:30pm, 09/04/2014 (sharp)
  • 03/04/2014: Solution to homework 7 can be found here
  • 26/03/2014: Homework #7 is assigned; due date 3:30pm, 02/04/2014 (sharp)
  • 23/03/2014: Lecture notes on Balls in Bins problem can be found here
  • 20/03/2014: Solution to Midterm 2 can be found here
  • 18/03/2014: Class notes on Recursive definitions and functions can be found here
  • 18/03/2014: The due date of homework 6 is changed from March 21 to March 24.
  • 15/03/2014: Solution to homework 5 can be found here
  • 14/03/2014: Homework #6 is assigned; due date 3:30pm, 21/03/2014 (sharp)
  • 07/03/2014: Hints to hw3, hw4 are here
  • 05/03/2014: Midterm 2 covers topics 2.5, 3.1, 3.2, 3.3, 3.4, 4.1
  • 05/03/2014: Sample exams can be found here
  • 04/03/2014: Solution to homework 4 can be found here
  • 03/03/2014: Homework #5 is assigned; due date 3:30pm, 12/03/2014 (sharp)
  • 01/03/2014: Solution to homework 3 can be found here
  • 24/02/2014: Homework #4 is assigned; due date 3:30pm, 03/03/2014 (sharp)
  • 24/02/2014: Midterm #2 is scheduled on March 10, 2014
  • 07/02/2014: Homework #3-1 is assigned; due date 3:30pm, 22/02/2014 (sharp)
  • 07/02/2014: Solution to Midterm 1 can be found here
  • 01/02/2014: Solution to homework 2 can be found here
  • 29/01/2014: Midterm 1 covers topics 1.1, 1.2, 1.3, 1.4, 2.1, 2.2, 2.3
  • 29/01/2014: Solution to homework 1 can be found here
  • 24/01/2014: Part 2 of homework #2 is assigned.
  • 22/01/2014: Sample exams can be found here
  • 20/01/2014: Homework #2-1 is assigned; due date 3:30pm, 31/01/2014 (sharp)
  • 15/01/2014: Midterm #1 is scheduled on Feb. 3, 2014
  • 10/01/2014: Homework #1 is assigned; due date 3:30pm, 17/01/2014 (sharp)
    Hand in the assignment in the class.

    Course outline

    Lectures

    3:30pm-4:20pm, Monday, Wednesday, Friday

     

    <\tr>

    Week

    Date

    Topics

    Other Information

    1

    		 06/01 Course Organization Read sections 1.1 and 1.2
    08/01 discussed sum and product rule; computed the number of structurally different binary trees with 4, 5, 6 ... nodes; finished section 1.1 Read sections 1.3 and 1.4
    10/01 started section 1.3

    2

    		 13/01 Permutation (contd.)
    15/01 Combinations, Binomial Theorem Text section 1.3
    17/01 Combinations with repetitions Text section 1.4

    3

    		 20/01 Combinations with repetitions completed. Read sections 2.1, 2.2 and 2.3 of the text
    22/01 Fundamentals of Logic (Chapter 2) started. Section 2.1 is covered
    24/01 Discussed logical equivalence (section 2.2) Read section 2.3

    4

    		 27/01 Logical Implication: rule of inference (2.3) started; various inference rules are discussed
    29/01 Rules of Inference (section 2.3) topic is covered. Read section 2.4
    31/01 The Use of Quatifiers; covered section 2.4

    5

    		 03/02 Midterm 1
    05/02 Logical Equivalence. Started section 2.5 Read section 2.5
    07/02 Proof of Theorms

    6

    		 17/02 Proof of Theorems continued
    19/02 Section 2.5 completed Read Chapter 3 on Sets
    21/02 Set Theory Section 3.2, 3.3 and 3.4

    7

    		 24/02 Completed sections 3.2 and 3.3 Read section 3.4 and Chapter 4
    26/02 Completed section 3.4 Read the induction part of Chapter 4.
    28/02 Induction principle covered

    8

    		 03/03 Examples on Induction
    05/03 Considered Strong Induction
    07/03 Recursive definitions (Chapter 4) Midterm 2 on Monday

    9

    		 10/03 Midterm 2 Start Chapter 5 next week
    12/03 Covered Section 5.1 on Relations Read Section 5.2
    14/03 Started discussing Functions (Section 5.2)

    10

    		 17/03 Covered sections 5.2 and 5.3 Class notes on Recursive definitions and Functions (sections 4.2, 5.1,5.2, 5.3) can be found here
    19/03 Counting using functions Read sections 5.4,5.5,5.6
    21/03 Special functions; and composition, inverse of functions Read 5.5 and Chapter 7 (sections 1 through 4)

    11

    		 24/03 Pigenhole principle started
    26/03 Pigeonhole principle completed 5.5
    28/03 Relations Sections to be covered 7.1, 7.2, 7.3, 7.4

    12

    		 31/03 Covered partial order relations Read section 7.4 on equivalence relation
    02/04 Covered 7.4 Read 4.3
    04/04 Number Theory (sections 4.3, 4.4, 4.5)

    13

    		 07/04 Number Theory
    09/04 Course review Last day of the class

    Textbook

    • Discrete and Combinatorial Mathematics by Ralph P. Grimaldi

    Homework Assignments:

    • 10/01/2014: #1 due Friday January 17 at 3:30pm SHARP
      • Sections 1.1 and 1.2 (page 11) 2, 4, 16, 34, 36
      • Section 1.3 (page 24) problems 4, 8, 12, 18
      • Problem: Let B(n) denote the number of possible distinct triangulations of a convex polygon with n (n >= 3) vertices. Using the method discussed in the class, compute B(5) and B(6).
    • 22/01/2014: #2-1 due January 31 at 3:30pm SHARP
      • Section 1.4 (page 34): 1, 8, 10, 14, 19, 20
    • 24/01/2014: #2-2 due January 31 at 3:30pm SHARP
      • Section 2.1 (page 54): 4, 5, 8, 10, 12
      • Section 2.2 (page 66): 2, 4, 6, 14, 16, 18
      • Problem: Rephrase problem 17 (page 66) using only the not, or, and connectives.
    • 07/02/2014: #3-1 due February 22 at 3:30pm SHARP Homework 3-1
    • 24/02/2014: #4 due March 3 at 3:30pm SHARP Homework 4
    • 03/03/2014: #5 due March 12 at 3:30pm SHARP Homework 5
    • 14/03/2014: #6 due March 21 at 3:30pm SHARP Homework 6
    • 26/03/2014: #7 due April 2 at 3:30pm SHARP Homework 7
    • 02/04/2014: #7 due April 9 at 3:30pm SHARP Homework 8

    Marking

    • Homework assignments: 15%
    • Midterm (2): 25%
    • Final: 60%
    • This happens rarely, but if your final exam grade is better than the average as calculated above, the final exam grade will prevail.