CS 499: Mathematical Foundations of Computer Science, Spring 2019

Jiaotong University

Time: Week 1-8: Monday, 08:00 - 09:40, Week 1-16: Thursday, 10:00 - 11:40. Location:东中院4-303

Teacher: Dominik Scheder.
Teaching Assistant: 汤舒扬, Tang Shuyang (htftsy at gmail dot com), 王培新, Wang Peixin (wangpeixin at sjtu dot edu dot cn)

Textbook: An Invitation to Discrete Mathematics by Jiři Matoušek and Jaroslav Nešetřil

Material: Video lectures and corresponding slides can be found at Coursera or 好大学在线.

Grading: 50% final exam, 50% homework. The students will form groups of size 4-5. Homework will be handed in by every group.

Date	Week	#	Class	Self-Study
Monday, May 23, 2019	Week 13	20	Discussing questions about Homework 10. Existence of a maximum flow. Introducing Dinic' Algorithm.	Start with Homework 11. Here are the corresponding tex sources. Watch the remaining three videos. Matchings: basic definitions Bipartite matchings: Hall's and Kőnig's Theorem Using Kőnig's Theorem to prove Dilworth's Theorem on partial orderings
Thursday, May 16, 2019	Week 12	19	Discussing the solution to Homework 10, especially (1) an uncountable chain in the powerset of the natural numbers, (2) an uncountable set of subsets of natural numbers such that all pairwise intersections are finite. Several proofs (two to three) for each of these problems.	Watch videos: Networks, flows, cuts The Max-Flow Min-Cut Theorem Start with Homework 10. Here are the corresponding tex sources.
Thursday, May 9, 2019	Week 11	18	Discussing solutions to Homework 8. Giving hints about Homework 9.
Sunday, May 8 2019 (make up for Thursday, May 2)	Week 10	17	Set theory: infinite sets; natural numbers, integers, and rational numbers all have the same cardinality; real line, real plane, unit circle, and the set of infinite bit strings all have the same cardinality.	Start with Homework 9. Here are the corresponding tex sources.
Thursday, April 25, 2019	Week 9	16	Discussing solutions to Homework 6 (graph automorphisms). Discussing questions about Homework 7 (minimum spanning trees).	Start with Homework 8. Here are the corresponding tex sources. Read my brief lecture notes on infinite sets, which you will need for Homework 9.
Thursday, April 18, 2019	Week 8	15	Kirchhoff's Matrix Tree Theorem: computing the number of spanning trees by computing the determinant of a certain matrix.	Start with Homework 7. Here are the tex files of Homework 7.
Monday, April 15, 2019	Week 8	14	Finding the winner of the "smallest unique asymmetric tree game". Discussing Homework 6: proving that aut(G) divides n!. Briefly discussing Robot Wars again.	Watch videos: Partial Orderings: basic notions Partial Orderings: width and height of an ordering.
Thursday, April 11, 2019	Week 7	13	Discussing the solution to Homework 4, in particular the Robot Wars. Class given by Zhang Chihao.
Monday, April 8, 2019	Week 7	12	Again playing the "Smallest unique asymmetric tree" game, this time hopefully determining a winner. The number of trees on n vertices: alternative proof. Maybe Kirchhoff's Matrix Tree Theorem.	Watch videos: Applications of the Handshaking Lemma: Sperner's Lemma and the Smith-Thomason Theorem Minimum Spanning Trees Start with Homework 6. Here are the tex files of Homework 6.
Thursday, April 4, 2019			Playing the "smallest unique tree" game and explaining several concepts along the way: The difference between trees, rooted trees, ordered rooted trees. Exploring all automorphisms of a graph and see that one can combine them (they form a group). The difference between counting graphs on n vertices or unlabeled graphs, i.e., graphs up to isomorphism. It turned out there is no winner of the game so far. We will repeat it on Monday. Please bring a small sheet of paper with an asymmetric tree on it.	Watch videos The number of trees on n vertices. Determining whether two trees are isomorphic.
Monday, April 1, 2019	Week 6	11	Discussing Homework 3, giving some hints about Homework 4. Playing the "smallest unique" game on graphs.	Watch videos Eulerian Cycles Hamilton Cycles and Ore's Theorem
Thursday, March 28, 2019	Week 5	10	The Pentagonal Number Theorem and a Recurrence for the Partition Numbers. Introducing Homework 5: generalizations of the graph score theorem.	Start with Homework 5. Here are the tex files of Homework 5. I updated the lecture notes on discrete probability. Graph connectivity. Cycles and trees.
Monday, March 25, 2019	Week 5	9	A bit about Homework 4: How to make those combinatorial identity proofs more formal. Partition Numbers: some generating function magic.	Watch videos: Basic graph theory. Graph isomorphism. The graph score theorem.
Thursday, March 21, 2019	Week 4	8	Discussing Homework 3. Probabilistic method: the crossing number inequality for graph diagrams.	Start with Homework 4. Here are the tex files of Homework 4. I answered some of your questions concerning homework 3 in this text file. Thanks for all the good questions! Watch videos: Talking about asymptotics: the big-O-notation Estimating the size of the binomial coeffiicent
Monday, March 18, 2019	Week 4	7	Discussing solutions to Homework 1, in particular how to prove the Inclusion Exclusion Formula without induction and how to recognize feasible sequences. Discrete probability: biased random walks on Z.	I updated the lecture notes on discrete probability.
Thursday, March 14, 2019	Week 3	6	Disrete probability: unbiased random walk on a finite path; unbiased random walk on Z.
Monday, March 11, 2019	Week 3	5	Discussing some questions about Homework 2. Methods for computing sums (like the first n squares; binomial coefficient times k²).	Start with Homework 3. Here are the tex files of Homework 3. I answered some of your questions concerning homework 2 in this text file. Thanks for all the good questions! Deadline for the final submission of Homework 1 is coming Sunday, 2019-03-17.
Thursday, March 7, 2019	Week 2	4	A closed formula for the Catalan numbers and two proofs: one using the "mirroring" technique, the other one placing 2n+1 symbols on a cycle. Brief intro to Homework 2.	Watch videos: Video: Application of the binomial coefficient - computing the expectation of the minimum of k random numbers. Start reading my very basic lecture notes on discrete probability. Start with Homework 2. Here are the tex files of Homework 2.
Monday, March 4, 2019	Week 2	3	Discussion of Homework 1 questions, mostly Exercise 3.3 (feasible sequences of set intersections). Starting with the Catalan numbers: counting ``mountain ranges'', ordered trees, and complete binary trees.	No video assignment this time.
Thursday, February 28, 2019	Week 1	2	Introduction to enumerative counting: the Fibonacci numbers.	Watch videos: Video: A recurrence for the binomial coefficient Video: Combinatorial identities
Monday, February 25, 2019	Week 1	1	Introduction. Two riddles: tiling the 8x8 chessboard and the coin riddle. Explaining the work flow of this class (homework, feedback, grading).	Watch videos on 好大学在线 or Coursera or (in smaller resolution) by clicking on the links below: Video: Introduction Video: Sets, Relations, Functions Video: Counting Basic Objects Video: Evaluating Simple Sums Please adhere to the class guidelines. Start with Homework 1. Here are the tex files of Homework 1.

back to teaching page