Course Information

Instructors

• Walter Whiteley MWF 8:30, Bethune 218. (Suggested Homework )(Updated 12/03/96)
• Alan Dow MWF 1:30 (Suggested Homework ) (Updated 12/7/96)
  Exam period Office Hours: MWF 11:30-2:30 (or drop in).

The exam is Thursday Dec 19 at 8:30 AM. It takes place in the three lecture rooms:
Whiteley's section (Section A) will write in CLH C.
Dow's section (Section B) will write in CLH A & B.

Notes on the content for the exam In response to queries: yes the exam will include:

• generating functions to solve recurrence relations.
  
• combinatorial proofs (the four you were asked to study for Test 2). Click here to review.
• Traversals (part of 8.3) should be treated as good practice at reading and using recursive definitions. If there is a question, the definitions will be given on the exam. However, having read this part would speed things up for you.
• Sorting (8.4): You should know that any sorting by binary comparisons will be at least O(n log(n)) complexity. You should also be able to prove the big O complexity of merge sort, bubble sort etc. (using section 5.3 if you wish). You are expected to know the merge sort algorithm, for others, the relevant algorithm will be described.
• Chinese Remainder Theorem (Section 2.5). You are not responsible for the proof, but you are responsible for knowing what it says and being able to use those facts in examples (solving systems of linear congruences). Note, you are not responsible for the last part of Section 2.5 (Fermat's Little Thoerem, encryption etc.)

Friday December 6 at 8:30, a review session will be held in Bethune 218. This is to make up for the class missed on October 25.

The same is true for the 1:30 Section (except the classroom will be our usual one).

Solutions to Quiz 3, Whiteley's section are available.
Solutions to Quiz 3, Section B = Dow's Section.

Tutorials:

• Wednesday 3:30, Ross N501;
• Thursday 9:30, Ross N501.

Dates:

1. Material for the first test (October 9) is:
   Sections 1.7-1.8 (big O notation) , Appendices 1 (logs) and 2 (pseudocode);
   Sections 2.1-2.2 (algorithms and complexity);
   Sections 2.4-2.5 selected topics: modular arithmetic;
   gcd: definition, algorithms, complexity, uses;
   linear congruences and the Chinese Remainder Theorem.
   
2. Quiz 1 will be Mon Sept 30
   
   • Answers Whiteley Version A
   • Answers Dow Version C
   • Answers Dow Version D
3. Test 1 will be Wed Oct 9
   Review 1
   Review 2
   Check back for solutions. Part 1 is ready
   So is the final part.

   Now Test answers are posted: Version A, Version C and Version D

4. Quiz 2 was Wed Oct 30. Here's some review.
   And some more really good stuff.

   Here's the answers to Dow's.
   Here's the answers to Whiteley's.

   >

5. Test 2 was Wed Nov 13.
   Here are solutions to Whiteley's Test 2.
   Here are solutions to Dow's Test 2 version 1.
   Here are solutions to Dow's Test 2 version 2.

6. Quiz 3 will be Wed Nov 27
7. Assignment 1 will be handed out in the second week of classes.
   You can now get the answers.
8. Assignment 2 will be handed out following Test 1.
   Assignment 2 was handed out Monday October 21
   Here are the answers

Grading scheme

1. 2 graded assignments but grade not recorded.
2. 3 fifteen minute quizzes totalling 20%
3. 2 full class tests worth 20% each
4. Final exam worth 40%. The time/date: 8:30-11:30 Thursday December 19.
5. If it works to your advantage, your term/exam ratio will be switched to 40/60.
6. Click here for old tests and exams (there's not much point, we've had little luck here).

Text: Discrete Mathematics and its Applications by Ken Rosen, McGraw Hill, 3rd edition.

We will cover Chapters 1, 2, 3, 4, 5, 7, 8, and Appendices 1-3. We will however skip the following sections: 1.1-5, 2.3, 3.1, 4.7, 5.2, 7.5, 7.7-8,

Updated coverage: Skipping 4.4, 4.5, 5.4, 5.5, all of 7.