TDA251/DIT280, Period 2, 2014: Algorithms Advanced Course




Lecture Notes

Numbers indicate the related book sections. Number "0" means that the material is not in the course book.

Times and Places

Monday 13:15-15:00, room ED
Thursday 8:00-9:45, room ED

Exercises: This course has no scheduled classroom exercise sessions. Exercise solutions have to be submitted in written form and are part of the examination (see Grading). However, we will provide some form of exercise help.

Consultation times outside the schedule can be booked individually or in small groups, by sending an email.

Course Description

This course is part of the master's programme Computer Science - Algorithms, Languages and Logic (MPALG) but is also of interest for various other programmes. The goal is to learn selected advanced techniques in the design and analysis of algorithms. It will continue in the spirit of the first Algorithms course and maintain a rigorous analytical style. It is assumed that you are taking this course because you like the subject and you want to gain a deeper understanding of more specialized topics in algorithms, not for a guide on how to implement them. At some points in the course we may even touch on frontiers of current research. We may also have possibilities to reflect upon the proper use of algorithms in reality, besides their mathematical aspects.

;-) Students who took this course also took:

Learning Outcomes

After the course you should


You MUST have passed a basic course in Algorithms (our local course or equivalent) and have a good background in Discrete Mathematics (sets, graphs, relations, combinatorics, logic, etc.) and Probability (random variables, expected values, conditional probability, etc.). You should be comfortable with rigorous mathematical analysis and proofs, and be familiar with:


Grading is based on compulsory hand-in exercises and a take-home exam that have equal weight. (Details about the exam will be announced.)

We do not use a point system and predefined thresholds, but we record the exercise comments and apply the following grading criteria.
5/VG: Your solutions are correct and also well explained, perhaps with very minor difficulties.
4/G: Mainly good solutions, but also some difficulties or gaps.
3/G: You show a basic understanding and can manage the majority of exercises, however with substantial difficulties.
U: Insufficient understanding and fundamental difficulties in most exercises.

Thus, not all exercises need to be "OK'd" in order to pass the course, but omissions can lower your grade. You may ask at any time during the course what your expected grade would be, based on your performance shown so far.

Not only problem solving but also the quality of technical writing is an important aspect of the exercises. (In the end one wants to communicate solutions to peers such that they can understand them without extra efforts.)

Some hand-in exercises may be marked as optional, but we recommend to try them anyway if you have the time, as they can positively influence your grade (and hopefully you find them interesting as such).

There is no scheduled re-exam, but you as a Chalmers student can improve your grade later on by follow-up assignments. (Be aware that this is not merely a formality. You must really achieve an improvement that justifies the higher grade.) You can express your interest before end of January, and the assignment should be finished before the end of study period 3. GU students do not have this possibility, according to GU regulations.

Homework Exercises

General Rules and Policies

Read them carefully and take them very seriously.


The course material is parts of the textbook

Jon Kleinberg, Eva Tardos: Algorithm Design. Pearson/Addison-Wesley 2006, ISBN 0-321-29535-8.

It should be available at Cremona at a price of ca 650 SEK, but it may be cheaper at other places. We are using this book also in the basic Algorithms course which covers much of the material in chapters 1-6 and 8.
The list of course topics is preliminary. Minor changes are always possible.