# 6125021 Introduction to Combinatorics

Lecturer: Prof. Zichen Xu

Email: zichenxu@outlook.com

Location: Graduate School Build 113

Time: Wednesday (Wed) 3:45PM-6:10PM

Open office time: Wednesday (Wed) 2:00PM-3:30PM, IEB A608-B

Textbook:

- Applied Combinatorics, online edition, by Mitchel T. Keller and William T. Trotter
- Applied Combinatorics, 6th edition, by Alan Tucker

Help Documents:

## Description

Combinatorics and discrete mathematics are increasingly important, particularly for their applications in computer science. This course will give a brief overview of this subject.

## Topic List

- Introduction to Combinatorics: factorials, permutations and combinations, binomial coefficients, Stirling numbers, double counting;
- Induction and Combinatorics Basics: bijections, binomial theorem, generating functions;
- Graph theory: bridges of Konigsberg, Eulerian circuits, trees, edge coloring, vertex coloring, planar graphs, Kempe's proof of the 5-color theorem;
- Network flows: sphere packing bound, Hamming codes;
- Graphic algorithms: Djkstra's algorithm for minimum spanning tree, depth first and breadth first algorithms for trees, greedy algorithm for graph coloring

## Homework

Roughly a few questions will be asked randomly at the end of one lecture in two weeks. Each homework takes one or two weeks to finish.

## Test

- There could be randomly 5 quizs
- Only top 4 grades are counted

## Projects

IMPORTANT DATES

- Grouping Set: Oct. 10th, 2019
- Presentation: Nov. 23rd, 2019
- final report due: Dec. 4th, 2019

- Male + female group gets 10% more grades than both female or both male

### Process

- One opening report: title, authors, abstract and related work list, due Oct. 17th.
- One final presentation: 7 mins + 2 mins Q&A
- One final report: everything as a full technical report