6125021 Introduction to Combinatorics
Lecturer: Prof. Zichen Xu
Location: Graduate School Build 113
Time: Wednesday (Wed) 3:45PM-6:10PM
Open office time: Wednesday (Wed) 2:00PM-3:30PM, IEB A608-B
- Applied Combinatorics, online edition, by Mitchel T. Keller and William T. Trotter
- Applied Combinatorics, 6th edition, by Alan Tucker
Combinatorics and discrete mathematics are increasingly important, particularly for their applications in computer science. This course will give a brief overview of this subject.
- 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
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.
- There could be randomly 5 quizs
- Only top 4 grades are counted
- 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
- 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