General
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 (2021), we will focus on Advanced Algorithmic Graph Theory, with topics centering around graph cuts, graph routing, geometric lens for graph problems, and graph compression. Next year (2022), the topics will be Advanced Probabilistic Combinatorics (very likely about High Dimensional Expanders).
This course will be online. Subject to Aalto rules, small tutorial sessions may be conducted physically if there are sufficient demands. In any case, there will be an option to do online tutorial sessions.
TEACHING STAFF:
Parinya Chalermsook - responsible professor
Wanchote Jiamjitrak - teaching assistant
Ly Orgo - teaching assistant
WARNING: This is a one-period course. About 20 hours per week are expected from your time.
KICK-OFF: April 19, 2021
LECTURES: Weekly overview vdo lectures posted on each Monday.
OTHER CONTACT SESSIONS:
These sessions will NOT be VDO recorded. Students are expected to make an effort to attend them.
- TUTORIALs. Wednesday 12:15 - 14:00 & 16:15 - 18:00. Someone (professor or teaching assistant) will present materials or exercise solutions that would help strengthen conceptual understanding.
At the end of each session, we will take 2-3 volunteers who would (1) summarize and write down the session in detail and (2) share your work with everyone before Friday noon (on Slack channel). Each volunteer will receive up to 5 bonus points (depending on the quality of the writeup); in other words, these are the points for "helping" your classmates who miss the session :) Each student may only volunteer at most once. - SMALL GROUP EXERCISES. Thursday 16:00 - 18:00. We work on selected problems in the exercise sheet. These sessions are run by two TAs. Bonus points (4 points for each) will be rewarded for attendance & participation in the activities.
Roughly, here is how you should think of these points: 2 points for your willingness to share your ideas, 1 point for your extra effort in trying to communicate, and 1 point for starting working on the exercises on time. We will operate by trust (instead of inspecting students in detail): Anyone participating in a session receives 4 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 basic concepts such as cuts, treewidths, cuts, and flows.GRADING
There will be no in-class exam. Your grades will be determined by online quizzes (30 points), discussion sessions (24 points), and take-home problem sets (60+ points). The total number of available points will likely be a lot more than 100. If you get the score of at least 80, it will guarantee Grade 5. The score of at least 40 in total would guarantee to pass the course.
LEARNING GUIDELINES:
Mathematical/proof content can be learned effectively in various ways, and in my opinion, the best two ways are to (i) explain it to others and (ii) write things down in your own language. The activities in this course are designed so that the points incentivize you to write (e.g. written assignments, scribes) and to explain stuffs in your own words (e.g. exercise sessions).
I believe that if you try to maximize the points, you will maximize your learning :)
Here is an example of a good study plan. The abundant total number of points (120 or so) should make it possible to have a one-week chill-out (i.e. doing nothing for one week, you would miss around 20 points).Plan your life in a way that works best for you :)
- Monday: Watching the overview. Read the lecture notes.
- Tuesday: Read the lecture notes. Submit the online quizzes.
- Wednesday: Attend tutorials.
- Thursday: Attend the group exercise session.
- Friday: Work on the exercise sheet.
- Saturday & Sunday: Optional, in case you cannot stop enjoying the exercises :) Submit the solutions before midnight on Sunday.
TOPICS (tentative)
- Week 1: Graph Theory Bootcamp. We go over basic graph theory and work on a lot of exercises.
- Week 2: Probability Bootcamp. We go over basic finite probability space and (again) work on a lot of exercises.
- Week 3: Graph Compression - Edge and Vertex Sparsifiers. Gomory-Hu trees. Spanners.
- Week 4: Connectivity & Expansion - We use the notion of connectivity and finish the proof of Benzcur-Karger result. Definitions and (nice) properties of expanders as sparse graphs that preserve both cuts and distances. We define the property called linkedness which is closely related to expansion.
- Week 5: Flows and Routing - Variants of flows and cuts. Flow-preserving sparsification and applications.
- Week 6: Low-stretch trees - Existence of low-stretch trees. Connection to metric embedding. Duality arguments. Equivalence between oblivious routing and low-stretch trees.