MACM 101-D2 Discrete Mathematics I
Click here for the Burnaby section of MACM 101
23/04/2007 The final marks are now available on go.sfu.ca.
17/04/2007 A correction on the study sheet: a complete undirected graph on n vertices has (n-1)n/2 edges, not n^2/2.
13/04/2007 The updated study sheet is now posted here. Please email me if you notice any mistakes/omissions/inconsistencies with textbooks.
09/04/2007 The solutions for assignment 5 are now posted here .
29/03/2007 Final exam office hours will be on April 16th, 12pm-3pm, at my office at Surrey (4072). Please let me know if this is not convenient for you.
28/03/2007 The solutions for test 2 are now posted here .
26/03/2007 Assignment 5 is now posted here . The due date is next Monday, April 2nd.
Old announcements
Lectures: Mon/Wed/Fri 10:30am-11:20am, in 3090 (Mon and Wed) and 2600 (Fri)
Tutorials: Fri 9:30-10:20 in 3040, Fri 11:30-12:20 in 3290, Fri 12:30-13:20 in 3050.
Instructor: Antonina
Kolokolova , email: akol@cs.sfu.ca, Surrey office 4072, Burnaby office TASC 1, 9205
Instructor office hours: Mon and Wed after class in 4072 , or by appointment.
Final exam office hours: April 16th, 12pm-3pm.
Note: By far the best way to contact me is by email. Please
email me whenever you have any questions.
TA: Rong She (email rshe, at cs.sfu.ca)
The course is based on the following textbook:
Grimaldi, "Discrete and combinatorial mathematics".
We will cover most of the material in Part 1, skipping over some subsections.
Academic calendar: first class is Jan 8, last day to drop is Jan 26 (with WD, Feb 9), last class is Apr 4.
Assignments are due (tentative!): Jan 22, Feb 05, Feb 26, Mar 14 and Apr 02 at the beginning of the lecture.
Tests are (tentative!): Feb 21 and Mar 21.
Final exam: April 18, 12:00-15:00, room 3310.
Marking scheme: 5 assignments at 5% each, 2 midterms 15% each,
participation 10%, and a final exam 35%.
|
Assignment 1. Due Jan 22, 2007
|
Solutions to assignment 1.
|
|
Assignment 2. Due Feb 5, 2007
|
Solutions to assignment 2.
|
|
Assignment 3, part 1. Due Feb 16, 2007
|
Solutions to assignment 3, part 1.
|
|
Test 1. Feb 21, 2007
|
Solutions to test 1.
|
|
Assignment 3, part 2. Due Feb 26, 2007
|
Solutions to assignment 3, part 2
|
|
Assignment 4. Due Mar 14th, 2007
|
Solutions to assignment 4.
|
|
Test 2. Mar 21, 2007
|
Solutions to test 2.
|
|
Assignment 5. Due April 2nd, 2007
|
Solutions to assignment 5.
|
Policy on collaboration: The work you submit must
be your own. You may discuss problems from assignments with each
other; however, you should prepare written solutions alone.
Plagiarism is a serious academic offense and will be dealt with
accordingly.
The study sheet is available here (final version)
- 08/01: Lecture 1.
Sections 1.1, 1.2 (rules of sum and product, permutations, started combinations).
- 10/01: Lecture 2. Section 1.3 (binomial theorem, example similar to 1.23)
- 12/01: Lecture 3. Section 1.4 (combinations with repetition, in particular examples 1.33 and 1.39)
- 15/01: Lecture 4. Section 2.1 (fundamentals of logic: truth tables, primitive statements, AND, OR, NOT)
- 17/01: Section 2.1,(fundamentals of logic: implication)
- 19/01: Section 2.2 (the laws of logic)
- 22/01: Section 2.2, 2.3 (the laws of logic and rules of inference)
- 24/01: Section 2.3 (rules of inference)
- 26/01: Section 2.4 (quantifiers)
- 29/01: Section 2.5, 3.1 (quantifiers and intro set theory)
- 02/02: slides ,Section 3.2, 3.3, 15.4 or Gossett 2.1, 2.5 (set operations, boolean algebra)
- 05/02: Sections 5.1, 5.2 in Grimaldi, 12.1 in Gossett (relations and functions)
- 07/02: Sections 5.3, 7.1 in Grimaldi, 12.2 in Gossett (properties of relations and functions)
- 09/02: Sections 7.2, 7.3 in Grimaldi, 12.2 in Gossett (properties of relations, equivalence)
- 12/02: Sections 7.4 in Grimaldi, 12.2 in Gossett (properties of relations, equivalence)
- 14/02: Section 5.2 in Grimaldi (functions)
- 16/02: Sections 2.5, 4.1 in Grimaldi, 3.1 in Gossett (Methods of proof)
- 19/02: Midterm review
- 21/02: Midterm
- 23/02: Appendix 3 in Grimaldi, Andrei Bulatov's slides. (Uncountable and countable sets)
- 26/02: Section 4.1 in Grimaldi, 3.3 in Gossett (Intro to math. induction)
- 28/02: Section 4.1 in Grimaldi, Andrei Bulatov's slides. (More examples of induction, strong induction)
- 02/03: Section 4.2 in Grimaldi, Andrei Bulatov's slides. (Recursive definitions)
- 05/03: Section 4.3 in Grimaldi, 3.1.3 in Gossett (prime numbers)
- 07/03: Sections 4.4, 4.5 in Grimaldi, 3.1, 3.2 in Gossett (Euclid's algorithm, fundamental theorem of arithmetic)
- 09/03: Sections 5.6, 5.7 in Grimaldi, 12.1, 4.2 in Gossett (functions, complexity, O-notation)
- 12/03: Section 5.5 in Grimaldi, 5.3 in Gossett (pigeonhole principle), halting problem.
- 14/03: Section 5.5 in Grimaldi, 5.3 in Gossett (Pigeonhole principle)
- 16/03: Sections 11.1, 11.3, in Grimaldi, Andrei Bulatov's slides. (intro graphs)
- 19/03: Midterm review
- 21/03: Midterm
- 23/03: Sections 11.2, 11.4, 11.5 in Grimaldi, Andrei Bulatov's slides: Graphs, Euler's formula, planarity)
- 26/03: Sections 12.1 and 12.2, Andrei Bulatov's slides:Trees and Rooted trees
- 28/03: Section 6.1, 6.2 in Grimaldi, 9.2 in Gossett (languages, finite automata, regular expressions)
- 30/03: Section 6.2, 6.3 in Grimaldi, 9.2, 9.3 in Gossett.(automata, grammars)
- 02/04: Stephen Rudich's slides, Gossett 1.2 (stable marriage problem)
- 04/04: Review.