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