6125021 Introduction to Combinatorics
Lecturer: Prof. Zichen Xu
Email: zichenxu@outlook.com
Location: Graduate School Build 218
Time: Sat 1:45PM--Whenever I would like to end (Possibly)
Open office time: Online
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.
Projects
IMPORTANT DATES
- Team Building: Due Oct. 8th. I would like to receive an email on all group information
- Male + female group gets 10% more grades than both female or both male
Process
- One opening report: title, authors, abstract and related work list, TIMEļ¼ Oct 24th 11:59PM.
- One final presentation: 5 mins + 2 mins Q&A
- One final report: everything as a full technical report