TDA251/DIT281, Period 2, 2020: Algorithms Advanced Course





Due to the exceptional circumstances, it consists of these components:

Self-study of Notes that are provided in advance. Please do not hesitate to email questions to the instructor, at any time, and about all points that are unclear to you.

Online sessions starting on Mondays 13:15 and Thursdays 10:00. They are used for question hours, summarizing lectures of more central or more difficult topics, and maybe other forms upon need. Details will be announced continuously in the Announcements section above.

Compulsory assignments (as in normal years) which are part of the grading but also a major part of the learning process.

Lecture Notes

Numbers in parantheses are corresponding sections in the textbook. Note that not all topics appear in the textbook.

Typos, Clarifications, etc.

Lecture 1, page 3, line -4: The second sum ends with n rather than m.

Compulsory Assignments


Large parts of the course are based on selected sections from the book

Jon Kleinberg, Eva Tardos: Algorithm Design. Pearson/Addison-Wesley 2006.

However, some contents may come from various other materials, i.e., they are not in the book. It should be possible to follow the course using the Lecture Notes only, but the book may serve as supplementary material.

Learning Outcomes

See also the course plan. After the course you should


Grading is based on compulsory assignments and a home exam that have equal weight. The assignments are usual problem solving exercises. In the home exam you also get some specific algorithmic problem, but it can be treated in a more essayistic form. The report will be evaluated based on depth, factual correctness, and clarity of presentation. The detailed exam problem(s) and instructions are posted in December, and the submission deadline is in the exam period in January.

The previous exam from 2019 may give an impression.

We do not use any point system, but we record the feedback comments and apply the following grading criteria.

5/VG: Your solutions are correct; they really solve the given problems; they are presented in a logical order and can be followed step by step; all these steps are conclusive; all claims are weil motivated; notations are well defined. There are at most some minor weak points.
4/G: Your submissions mainly fulfill the above criteria, but there also remain noticeable errors, difficulties, or gaps.
3/G: You show a basic understanding of the topics and can manage most problems, however with substantial difficulties.
U: Insufficient understanding and fundamental difficulties in most topics.

Thus, not all exercises need to be "OK'd" in order to pass the course, but omissions can lower your grade. Feel free to ask at any time what grade you can expect based on the solutions shown so far.

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 a certain deadline, and the assignment should be finished before another deadline (to be announced). GU students do not have this possibility, according to GU regulations.

Rules and Policies

Read them carefully and take them very seriously.

Submission Instructions

We do not use the Assignments feature of Canvas, but everything is done simply by mail. This system (or rather non-system) has proved, over the years, to be well suited for the pedagogical goals of this course, as it is most flexible. Further remarks: Clear technical writing, besides solving the problems, is an important aspect of the assignments. Slight formulation details can make a difference: Even if two authors had the same solution in mind, one write-up can be comprehensible and the other one not. If you think that some comments are wrong or based on misunderstandings (we are not free of mistakes!), do not hesitate to discuss your doubts. Anyway, this is part of the resubmission process.