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 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 Wednesday, June 20, 2018 Week 17 Exam. 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 23 Discussing the exam of 2017. Monday, June 4, 2018 Week 15 22 Preparing for the exam: reviewing course material and solving exam-like problems in class. Monday, May 28, 2018 Week 14 21 Discussing the solution of Homework 11. Monday, May 21, 2018 Week 13 20 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 19 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 18 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 17 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 16 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: Video: Hamilon Cycles Video: An application of the Handshaking Lemma: Sperner's Lemma and the Smith-Thomason Theorem Video: An algorithm for isomorphism of trees Start with Homework 9. Here are the corresponding tex sources. Thursday, April 19, 2018 Week 8 15 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 14 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: Video: Minimum Spanning Trees Video: The number of trees on n vertices Start with Homework 8. Here are the corresponding tex sources. Thursday, April 12, 2018 Week 7 13 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 12 Discussing Homework 4, in particular Exercise 4.14, giving a combinatorial proof that (pd choose k) is divisible by p for 1 ≤ k ≤ pd. Starting the "smallest unique bet wins" game on graphs, asymmetric graphs, and asymmetric trees. Watch videos: Video: The Graph Score Theorem Video: Eulerian Cycles 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 11 Applicationg of our estimates for the binomial coefficient: upper and lower bounds for error-correcting codes. Watch videos Video: Graph theory basics Video: Graph isomorphisms and graph score Video: Graph connectivity Video: Cycles and Trees Start with Homework 6. Here are the tex files of Homework 6. Thursday, March 29, 2018 Week 5 10 Estimating the size of the binomial coefficient. Watch videos Monday, March 26, 2018 Week 5 9 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 8 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 7 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 6 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 5 Showing sample solutions for some problems in Homework 1. Discussing questions and first submission of Homework 2. Watch videos Video: Basic Counting Video: Simple Sums Video: A recurrence for the binomial coefficient Video: Combinatorial identities 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 4 Explaining and giving hints for some problems in Homework 2. Monday, March 5, 2018 Week 2 3 Discussion of Homework 1 questions and submissions. Some more things on infinite sets. Watch the following videos: Video: Partial Orderings Video: Width and Height: Mirsky's Theorem Start with Homework 2. Here are the tex files of Homework 2. Thursday, March 1, 2018 Week 1 2 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 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: Video: Introduction Video: Sets, Relations, Functions Please adhere to the class guidelines Start with Homework 1. Here are the tex files of Homework 1.

back to teaching page