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.

    TEACHING STAFF:

    Parinya Chalermsook - responsible professor

    Ly Orgo - TA

    Minoo Zarsav - TA


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

    KICK-OFF: September 4, 2023 (room T5)

    LECTURES: Monday & Wednesday 12:15 - 14:00. The lectures will be devoted to highlighting the connection between combinatorics and computation. The lectures typically focus on giving high-level ideas.

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

    TUTORIAL & EXERCISE SESSIONS: Tuesday & Thursday 16:15- 18:00. We go over the proofs in detail. In some cases, mathematical background tutorials will be provided. 

    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 (80+ points): There will be 3 take-home proof-based problem sets (20 +20+40 points). To gain full points from them, rigorous proofs would be expected from students. This is a theoretical subject. We value ideas more than the "results" :-) So giving a correct results (algorithms or answers) without proofs will likely receive less points than presenting an interesting rigorous ideas.

      The soft deadlines for these problem sets are September 17  24, October 1 8, and October 22. 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 will only be graded slowly.

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