V63.0240: Combinatorics
| Term: | Spring 2011 |
| Meeting times: | MW 3:30pm-4:45pm in WWH 201 |
| Instructor: | Prof. F. Bogomolov |
| Office: | 1012 WWH |
| Office hours: | Tue 1pm-3pm and by appointment |
| Phone: | 212-998-3243 |
| Email: | bogomolo@cims.nyu.edu |
Prerequisites
Students who wish to enroll in Combinatorics must meet the following prerequisites:
- V63.0122 Calculus II with a grade of C or better and/or the equivalent
Goals and Topics
- Techniques for counting and enumeration including generating functions, recursions, partitions
- The principle of inclusion and exclusion
- Polya counting
- Elements of graph theory: planar graphs, colouring problems, trees, searching algorithms, network flows
- Network flows
Course Details
Textbook and Materials
Applied Combinatorics, Alan Tucker, John Wiley 2007
Combinatorics, R. Brualdi, 5th Edition
Homework
Assigned weekly (during the Wednesday class) and collected at the beginning of next Monday class (5-6 problems / week)Exams
There will be a midterm exam and a final exam on Wed., May 11, 2011, from 4:00pm-5:50pm
Grading policy
The results of homework, quizzes, midterm, and final will be combined
| Week | Topic |
|---|---|
| 1 | Graph theory |
| 2 | Graph coloring |
| 3 | Trees and searching |
| 4 | Network algorithms |
| 5 | Enumeration |
| 6 | Counting methods for arrangments |
| 7 | Generating functions |
| 8 | Recursions |
| 9 | Inclusion / Exclusion |
| 10 | Additional topics |
| 11 | Polya's enumeration |
| 12 | Games with graphs |
| 13 | Review of the course |