Skip to main content
MyCourses MyCourses
  • Schools
    School of Arts, Design, and Architecture (ARTS) School of Business (BIZ) School of Chemical Engineering (CHEM) –sGuides for students (CHEM) – Instructions for report writing (CHEM) School of Electrical Engineering (ELEC) School of Engineering (ENG) School of Science (SCI) Language Centre Open University Library Aalto university pedagogical training program UNI (exams) Sandbox
  • Service Links
    MyCourses - MyCourses instructions for Teachers - MyCourses instructions for Students - Teacher book your online session with a specialist - Digital tools for teaching - Personal data protection instructions for teachers - Workspace for thesis supervision Sisu Student guide Courses.aalto.fi Library Services - Resourcesguides - Imagoa / Open science and images IT Services Campus maps - Search spaces and see opening hours Restaurants in Otaniemi ASU Aalto Student Union Aalto Marketplace
  • ALLWELL?
    Study Skills Guidance and support for students Starting Point of Wellbeing About AllWell? study well-being questionnaire
  •   ‎(en)‎
      ‎(en)‎   ‎(fi)‎   ‎(sv)‎
  • Toggle Search menu
  • Hi guest! (Log in)

close

Can not find the course?
try also:

  • Sisu
  • Courses.aalto.fi

CS-E4555 - Combinatorics D, 19.04.2021-27.05.2021

This course space end date is set to 27.05.2021 Search Courses: CS-E4555

  1. Home
  2. Courses
  3. School of Science
  4. department of...
  5. cs-e4555 - co...
 
Syllabus
 

General

  • General

    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. 









    • icon for activity
      ForumAnnouncements Forum
    • icon for activity
      ForumGeneral discussion Forum

Course home

Course home

Next section

Written Assignments►
Skip Upcoming events
Upcoming events
Loading There are no upcoming events
Go to calendar...
  • CS-E4555 - Combinatorics D, 19.04.2021-27.05.2021
  • Sections
  • General
  • Written Assignments
  • Online Quizzes
  • Links for Group Exercise Sessions
  • Home
  • Calendar
  • Learner Metrics

Aalto logo

Tuki / Support
Opiskelijoille / Students
  • MyCourses instructions for students
  • email: mycourses(at)aalto.fi
Opettajille / Teachers
  • MyCourses help
  • MyTeaching Support form
Palvelusta
  • MyCourses rekisteriseloste
  • Tietosuojailmoitus
  • Palvelukuvaus
  • Saavutettavuusseloste
About service
  • MyCourses protection of privacy
  • Privacy notice
  • Service description
  • Accessibility summary
Service
  • MyCourses registerbeskrivining
  • Dataskyddsmeddelande
  • Beskrivining av tjänsten
  • Sammanfattning av tillgängligheten

Hi guest! (Log in)
  • Schools
    • School of Arts, Design, and Architecture (ARTS)
    • School of Business (BIZ)
    • School of Chemical Engineering (CHEM)
    • –sGuides for students (CHEM)
    • – Instructions for report writing (CHEM)
    • School of Electrical Engineering (ELEC)
    • School of Engineering (ENG)
    • School of Science (SCI)
    • Language Centre
    • Open University
    • Library
    • Aalto university pedagogical training program
    • UNI (exams)
    • Sandbox
  • Service Links
    • MyCourses
    • - MyCourses instructions for Teachers
    • - MyCourses instructions for Students
    • - Teacher book your online session with a specialist
    • - Digital tools for teaching
    • - Personal data protection instructions for teachers
    • - Workspace for thesis supervision
    • Sisu
    • Student guide
    • Courses.aalto.fi
    • Library Services
    • - Resourcesguides
    • - Imagoa / Open science and images
    • IT Services
    • Campus maps
    • - Search spaces and see opening hours
    • Restaurants in Otaniemi
    • ASU Aalto Student Union
    • Aalto Marketplace
  • ALLWELL?
    • Study Skills
    • Guidance and support for students
    • Starting Point of Wellbeing
    • About AllWell? study well-being questionnaire
  •   ‎(en)‎
    •   ‎(en)‎
    •   ‎(fi)‎
    •   ‎(sv)‎