General

  • General

    In this course, students will get familiar with combinatorics through selected exciting ideas in theoretical computer science (in particular, algorithms and complexity). This is a class that spans over 6 weeks only, so it is relatively intensive. Please try to minimize your other workload when taking this class. 

    The course is worth 5 credits. 

    Basic information: 

    Teaching staff: 
      • Parinya Chalermsook (responsible professor) 
      • Wanchote Jiamjitrak (teaching assistant) 


    First meeting: April 15, 2020 (only 30 minutes intro & 1 hour technical material) 

    Lectures: Monday & Wednesday, 12:15 - 13:45. Room T4. Meeting on Zoom

    Exercise sessions: Thursday, 16:15 - 18:15. Room T4.  Meeting on Zoom.

    Final Project Days: TBA

    Prerequisite: Mathematical maturity. In particular, the ability to read and write basic mathematical proofs and familiarity with algorithms and asymptotic analysis. Ability to use (or learn how to use) LaTex :) 

    Intended Learning outcomes: Students are comfortable with probabilistic combinatorics and are able to read/write technical work on this topic. 

    Grading: 

    There will be no in-class exam. There will be 8-9 mandatory lectures. Your grade will be a combination of: 

    • Contribution to the commons [20 points]: We will maintain a local wiki page that summarizes the lectures and relevant materials. You get 20 points by making contribution to this cause. Each student is expected to  write one scribe note (10 points) and make minor edits (requested by the instructor) or wrote the solutions of DO exercises  (1 point per each edit which involves small improvements to the text). 
    • Project & Presentation [40 points]: Each student should pick a project topic to study and give a 45-minute presentation about it. The presentation days are SOME TIME IN JUNE!! In exceptional cases, I might arrange project presentation outside these dates. 
    • Exercises [40 points]: There are 4 exercise sessions, and each is worth 10 points. You get 10 points if you participate in the session activities and submit your work at the end of the session. (DUE TO COVID SITUATION, THE FORMAT IS CHANGED) There will be 4 homework sets. Each set contains 4 questions: 2 questions will be discussed explicitly during the exercise session. 1 question will be hinted a bit. The remaining one cannot be asked or discussed with anyone. It's supposed to be an independent work. Here is the list of sessions: 
      • April 23 
      • April 30
      • May 7 -- for project selection --  
      • May 14 
      • May 21 
    • Possible bonus points ... 

    Roughly, 75 points guarantee grade 5, and each decrement of 10 points reduces your grade by 1. 

    List of topics: 

    In this iteration of the course, we cover 5 topics. 

    • Forbidden Structures, Geometry, and Data structures: Davenport-Schinzel Sequences, Zarankiewitz problems 
    • Algorithms through Ramsey-type results: Independent set and graph coloring 
    • Concentration Inequalities: Chernoff bound and Martingale, applications in algorithms design. 
    • Lovasz Local Lemma: Algorithmic Proofs and applications in routing. 
    • Set systems, VC-dimension, epsilon-nets, and discrepancies: Applications in computational geometry. 


    Useful links: 



Course home

Course home

Next section

Project Information►