Topic outline

  • The course will be conducted physically on campus. The lectures and other events will not be VDO-recorded and could not be participated online.

    This course introduces students to combinatorics through the lens of computer science. Although the topics vary every year, 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. 

    In this iteration of the course (2022), we will focus on Spectral & Algebraic Graph Theory. Last year (2021), we focused on graph cuts and sparsification. The year before (2020), we did extremal & probabilistic combinatorics.

    TEACHING STAFF

    Parinya Chalermsook - responsible professor

    Ly Orgo - teaching assistant 

    Sorrachai Yingchareonthawornchai - teaching assistant

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

    KICK-OFF: April 20, 2021

    LECTURES: Monday & Wednesday 12:15 - 14:00. There will be 9 lectures which focus on concepts.

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

    Various opportunities for earning bonus points will be there for those who attend the sessions, e.g., participating in group discussions and submitting your work give 2 points.   

    PREREQUISITES : Mathematical maturity and 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 are able to work proficiently with graphs and their spectral and algebraic properties.

    GRADE POLICIES:

    Students are expected to attend the lectures.

    Points will come from:

    • Online quizzes (20 points): These quizzes test your understanding of definitions.

    • Scribes (15 points): Students are expected to scribe some class materials covered in the lectures and recitations (in detail, containing all proofs) in LaTex and go through editorial phase with teaching assistants (i.e. TAs may ask you to edit your notes until they are of desirable quality).  

    • Learning log (10 points): Students are expected to maintain & submit their weekly learning log, listing the concepts learned in that week, discussions with your peers, problem solving attempts, etc. The learning log should contain the estimates of the number of hours you spent in that week on this course.

    • Mid-term problem set (25 points): A (take-home) problem set containing ~5 proof-based exercises will be handed out at the end of 3rd week and you will have a week to solve it.

      We will offer mid-term collaborative sessions to help you solve and meet collaborators. Some bonus points will be handed out for participations.

    • Final project(30 points): Each student is expected to pick one topic, not covered in the lectures and learn it. Final report is expected before mid June (actual date TBD).