## Course Information

### Instructors

For more counting problems and additional techniques, the book "Introductory Combinatorics" by Kenneth Bogart is on reserve in Steacie Library (under Math 2320). This is also a second reference for Generating Functions.

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.)
Walter Whiteley will hold an extra 'review tutorial' for Math 2320 on Monday December 16 at 1:30-3:30 in SLH B. This is open to all students in the course.

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
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.

>

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

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.
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.

This text and the Instructor's Solution Manual (solutions to the even numbered problems) are on 2 hr reserve in Steacie Library.

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.

• Walter Whiteley: Office S616 Ross. Phone 33971
Office hours: 9:30- 10:00 MWF, and by appointment (see me before or after class or e-mail me).
E-mail Walter.Whiteley@mathstat.yorku.ca

• Alan Dow: Office N528Ross. Phone 22594. E-mail adow@yorku.ca