TDA251/DIT280, Period 2, 2017: Algorithms Advanced Course
- Jonatan Kilhamn
- Prasanth Kolachina
- Joel Gustafsson
- Sebastian Norlin
- Course start: Monday 30 October 13:15.
- Be aware that you are supposed to have the knowledge from the first course
in Algorithms (or equivalent).
- The plan is to give three compulsory assignments, ca. every other week.
- Home exam, preliminary time window: from Monday 8 January 14:00 (release)
until Tuesday 9 January 18:00 (deadline).
Lecture Times and Rooms
Numbers in parentheses indicate related book sections. Number 0 indicates that
the topic is not in the book.
The list is preliminary, and small changes are always possible.
- Approximation algorithms: Load balancing (11.1). Center selection (11.2).
- Non-constant approximation ratio: Set cover (11.3). Pricing method,
example: vertex cover (11.4).
- Assignment 1: approximation.
- Different "approximability": Disjoint paths (11.5). Knapsack (11.8).
- Approximation by linear programs (11.6). Reductions and approximation (0).
- Maximum flow and minimum cut - short repetition (7.1-7.2). Disjoint paths
and Menger's theorem (7.6). Circulations with demands and lower capacity bounds
- Reductions of various problems to flows and cuts: Survey design (7.8).
Airline scheduling (7.9). Image segmentation (7.10). Project selection (7.11).
Baseball elimination (7.12).
- Assignment 2: reductions to flows and cuts.
- Elementary probability theory - repetition (13.12, 13.3). Randomized
algorithms (details will be provided).
- Problems with special input (details will be provided).
- Some "advanced advanced" topics, if time allows.
Jon Kleinberg, Eva Tardos: Algorithm Design.
Pearson/Addison-Wesley 2006, ISBN 0-321-29535-8.
The course is based on parts of this textbook (also used in our basic
Algorithms course) and perhaps additional materials.
After the course you should
- know in more depth some important design and analysis techniques for
algorithms, in particular, ways to approach NP-complete problems,
- to some extent be able to apply such techniques to solve new problems
that may arise in various applications,
- have some practice in recognizing connections between algorithmic problems
and reducing them to each other,
- be able to explain more complex algorithms and proofs in written form,
- know selected topics of current research on algorithms.
Grading is based on compulsory assignments and a take-home exam
that have equal weight. (Details about the exam will be announced in due time.)
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 minor difficulties.
4/G: Mainly good solutions, but also larger 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.
Not only the problem solving itself, 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.)
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.
- Exercise deadlines are firm. Delays must be motivated before the
deadlines. Unannounced late submissions will not be considered. Once you have
submitted a first version before the deadline, you are allowed to resubmit at
- It is allowed, even encouraged, to discuss the exercises during the course. Also, do not hesitate to ask if you have difficulties with the
exercises, or if something is unclear.
- However, you must write your final solutions on your own, using your
own words, and expressing them in the way you understood them yourself.
- Submitting others' work in your own name is cheating! It can lead to
severe consequences, in very bad cases even suspension from studies.
- Specifically, it is prohibited to copy (with or without modifications)
from each other, from books, articles, web pages, etc., and to submit solutions that you got from external persons. All sources beyond the course materials
must be explicitly acknowledged.
- You are also responsible for not giving others the opportunity to cheat.
We will not investigate who copied from whom.
- In the take-home exam you must work completely on your own and direct
questions to the teachers only.
- Respect the deadlines (see Rules and Policies). It is strongly recommended
to start working when the exercises have been posted, not only when the
deadline is approaching.
- Solutions must be submitted individually (not in groups!) by email
to "ptr..." The subject line must contain the course code and exercise numbers.
- Please send only PDF attachments, no other formats! Submitting
handwritten and scanned solutions is not encouraged, but if you do so, the PDF
must be legible.
- Send the entire assignment as one document, rather than a separate
file for each exercise.
- Write your name, personal number, and email address in the submitted
file (not only in the mail).
- A check list for your solutions:
- Have you really solved the given problems and come to conclusions?
- Are all answers and claims motivated?
- Is every step of your reasoning conclusive?
- If you describe an algorithm: Explain how and why it works, do not only
provide uncommented pseudocode.
- Be concise, avoid unnecessary additional writing. In particular, you need not
prove facts that are already known from the course.
- If you could not solve an exercise, submit anyway and point out precisely
where you got stuck. This may help us give further hints. An even better way is
to ask for help early.
- If you get feedback on an exercise: Improve your solution
accordingly and resubmit as soon as possible.
- Please resubmit the complete solution (not only isolated answers).
Moroever, it helps us if you mark the changes.
- There is no fixed limit on the number of resubmissions. However, try and
address all comments, to avoid long chains of only incremental
improvements. Also, no resubmission deadlines are set during the course; there will be only one final deadline for all resubmissions.