# Math 3012B - Applied Combinatorics

*Summer 2016*

Instructor: Marcel Celaya

Lecture: 9:20am - 10:30am every Monday, Wednesday, and Friday in Skiles 268

Office hours: 11am - 12pm every Monday and Tuesday in Skiles 146a (or by appointment)

E-mail: mcelaya@gatech.edu

Instructor: Marcel Celaya

Lecture: 9:20am - 10:30am every Monday, Wednesday, and Friday in Skiles 268

Office hours: 11am - 12pm every Monday and Tuesday in Skiles 146a (or by appointment)

E-mail: mcelaya@gatech.edu

**About this course:** This course serves as an introduction to combinatorial mathematics. The goal of this course is to teach students how to write proofs, and to give students understanding of important algorithms that arise in discrete mathematics and computer science.

**Book:**We will use the book Applied Combinatorics by Keller and Trotter. It is worth taking a look at Trotter's webpage for additional course materials, including old exams and solutions to some problems in the book.

**Topics:** This course will mostly follow the book, and we will cover chapters 2-9 and 12-14. Topics will include:

- Counting and combinatorial proofs (Ch. 2)
- Mathematical induction (Ch. 3)
- The pigeonhole principle (Ch. 4)
- Graph theory (Ch. 5)
- Partially ordered sets (Ch. 6)
- Inclusion-exclusion (Ch. 7)
- Generating functions (Ch. 8)
- Recurrences (Ch. 9)
- Minimum weight spanning trees (Ch. 12)
- Dijkstra's algorithm (Ch. 12)
- The max-flow min-cut theorem and the Ford-Fulkerson algorithm (Ch. 13)
- Bipartite matching and chain partitioning (Ch. 14)

**Exams:** There will be two midterm exams in this course. The dates for these are **June 8, 2016** and **July 11, 2016**.

The final exam will be on Monday, August 1 from 8am to 10:50am.

**Homework:** Homework will be assigned weekly, and the lowest homework grade will be dropped. You are encouraged to work in groups, but your submissions must be written in your own words.

- Homework 1 - Due May 29.
- Homework 2 - Due June 3.
- Homework 3 - Due June 10.
- Homework 4 - Due June 17.
- Homework 5 - Due June 24.
- Homework 6 - Due July 1.
- Homework 7 (optional). Solutions to book problems
- Homework 8 - Due July 15.
- Homework 9 (optional).

**Homework submission:** In addition to submitting homework in class, you may also submit PDFs or scanned homework on T-Square. However, **pictures of your handwritten homework taken by a camera phone will not be accepted.** If for some reason you absolutely must do this, please either hand in directly to me or email me a scanned copy of your **unaltered** homework by the end of the first lecture after the due date. No late homework will be accepted without prior arrangement.

**Piazza:** We will be using Piazza for this class. Please feel free to ask a question on Piazza if you are stuck on a problem! If you know the answer to a question, consider also helping out your fellow classmates by posting your thoughts on it.

**Grading scale:**

- A: 90-100%
- B: 80-89%
- C: 70-79%
- D: 60-69%
- F: 59% or below

**Grading distribution:**

- 20% Homework
- 50% Two midterms, each worth 25%
- 30% Final exam

**Academic integrity: **Students are reminded of the obligations and expectations associated with the Georgia Tech Honor Code.

**Learning Disabilities: ** It is the right of any student with a certified learning disability to request necessary accommodation. Such requests must be made well in advance of the time that the accommodation is required, ideally in the first or second week of class, and a letter of documentation from the ADAPTS office must be presented at the time of any request.

**Attendance:** Attendance is required for all lectures. The student who misses a class meeting is responsible for any announcements made about homework or exams. Make-up exams are given only in extraordinary circumstances at the discretion of the instructor. In the event of an absence due to travel representing Georgia Tech, such as an intercollegiate sports competition, you must notify the professor at least **two weeks** in advance to arrange for an alternative test date.

*Updated July 3, 2016*