# Math 3012A - Applied Combinatorics

*Summer 2017*

Instructor: Marcel Celaya

Lecture: 9:30am - 10:45am every Monday, Wednesday, and Friday in College of Computing 17

Office hours: 1pm - 2pm every Monday and Tuesday in Skiles 142 (or by appointment)

E-mail: mcelaya@gatech.edu

Instructor: Marcel Celaya

Lecture: 9:30am - 10:45am every Monday, Wednesday, and Friday in College of Computing 17

Office hours: 1pm - 2pm every Monday and Tuesday in Skiles 142 (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 help students reason about discrete structures and algorithms that arise in mathematics and computer science.

**Book:**We will use the book Applied Combinatorics (pdf version) by Keller and Trotter. It is worth taking a look at Trotter's webpage for additional course materials, including videos, 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 tentative dates for these are **June 9, 2017** and **July 7, 2017**.

The final exam will be on Monday, July 31 from 8am to 10:50am at our usual classroom (CoC17).

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

- Homework 1 - Due May 24.
- Homework 2 - Due May 31.
- Homework 3 - Due June 7.
- Homework 4 - Due June 14.
- Homework 5 - Due June 23.
- Homework 6 - Due June 28.
- Homework 7 - Due July 5.
- Homework 8 - Due July 12.
- Homework 9 - Due July 21.
- Homework 10 (optional) - Due August 3.

**Homework submission:** ~~In addition to submitting homework in class, you may also submit PDFs or scanned homework on T-Square. If your online submission is illegible (e.g. blurry pictures from a camera phone), you may be asked to provide the handwritten version of your homework in order to receive credit.~~ All homework will be due in class. I will still accept homeworks after class, on the due date only, but you'll have to stop by my office to drop it off. Please let me know in advance if you plan to do this so I can be there. If you can't physically be on campus to turn homework in, please send me an email. No homework will be accepted after the due date 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 May 26, 2017*