CS2304: Mathematical Foundations of Computer Science (Spring 2026)
- Instructor:
Huan Long, longhuan (at) sjtu.edu.cn
- Class: 14:00-15:40 every Monday (weeks 1-16)
10:00-11:40 every Wednesday (weeks 9-16)
- Place: Dong Shang Yuan 315
- TA: TBA
- Office hour: 13:00 - 15:00 every Thursday,
Location: Dianxin Building 3-327 (电信群楼3-327)
Introduction to CS2304
Mathematical foundations of computer science introduces to the students how to use mathematical models and methods to analyze problems that arise in computer science. It aims to enhance the logical and analytic abilities of the students to model and solve computational problems in a rigorous manner. The course is going to cover several important and useful topics in modern computer science, including ordering theory, combinatorics, graph theory, probabilistic methods, network etc.. At the end of each semester, some cutting-edge topics will be introduced to make the course more adaptable. This is one of the core courses for computer science major, offering them the mathematical sophistications necessary for further study.
Announcement
- Feb. 27. 2026, Welcome to CS2304.
Syllabus
Set and Ordering
- Set, relation, function (pdf)
- The diagonalization method (pdf)
- Ordering (pdf)
- Wide or Tall - Mirsky's theorem and its application
- Dilworth's theorem and its application(*) (pdf)
Combinatorics
- Twelvefold way: Introduction to counting
- Inclusion-exclusion principle and its application
- Generating functions
- Recurrence relations
- Polya Counting(*) (pdf)
- Big O and asymptotic analysis
- Estimates: Examples
Graph theory
- Basic notions and hand shaking lemma
- Graph isomorphism and graph score
- Applications of handshake lemma: Parity argument
- The number of spanning trees
- Isomorphism of trees
The probabilistic method
- Probability: a quick review
- Probabilistic method: basic counting argument and expectation argument, Lovasz Local lemma
Random graph
- The G(n,p) model,global properties, threshold, and phase transition for increasing properties
Introduction to data science
- High-dimensional space
- Best-fit subspaces and singular value decomposition
- Introduction to Markov Chain Monte Carlo
- Massive data algorithm
References
- Invitation to Discrete Mathematics, 2nd Edition, by Jiri Matousek and Jaroslav Nesetril,OXFORD 2008
- Foundations of Data Science, by Avrim Blum, John Hopcroft, and Ravindran Kannan, 2019