Topic outline

  • General

    In this course, students will get familiar with combinatorics through selected exciting ideas in theoretical computer science (in particular, algorithms and complexity). The course has always been committed to the same principle: Mathematical reasoning and toolkits for computer science. It is suitable for (i) advanced computer science students seeking to enhance mathematical background, or (ii) math students seeking exposure and challenges in mathematics of computation.

    Here is tentative content this year (each part is 2-week long):

    • Part I: Extremal combinatorics & computation: We cover extremal combinatorics (e.g., Ramsey's theory) through the lens of graph algorithms and data structures.

    • Part II: Probability & computation: We introduce probabilistic combinatorics through the lens of algorithms. We show applications such as streaming algorithms and graph sparsification. You will also see the boundaries between constructive and nonconstructive methods in combinatorics, which highlight the transfer of techniques between combinatorics and computation.

    • Part III: Linear algebra & computation: In the final part, we go through linear algebra concepts via applications in spectral graph algorithms and (time permitting) analysis of Boolean functions. You will see the applications of random walks, spectral clustering, average case analysis, etc. If things go well, the lectures will end with dictatorship testing.

    There will be handouts for computer science materials. For mathematical background, we will discuss/work on exercises from Laci Babai's lecture notes.

    TEACHING STAFF:

    Parinya Chalermsook - responsible professor

    Ly Orgo - TA

    Wanchote Jiamjitrak - TA

    Sorrachai Yingchareonthawornchai - guest lecturer & TA

    WARNING: This is a one-period course. About 20 hours per week are expected from your time. 

    KICK-OFF: September 5, 2022

    LECTURES: Monday & Wednesday 12:15 - 14:00. The lectures will be devoted to highlighting the connection between combinatorics and computation.

    Attending the lectures is supposed to help your process of reading the lecture notes ....

    TUTORIAL & EXERCISE SESSIONS: Tuesday & Thursday 16:15- 19:00. We cover (only) math backgrounds to support the lectures, and give opportunities for students to divide into smaller groups to work on exercises together.

    From 16:15 to 17:15, a TA will give a solo tutorial. (of course, feel free to ask questions) 

    From 17:30 to 19:00, the class will divide into small groups to work on exercises with help from the TA.

    PREREQUISITES : Mathematical maturity and (some) knowledge in algorithms. In particular, for those who are familiar with Aalto curriculum, students should be familiar with the following course content. MS-A0402 Foundations of Discrete Mathematics. Without the proper backgrounds, it is still however possible to understand this course but would require much more time. 

    INTENDED LEARNING OUTCOME: 

    Students familiarize themselves with the concepts of graph theory, probabilistic method in computer science, and linear algebra.

    GRADE POLICIES:

    Students are expected to attend (most of) the contact sessions. Skipping sessions should be used only sparingly (e.g., illness or feeling extremely confident about the materials -- in the latter case, you might still benefit from discussions and/or exchanges of ideas)

    Points will come from:

    • Online quizzes (30 points): There will be 6 weekly quizzes.

    • Problem sets (75 points + Bonus): There will be 3 take-home proof-based problem sets. Each problem set is worth 25 points (plus potential bonuses). To gain points from them, rigorous proofs would ideally be expected from students.

      The soft deadlines for these problem sets are September 18, October 2, and October 23. Submissions by the soft deadlines guarantee that you will get feedbacks within 3-4 days after the deadlines.

      Hard deadlines are 14 days after the soft ones.

      Late submissions (after the soft but by the hard deadlines) receive only 60% of the achieved points and may be graded very slowly.

    Getting 80 points will guarantee the highest grade (Grade 5) and 40 points will guarantee that you pass the course.