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). In this iteration of the course, we will focus on graphs and probabilistic method. 

    First meeting: 9 January 2019  

    First exercise session: 17 January 2019

    Lectures: Wednesday, 12:15 - 13:45. Room T4. You are expected to make an effort to attend the lectures and scribe one of the lectures. 

    Tutorials and Q&A sessions: Thursday, 16:15 - 18:15. Room T4. These sessions will be hands-on problem-solving sessions. At the beginning of each session, we will hand out an exercise sheet where you are expected to submit a small part of it at the end. 

    Lecturers:

    Teaching Assistants: 
    • Osama Abuzaid (osama.abuzaid@aalto.fi)
    • Miika Leinonen (miika.leinonen@aalto.fi)
    • Valtteri Lipiäinen (valtteri.lipiainen@aalto.fi)

    Prerequisite: Mathematical maturity. In particular, the ability to read and write basic mathematical proofs. Familiarity with the asymptotic analysis in discrete mathematics AND/OR analysis of algorithms would make your life much easier in this course. If you do not have these backgrounds, you will be expected to work harder in order to complete the courses. 

    Intended Learning outcomes: (i) Students are familiar with the basic concepts of graph theory and discrete probability. (ii) Students are able to apply some of these concepts to address questions arising in computer science.


    Grading: 

    Your grades will be determined by weekly problem sets, exercise sessions, and oral exams. In total, there are at least 110 points. (100 + B) where B = bonus points.  Standard points are distributed over several components. 

    • Weekly problem sets (50 points): There will be 9-10 problem sets. Each set has 4-6 questions and you would have one week to work on it. The problems will be out on Wednesday at noon and due on the following Wednesday at noon.
    • Scribe (10 points): You can get 10 points by scribing a lecture in LaTex and submit it for the whole class to read. At the beginning of each lecture, we will ask for 1-2 volunteers to do scribing for that class. In case there are 2 volunteers, this would become a group work. Here is the template to scribe the lectures.  Deadline for scribe: Following Monday 23:55. Submit a .zip file containing the .pdf, the .tex and the figures files for your scribe.

    • Exercise sessions (10 points): There will be 10 exercise sessions. Each session is associated with 1 bonus and will focus on helping you understand the detailed content of the lectures as well as the exercises. You will submit your work at the end of each session. 

    • Oral exam or final project (30 points): There will be an oral exam on the exam week. In particular, we will have it on April 10 & 11. Alternatively, you may choose to go in-depth into one research topic related to this course, read one or two difficult papers, and write a 5-page report about it. The deadline for final project would be April 30.
         Oral exam option is suitable for those who would not want to pursue research in related areas and simply want to focus on learning technical toolkits from the course.  
         Research report option would be ideal for those who are motivated by theoretical computer science research. 
           Note: It is mandatory to pass the oral exam or the final project to pass the whole course!


    Grading table

    • Grade 5: At least 75 points
    • Grade 4: At least 65 points
    • Grade 3: At least 55 points
    • Grade 2: At least 45 points
    • Grade 1: At least 35 points


    Tentative list of topics

    Each topic will be taught from the perspectives of applications in computer science.

    The first half of the course will focus on understanding some of the deep structural results of graph theory and their applications in computing exact or approximate solutions for many fundamental optimization problems. We will start with a couple of central problems in computer science, namely graph coloring, and matching, and learn some classical algorithms to solve them. Then we will go through more modern algorithmic approaches like kernelization, graph compression, and treewidth which are very actively used these days to get faster algorithms for NP-Hard problems. 

    Here is a tentative list of topics: 

    Introductory Lecture (9 Jan). 

    Graph Theory: 
    • Background reading: Basics of graph theory
    • Lecture 2 (16 Jan): Graph coloring
    • Lecture 3 (23 Jan): Matching 
    • Lecture 4 (30 Jan): Compression
    • Lecture 5 (6 Feb): Treewidth 1
    • Lecture 6 (13 Feb): Treewidth 2


    Discrete Probability: We will look at algorithms & complexity, and along the way, we will learn probability. 
    • Concentration bounds. Concepts introduced via Streaming Algorithms. 
    • Lovasz Local Lemma. Concepts introduced via algorithms for satisfiability & routing.  
    • Limited Dependency and expanders. Concepts introduced via Derandomization.  


    References:
    1. Graph Theory with Applications by Bondy and Murty
    2. Graph Theory by Diestel
    3. Introduction to Graph Theory by Douglas B. West

  • Lectures

  • Exercises Submissions

  • Scribe and bonus submissions

  • Project Submission