Course information

Instructor: Andrew McDowell
Email: amcdowel AT andrew.cmu.edu
Office hours: Wean Hall 7130 

• Monday 10:30-11:30
• Friday 10:30-11:30
  

Course textbook: Invitation to Discrete Mathematics by J. Matousek and J. Nesetril. Oxford University Press.

Course description

The aim of this course is to provide an introduction to various areas of combinatorics and provide a grounding in both combinatorial techniques and methods that can be used in solving combinatorial problems.
Here is a rough outline of the course material.

• Combinatorial counting
• Sets, subsets and mappings
• Inclusion-exclusion
• Combinatorial identities and proofs
  
• Generating functions
• Extremal combinatorics
• Ramsey theory
• Probabilistic methods
  
• Graph theory
• Random graph theory
• Combinatorial games

An excellent source of notes for the material covered in class, especially for generating functions, can be found at Alan Frieze's website;
Alan Frieze Course Notes

Homework

Homework will be given out on Wednesdays and usually expected at the beginning of the following Wednesday lecture. Regardless, it will be expected by the beginning of the lecture given as the due date.

Collaboration on homework is permitted and in fact encouraged to help understand the problems, but the aim of the homework is to help your understanding of the material, so discuss but do not copy solutions. Write up your work on your own.

Late homework will not be accepted for grading unless prior notice is given of exceptional circumstances such as illness or emergency, in which cases extensions will be considered.

Homework Sheet 1    Homework 1 Solutions
Homework Sheet 2    Homework 2 Solutions
Homework Sheet 3    Homework 3 Solutions
Homework Sheet 4    Homework 4 Solutions
Homework Sheet 5    Homework 5 Solutions

Note that HW5 is for practice and does not need to be handed in.
Homework Sheet 6    Homework 6 Solutions

Homework 6 is optional. I will take an average of your 4 best homework scores.

Midterms

The first midterm will be on Wednesday 18th of February. It will cover the material we've seen in class on counting, generating functions and 'Description, Involution, Exceptions'.

The second midterm will be on Wednesday 4th of March. It will cover topics on estimates and probabilistic methods.

The third midterm will be on the 10th of April. It will cover topics on the Markov, Chebychev and Hoeffding's inequalities.
Mid Term 1 Solutions
Mid Term 2 Solutions
Mid Term 3 Solutions

Course grading

Homework and unannounced quizzes:	20%
3 Midterm exams:	45%
Final exam:	35%