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, 07.01.2019-12.04.2019

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

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

General

  • General

    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:

    • Prof. Parinya Chalermsook: Office hours (Room B305): Wednesday 14:30 - 15:30
    • Dr. Sumedha Uniyal
    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

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

Course home

Course home

Next section

Lectures►
Skip Upcoming events
Upcoming events
Loading There are no upcoming events
Go to calendar...
  • CS-E4555 - Combinatorics, 07.01.2019-12.04.2019
  • Sections
  • General
  • Lectures
  • Exercises Submissions
  • Scribe and bonus submissions
  • Project Submission
  • 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)‎