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:

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

Help Documents:

Markdown Cheatsheet

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

  1. Introduction to Combinatorics: factorials, permutations and combinations, binomial coefficients, Stirling numbers, double counting;
  2. Induction and Combinatorics Basics: bijections, binomial theorem, generating functions;
  3. Graph theory: bridges of Konigsberg, Eulerian circuits, trees, edge coloring, vertex coloring, planar graphs, Kempe's proof of the 5-color theorem;
  4. Network flows: sphere packing bound, Hamming codes;
  5. 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

Projects

Topic Handout

IMPORTANT DATES

Process

Lectures

Lecture 1

Lecture 2

Lecture 3

Lecture 4

Lecture 5

Lecture 6

Homework

Homework 1

Homework 2, due 11:59PM Sep. 17th, 2019

Homework 3, due 11:59PM Nov. 5th, 2019