e CS 499: Mathematical Foundations of Computer Science, Spring 2018 back to teaching page

CS 499: Mathematical Foundations of Computer Science, Spring 2018

Jiaotong University

Time: Week 1-16: Monday, 08:00 - 09:40, Week 1-8: Thursday, 10:00 - 11:40. Location:下院413
Teacher: Dominik Scheder. Teaching Assistant: 林茵 (ireane at "School domain"), 毛威超 (maoweichao at "School domain"), where "School domain" is "sjtu.edu.cn"
Textbook: An Invitation to Discrete Mathematics by Jiři Matoušek and Jaroslav Nešetř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.







Wednesday, June 20, 2018

Week 17

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 11, 2018

Week 16


Discussing the exam of 2017.

Monday, June 4, 2018

Week 15


Preparing for the exam: reviewing course material and solving exam-like problems in class.

Monday, May 28, 2018

Week 14


Discussing the solution of Homework 11.

Monday, May 21, 2018

Week 13


Discussing the solution to Homework 10. Addressing questions and problems concerning Homework 11.

Here is last year's final exam. Work on it, you'll get an idea what type of prolems will be in the exam.

Monday, May 14, 2018

Week 12


Discussing Homework 9: Minimum number of edges you have to remove from Kn in order to destroy all Hamilton cycles. Theorem that every tournament has a directed Hamilton path.

Discussing Homework Exercise 10.2: show that flow is transitive.

Flow integrality theorem, bipartite matchings, examples.

Watch the remaining three videos.

Start with Homework 11. Here are the corresponding tex sources.

Monday, May 7, 2018

Week 11


Discussing solutions to Homework 8.

Watch videos:

Start with Homework 10. Here are the corresponding tex sources.

Please take this one-question survey and vote which material we should cover in the rest of this course.

Saturday, April 28, 2018

Week 10


Kirchhoff's Matrix Tree Theorem: how to compute the number of spanning trees of a given graph by computing the determinant of a matrix.

Monday, April 23, 2018

Week 9


Discussing solutions to Homework 7 (graph score theorems). Presenting an inductive proof of the Multigraph Score Theorem that incrementally builds a multigraph, by first drawing an edge between the two highest-degree vertices and then recursing.

After the break presenting a completely different proof, due to group "Long Live". Allow the multigraph to have self-loops. A self-loop incident to vertex x counts as two edges. Initialize the multigraph with self-loops to satisfy the degree constraints. Then iteratively get rid of self-loops until none survives.

Adapting the above proof to weighted graphs, discussing proof of termination (all self loops get deleted eventually).

Watch videos:

Start with Homework 9. Here are the corresponding tex sources.

Thursday, April 19, 2018

Week 8


Preparing for Homework 8: Counting trees on n vertices. Presenting two different proofs, one using vertebrates and one using Prüfer codes. Selecting random students to come to the blackboard and do several examples.

Monday, April 16, 2018

Week 8


Discussing the first submission of Homework 7: graph score theorems for alternative graphs (multigraphs, weighted graphs, weighted graphs with negative weights allowed).

Presenting solutions to Homework 6.

Watch videos:

Start with Homework 8. Here are the corresponding tex sources.

Thursday, April 12, 2018

Week 7


Determining the winner of the "smallest unique bet wins" game on graphs, asymmetric graphs, and asymmetric trees. Handing out prizes. Discussing several small problems on asymmetric trees.

Upper and lower bounds on the number of isomorphism classes of graphs on n vertices.

Monday, April 9, 2018

Week 7


Discussing Homework 4, in particular Exercise 4.14, giving a combinatorial proof that (pd choose k) is divisible by p for 1 ≤ kpd.

Starting the "smallest unique bet wins" game on graphs, asymmetric graphs, and asymmetric trees.

Watch videos: Start with Homework 7. Here are the tex files of Homework 7.

Thursday, April 5, 2018

No class because of Qingming Festival.

Monday, April 2, 2018

Week 6


Applicationg of our estimates for the binomial coefficient: upper and lower bounds for error-correcting codes.

Watch videos Start with Homework 6. Here are the tex files of Homework 6.

Thursday, March 29, 2018

Week 5


Estimating the size of the binomial coefficient.

Watch videos

Monday, March 26, 2018

Week 5


A bit about Homework 4: How to make those combinatorial identity proofs more formal.
Possibly the Pentagonal Number Theorem and a fascinating recurrence for the partition numbers.

No new homework assignment this week.

Thursday, March 22, 2018

Week 4


Discussing the Exercise 2.15 (uncountable chain). Obtaining upper and lower bounds on the Bell numbers Bn and the Partition numbers Pn.

Please take the little survey I have created on Survey Monkey.

Monday, March 19, 2018

Week 4


Discussing solutions to Homework 2. In particular

  • Exercise 2.3: infinite subsets of Nk contain an infinite chain
  • Exercise 2.8: midlevel is the largest antichain of {0,1}n
  • Exercise 2.15: {0,1}N contains an uncountable chain. Here are some slides giving a longer, more explicit solution of Exercise 2.15.

Watch video Application to a problem in discrete probability theory.

Start with Homework 4 and submit questions by Sunday, March 25, 12:00. Here are the tex files of Homework 4.

Thursday, March 15, 2018

Week 3


A bit more on orderings: Hasse diagrams; some (infinite) examples where we cannot reconstruct the ordering from the Hasse diagram.

Monday, March 12, 2018

Week 3


Showing sample solutions for some problems in Homework 1. Discussing questions and first submission of Homework 2.

Watch videos

Four videos might seem like a lot; however, I think you already know most of the material of the first two videos, so it will not be much new material.

Start with Homework 3 and submit questions by Sunday, March 17, 12:00. Here are the tex files of Homework 3.

Thursday, March 8, 2018

Week 2


Explaining and giving hints for some problems in Homework 2.

Monday, March 5, 2018

Week 2


Discussion of Homework 1 questions and submissions. Some more things on infinite sets.

Watch the following videos:

Start with Homework 2. Here are the tex files of Homework 2.

Thursday, March 1, 2018

Week 1


Given hints for Homework 1, Exercise 3.3 (feasible intersection sequences). Some basics of infinite sets, countable, uncountable setes.

I wrote some lecture notes on set theory. Please read them, we will need this for Homework 2.

Monday, February 26, 2018

Week 1


Introduction. Two riddles: tiling the 8x8 chessboard and the coin riddle.

Watch videos on 好大学在线 or Coursera or (in smaller resolution) by clicking on the links below:

Please adhere to the class guidelines

Start with Homework 1. Here are the tex files of Homework 1.

back to teaching page