Times | Tuesday Thursday 2:15pm - 3:30pm | ||
---|---|---|---|
Location | Econ 140 | ||
Instructor | Amin Saberi  (email) | Office Hours | T Th 3:30 - 4:30 or by appt. |
Course Assistant | Paul Constantine   (email) |
Required Text
- A Course in Combinatorics by Van Lint and Wilson
Topics
- graphs, trees (Cayley’s Theorem, application to phylogeny)
- system of distinct representatives, sequential and parallel algorithms for matching
- eigenvalues, graph expansion and conductance
- probabilistic method, power of randomization
- basic enumeration (permutations, Stirling and Bell numbers), recurrences, generating functions
- Latin squares, combinatorial designs and their applications in coding and statistics
- basic asymptotics, NP-hardness and other complexity classes
Course Requirements
The course will consist of three homework assignments, a straightforward midterm, and one final project. MS students may choose to take a final exam in place of the final project. The deadline for choosing the subject of your final project is April 20th. If you're having trouble choosing a final project, please contact Amin and he will help you choose a project. You may also look at the wiki projects page for ideas.
Grade Distribution
- Final Project 50%
- Midterm 20%
- Homeworks 30% (three homeworks at 10% each)