Avancerade algoritmer

Please use the CANVAS PAGE.  From 2017, the course will be hosted on CANVAS. 

===================================

Important 

To make sure that you don't miss any news, please set your notification at "My Settings" --> "Notifications". 

When you send an email to the lecturer or TAs, please put "[DD2440]" in front of the email subject.

General information about the course

This course will focus on advanced algorithms, and in particular algorithms developed in the last few decades. This course will focus on two modern ideas: Approximation and Randomization. The course will also touch various computational models emerged from the need of using computation in different situations. In case of questions, please send an email to danupon@kth.se. 

People & Office hours

Lecturer: Danupon Nanongkai (danupon@kth.se, danupon@gmail.com)

Teaching Assistants:  

• Jan van den Brand <janvdb@kth.se>
• Mohit Daga <mdaga@kth.se>
• Mehmet Berk Gedik <gedik@kth.se>
• Yassir Jedra <jedra@kth.se>
• Dmytro Kalpakchi <dmytroka@kth.se>
• Thatchaphol Saranurak <thasar@kth.se>

Learn more about the staff at the staff page .

Office hours 

Office Hours:  You can meet some of the TAs at the following time and locations. 

• Monday 3-4pm: Danupon (Room 1525)
• Tuesday 3-4pm: Thatchaphol (Room 1526)
• Wednesday 3-4pm: Mohit (Room 4528)
• Thursday 3-4pm: Jan  (Room 4528)

Besides, there are a few master students that will participate in grading your work from time to time. 

Office hour appointment with main TAs: Please make an appointment by email at least 24 hours before the actual office hour. Otherwise, availability cannot be guaranteed. 

Venue: Office hours will be held at the TCS department, which is on Level 5 at Lindstedtsvägen 3 [map].

Tutorial: You may request any TA for a tutorial in small group. Please post your request (with as much details as possible) on this course website so that other participants can consider joining. This is based on the TA's availability which cannot be guaranteed. 

Main changes from previous years

1. The course grading scheme will be criteria-based instead of point-based. This means that it is not possible to pass to course by, e.g., finishing only projects without doing any exercises. This is the change that have been implemented in an increasing number of courses at KTH. This year, it will be implemented for DD2440, although there will be some parts that are not completely changed. Read more about the grading criteria at the examination page. You are welcome to send the lecturer your thought about this change. 

2. Peer-reviewing process will play a bigger role this year. In particular, besides you are expecting to criticize works written by other course participants (i.e. homework solutions and project reports). 

Before the course starts

Background in discrete mathematics, basic probability, and basic algorithms and analysis is a must for this course. Make sure to review what you have previously learned in Algorithms, Data Structures and Complexity course (DD1352) and Discrete Mathematics course (SF1630/SF1631). In particular, make sure that you are familiar with the running time analysis, big-Oh notation, the notion of NP-completeness, and basic probability. To check if you have enough familiarity with the background, try reading materials from the first few lectures in the previous year here and work on previous exercises here. 

Reading materials

The main reading source for the course is the hand-written notes and/or slides used in the lectures. We will also provide some links to extra materials. Relevant chapters and other lecture notes for each lecture will be provided before the lecture. They can be found on the "Reading Materials" page.

About 70% of the materials in this course are similar to those from 2015 which can be found at this page; thus, those who which to study ahead of time are encouraged to study from this page, and work on exercises from the previous year. You are also strongly encouraged to search for extra materials by themselves on the internet. After all, it is an objective of the course for the participants to be able to study algorithms independently. (EXCEPTION: For your exercises, you cannot search for solutions or hints, or even anything remotely related, on the internet.)

Since many topics covered in this course are advanced topics, there is no single textbook that covers all of them. Some books that should be good starting points are:

• A Graduate Course in Algorithm Design and Analysis by Sanjeev Arora. (See the related course homepage at Princeton here.)
• Computer Science Theory for the Information Age by John Hopcroft and Ravi Kannan. (See the related course homepage at CMU here.)

Feedback

If you have any feedback about the class (e.g. if it is too fast, too slow, too hard, or too easy), please provide your feedback either by writing a post, sending an email to Danupon, or filling in this form.

Want to learn more?

If the class is not challenging enough, attend our Theory Reading Group & Lunch Seminar sometimes!

KTH also organized the Swedish Summer school in Computer Science every summer, and we usually have 1-2 free spots for exceptional master students.

And if you are truly interested and want to pursue a PhD, do not be shy to contact our faculties. (Danupon, for example, have some vacant positions.)