CO 220 Introduction to Combinatorics

Winter 2009

Who?

Instructor

David G. Wagner
office: MC 5040, phone: x32487
dgwagner@math.uwaterloo.ca
OFFICE HOURS: Weds 2:00-3:00 or by appointment.

Teaching Assistant

Stuart MacGillivray
office: MC 6204, phone: x36696
s2macgillivray@uwaterloo.ca
OFFICE HOURS: Thurs 1:00-2:00 or by appointment.

FINAL EXAM PERIOD OFFICE HOURS

D.G. Wagner: April 8, 15, 20, 21, 22 from 2:00 to 3:00.
S. MacGillivray: April 17 from 2:00 to 3:00, and April 21 from 3:00 to 4:00.

Where and When?

Lectures: MWF 11:30-12:20 in RCH 207.
Tutorials: none
Office Hours: see above
Quiz #1: Friday February 6th in class.
Midterm Exam: Wednesday February 11th 4:30-6:30 in PHY 313.
Quiz #2: Wednesday April 1st in class.
Final Exam: Thursday April 23rd 9:00-11:30 in RCH 305.

What?

This course is an introduction to two major subjects within the branch of Mathematics called Combinatorics -- these subjects are Enumeration and Graph Theory. The first half of the course will cover enumeration, and the second half will cover graph theory.

Homework: 15%

Quizzes: 10%

Midterm Exam: 25%

Final Exam: 50%


(Note: this was revised from the original 15%:10%:30%:45% format because the midterm exam was scheduled so early in the semester.)

Homework assignments and solutions, midterm exam and quiz solutions, and supplemental notes will be posted here.

Homework assignments will be due (approximately) every second Friday at the beginning of class.

There will be two in-class quizzes designed to prepare you for the midterm and final exams. They will be worth 5% each.

The textbook will be the MATH 239 Course Notes (on sale at Campus Copy MC 2018) together with supplementary material that will be posted on this website.


ENUMERATION

Here are some supplemental notes to start with....

  • Basic Principles of Enumeration and Examples and Applications [PDF file]


    • REFERENCE BOOKS
    (On reserve for 3-hour loans at the DC Library.)
    [Call numbers in square brackets.]
  • K.P. Bogart, Introductory Combinatorics [QA164/B63/1990]
  • C.A. Charalambides, Enumerative Combinatorics [QA164.8/C48/2002]
  • D.I.A. Cohen, Basic Techniques of Combinatorial Theory [QA164/C6/1978]
  • J. Gross and J. Yellen, Graph Theory and its Applications [QA166/Q757/1999]
  • G.E. Martin, Counting: the Art of Enumerative Combinatorics [QA164.8/M37/2001]
  • A. Tucker, Applied Combinatorics [QA164/T83/1995]


  • HOMEWORK ASSIGNMENT #1: due Friday, Jan.16.
    Exercises: [PDF file] || Solutions: [PDF file]


  • HOMEWORK ASSIGNMENT #2: due Friday, Jan.30.
    Exercises: [PDF file] || Solutions: [PDF file]


  • PRACTICE QUESTIONS: INCLUSION/EXCLUSION
    Exercises: [PDF file] || Solutions: [PDF file]


  • HOMEWORK ASSIGNMENT #3: due Friday, Feb.13.
    Exercises: [PDF file] || Solutions: [PDF file]


  • QUIZ #1 SOLUTIONS: [PDF file]
    Histogram of class grades: [PDF file]


  • MIDTERM EXAM SOLUTIONS: [PDF file]
    Histogram of class grades: [PDF file]



    • GRAPH THEORY

  • A fun little flash game based on graph theory
    (you have to move the vertices around so that the edges don't cross).
  • Here's another one (you figure it out).
  • Ah, heck... here's one more.
  • Well... this one is really good.


  • HOMEWORK ASSIGNMENT #4: due Friday, March 6.
    Exercises: [PDF file] || Solutions: [PDF file]


  • There are eleven isomorphism classes of trees with seven vertices.
    (Try to find them all before you peek at the answer.)


  • HOMEWORK ASSIGNMENT #5: due Friday, March 20.
    Exercises: [PDF file] || Solutions: [PDF file]


  • HOMEWORK ASSIGNMENT #6: due Friday, April 3.
    Exercises: [PDF file] || Solutions: [PDF file]


  • QUIZ #2 SOLUTIONS: [PDF file]
    Questions 1 and 2 were done very well, as expected. Question 3 was done very poorly -- I thought it would be challenging, but only a few people deserved more than 3/12. There will be at least one proof question on the final exam!
    Histogram of class grades: [PDF file]
    Also included with the above histogram is a list of the results of both quizzes and the midterm, with names removed, sorted by ID number. Please check this data and inform me of any inaccuracies or omissions.


  • FINAL EXAM PRACTICE QUESTIONS [PDF file]
    Here are some practice questions to help you prepare for the final exam. This collection of problems is tougher than the exam will be -- it is not meant to be a sample exam. I will not be posting solutions.


    • Why?

    Because it is interesting! Besides which, you can use this stuff in probability theory, theoretical computer science, physics, and a bunch of other ways.

    NOTICES ON ACADEMIC INTEGRITY

    The University requires me to include this. You should know it already!