e
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. |
Date |
Week |
# |
Class |
Self-Study |
Wednesday, June 20, 2018 |
Week 17 |
|
Exam. |
|
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. |
Watch the remaining three videos.
|
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. |
Watch videos:
|
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). |
Watch videos:
|
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. |
|
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. |
Watch videos:
|
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
|
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. |
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
|
Watch video
Application to a problem in discrete probability theory.
|
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
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:
|
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:
|