CS 499: Mathematical Foundations of Computer Science, Spring 2017

Jiaotong University

Time: Week 1-16: Monday, 08:00 - 08:40, Week 1-8: Thursday, 10:00 - 11:40. Location:东上院102

Teacher: Dominik Scheder. Teaching Assistant: 孔令坤 (Kong Lingkun, klk316980786@sjtu.edu.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 好大学在线.
Here is some additional material.
Here are latex source files of the homework assignments (zipped).

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
Wednesday, June 21, 2017	Week 18		Exam. 15:40 - 17:40, 东中院2-101. This is an open book exam. Feel free to bring any printed or written material. However, electronic equipment is not allowed, and you will not need it, either.
Monday, June 5, 2017	Week 16	23	Repetition of the whole course.
Saturday, May 27, 2017	Week 15	22	Repetition: Questions about Homework 10; discussing solutions to earlier homework assignments (e.g. Graph Score Theorem for graphs with non-negative edge weights).
Monday, May 22, 2017	Week 14	21	Repetition: Discussing some exercises from Homework 8 and Homework 7.	Watch videos on 好大学在线 "Eulerian Cycles" "Hamilton Cycles - Ore's and Dirac's theorem" "Application of the Handshaking lemmma - Sperner's lemma and the Smith-Thomason theorems for Hamilton cycles" Start with Homework 10. Monday, May 22: handed out. Wednesday, May 24, 18:00: submit questions by email. Sunday, May 28, 18:00: submit first solution.
Monday, May 15, 2017	Week 13	20	Discussing Homework 9.
Monday, May 8, 2017	Week 12	19	Winner of the Unique Asymmetric Graph Contest. Kirchhoff's Matrix Tree Theorem.	Watch videos on 好大学在线 Part III, Video 9, "Minimum Spanning Trees" Part III, Video 10, "The Number of Spanning Trees" Start with Homework 9. Monday, May 8: handed out. Wednesday, May 10, 18:00: submit questions by email. Sunday, May 14, 18:00: submit first solution.
Monday, April 24, 2017	Week 10	18	Issues of Homework 7 submissions. Isomorphism on graphs. Asymmetric graph. Introducing Homework 8.	Watch videos on 好大学在线 Part III, Video 4, "Graph connectivity" Part III, Video 5, "Cycles and trees" Part III, Video 11, "En efficient algorithm for graph isomorphism on trees" Start with Homework 8 (uploaded on Wednesday 26, evening). Wedneday, April 26: handed out. Sunday, April 30, 18:00: submit questions by email. Sunday, May 7, 18:00: submit first solution.
Monday, April 17, 2017	Week 9	17	Briefly addressing problems of Homework 6 submissions. Introducing graphs, degree, graph score. Possible and impossible graph score sequences. Playing it as a game.	Watch videos on 好大学在线 Part III, Video 1, "Graph theory basics - graphs, cycles, paths" Part III, Video 2, "Graph isomorphism, degree, graph score" Part III, Video 3, "Graph score theorem" Start with Homework 7 and submit questions by Wednesday, April 19, 18:00.
Thursday, April 13, 2017	Week 8	16	Discussion questions about Homework 6.
Monday, April 10, 2017	Week 8	15	Estimating the binomial coefficient. Generalizing to strings over the set {0,1,2}. How many such strings have "weight" k?	Watch videos on 好大学在线 Part II, Video 5, "Application of counting" Part II, Video 6, "Big-O-notation" Start with Homework 6 and submit questions by Wednesday, April 12, 18:00.
Thursday, April 6, 2017	Week 7	14	Lower bounds and improved upper bounds on the nth partition number. Approximate size of the binomial coefficient.
Saturday, April 1, 2017	Week 7	13	A recurrence for the partition numbers. Upper bounds like 2ⁿ or F_n on the partition number.
Thursday, March 30, 2017	Week 6	12	The generating function of the partition numbers. The pentagonal number theorem.
Monday, March 27, 2017	Week 6	11	Notions of infinity. Bijections, the Schröder-Bernstein Theorem.
Thursday, March 23, 2017	Week 5	10	Questions about Homework 5. Dimension of an ordering.
Monday, March 20, 2017	Week 5	9	Discussing the first submission of Homework 4. Discussing Homework 5.	Watch videos on 好大学在线 Part III, Video 4, "Combinatorial Identities" Part III, Video 7, "Estimating the Binomial Coefficient" Start with Homework 5 and submit questions by Wednesday, March 22, 18:00.
Thursday, March 16, 2017	Week 4	8	Notions of infinity. Bijections, injections, surjections between N, Z, Q. Uncountability of R
Monday, March 13, 2017	Week 4	7	Discussing the first submission of Homework 3.	Watch videos on 好大学在线 Part II, Video 1, "Basic counting" Part II, Video 2, "Basic summation" Part II, Video 3, "Recurrence for the binomial coefficient" Start with Homework 4 and submit questions by Wednesday, March 15, 18:00.
Thursday, March 9, 2017	Week 3	6	Questions concerning homework 3: maximum, maximal, minimum, minimal; equivalence relations versus partitions; equivalence relations ordered by set inclusion; arbitrarily large versus infinitely large; Hasse diagram. Here is the text file in which I wrote some questions / comments during the lecture.	Some hints concerning Homework 3.
Monday, March 6, 2017	Week 3	5	Equivalence relations and partitions; Bell numbers, partition numbers.	Watch videos on 好大学在线 Part I, Video 2, "Orderings - basic notions" Part I, Video 3, "Orderings - Mirsky's Theorem" Start with Homework 3 and submit questions by Wednesday, March 8, 18:00. I corrected some typos in Homework 3.
Thursday, March 2, 2017	Week 2	4	Questions concerning homework 2. Composition of relations; reflexive-transitive closure of relations
Monday, February 27, 2017	Week 2	3	Discussion of homework submissions. Feasible set intersection sequences. Basic things about relations.	Start with Homework 2 and submit questions by Wednesday, March 1, 18:00. I corrected some typos in Homework 2.
Thursday, February 23, 2017	Week 1	2	Questions about the homework. Formally proving some of the coin riddles.
Monday, February 20, 2017	Week 1	1	Introduction. Two riddles: tiling the 8x8 chessboard and the coin riddle.	Watch videos on 好大学在线 Part 0, Video 0, "Introductory" Part I Video 1, "Sets, Relations, Functions" Start with Homework 1 and submit questions by Wednesday, February 22, 18:00. I corrected some typos after students have pointed them out. Sorry.

back to teaching page