Math 3012 Applied Combinatorics

Fall 2017 T-Th 8:00 - 9:15 am

Skiles 249

**Text:**The text for this course is Applied Combinatorics by Keller and Trotter. It is available without cost in a web based version, and students are encouraged to bookmark this site. This text has been under development for the past ten years and extensive revisions have been incorporated in the past year. This web-based version is a major upgrade, and we expect that this format will be especially useful for students. Students who need or want hard copy can purchase one through Amazon or Barnes and Noble, but we emphasize that such a purchase is entirely optional. The web-version is ``world readable'' and completely free.This text is a joint project between Professor Trotter and Mitchel T. Keller, who completed his Ph. D. in spring 2010 at Georgia Tech, with Professor Trotter serving as his thesis advisor. Mitch won a presigious Marshall Sherfield postdoctoral fellowship in the Department of Mathematics of the London School of Economics. He is now on the faculty of Washington and Lee University.

This text has specifically written with Georgia Tech students and Math 3012 as targets. Although it is a mathematics text, it has computer science and engineering concepts, principles and applications close to the surface.

**Outline of Topics:****Discrete Structures:**Graphs, digraphs, networks, designs, posets, strings, patterns, distributions, coverings, partitions.**Enumeration:**Permutations, combinations, inclusion/exclusion; generating functions; recurrence relations, Polya counting.**Algorithms and Optimization:**Sorting, spanning trees, shortest paths, eulerian circuits, hamitonian cycles, graph coloring, planarity testing, network flows, bipartite matchings, chain partitions.

**Grading Scale:**Grades will be assigned on the traditional scale:

A |
90 or higher |

B |
80 - 89 |

C |
70 - 79 |

D |
60 - 69 |

F |
Below 60 |

**Grading Policy:**Grades will be determined by the following distribution:

60% |
Three in semester tests |

10% |
Homework, quizzes and projects |

30% |
Final Exam |

**Tests:**There will be three tests during the term, each counting 20% of the final grade, i.e., altogether, these three tests will count for 60% of the final grade.**Test Dates:**- Test 1. Tuesday, September 19, 2017 (tentative)
- Test 2. Thursday, October 19, 2017 (tentative)
- Test 3. Thursday, November 16, 2017 (tentative)
- Final Exam. Tuesday, December 12, 2017. 2:50 - 5:40pm (FIRM!)
- Note that relative to other semesters, the first three test dates are scheduled somewhat earlier than in other years, so some adjustments of topics on tests in the archive will be necessary. This scheduling feature results primarily from the decision not to have Test 3 in the last class day before the Thanksgiving holiday.

**Homework, quizzes and projects:**There will be a limited number of turn-in homework assignments, and they will be assigned via email. Remember that there is a full archive of all course related email. Occassional pop quizzes may be given, usually at the beginning or the end of a class. There will be an optional project assigned near the middle of the semester. Students who elect to carry out this project must submit their work on or before the last class day, which is Tuesday, December 5, 2017.**Final Exam:**The final exam will be cumulative and will count for 30% of the final grade. An exceptionally strong final exam score may off set to a small degree a weaker score on one of the three hour tests.**Computing element:**This course is a math course. But combinatorics is closely related to computer science, and students are strongly encouraged to use and understand computer programs developed for this course. On the other hand, no prior programming knowledge is assumed.**Attendance:**Students are expected to attend all lectures without exception. Absences will be excused**only**for (1) official representation of the Institute, and (2) documented medical emergencies. Normally, a statement from the attending physician is required. Notice of being seen at the Student Health Center is**not**accepted as documentation. When absence from an in-term exam has been excused, the relevant portion of the final exam will be used as a "make-up" test. In particular, individualized make-up tests will not be given during the term.**Student Support:**Professor Trotter holds regularly scheduled office hours, and students are strongly encouraged to drop by for help. Come sooner rather than later. Experience shows that some Georgia Tech students are reluctant to ask for help as it something they never had to do in high school. Don't fall into this trap. The School of Mathematics wants every student to succeed and we will help you if you make the effort.**Academic Integrity:**Students are reminded of the obligations and expectations associated with the Georgia Tech.*Academic Honor Code*