TDA251/DIT281, Period 2, 2017: Algorithms Advanced Course
Instructor
Assistants
- Jonatan Kilhamn, EDIT 5453, jonatan.kilhamn(at)gmail.com
- Prasanth Kolachina, EDIT 6113A, prasanth.kolachina(at)cse.gu.se
- Joel Gustafsson
- Sebastian Norlin
Announcements
- Student representatives: Vishnu Reveendra Nadhan (nadhan), Sy Hai Dinh (hasy), Abdul Sattar (gussattasa), Robin Åstedt (gusstedro) - Email: Add
"(at)student.chalmers.se", or "(at)student.gu.se" if the address begins with
"gu".
- The home exam. Deadline has expired.
Solutions.
- (Peter) Compare your exam answers to the published answers. I shall send
exam comments (and grade motivations) upon request at 23-24 January.
- (Peter) I am completely unreachable from 25 January until 11 February.
- Individual follow-up assignments for possible raise of your grade: Express
your interest by sending a mail, no later than Monday 26 February.
Lecture Times and Rooms
See TimeEdit.
Office hours:
Prasanth: Thursday 13-14
Jonatan: Friday 10-11 (not 22 Dec)
If you want to book a consultation time (outside the schedule) for
questions or help, please send a mail.
Topics and Assignments
Numbers in parentheses indicate related book sections. Number 0 indicates that
the topic is not in the book.
- Lecture 1. Approximation algorithms: Load balancing
(11.1). Center selection (11.2).
- Lecture 2. Non-constant approximation ratio: Set cover
(11.3). Pricing (primal-dual) method, example: vertex cover (11.4).
- Assignment 1.
- Lecture 3. Different "approximability": Disjoint paths
(11.5). Knapsack (11.8).
- Lecture 4. Approximation by linear programs (11.6).
Reductions and approximation (0). Maximum flow and minimum cut - short
repetition (7.1-7.2), preparing for reductions of various problems to flows
and cuts.
- Lecture 5. Disjoint paths and Menger's theorem (7.6). Circulations with demands and lower capacity bounds (7.7).
Survey design (7.8). Airline scheduling (7.9).
- Lecture 6. Reductions to min-cut. Image segmentation
(7.10). Project selection (7.11). Baseball elimination (7.12).
- Assignment 2.
- Lecture 7. Elementary probability theory - repetition (13.12, 13.3). Randomized algorithms: Global minimum cut (13.2).
- Lecture 8. Monte Carlo versus Las Vegas algorithms (0).
Max 3-Sat and the Probabilistic Method (13.4). Rigorous analysis of median
finding and Quicksort (13.5).
- Lecture 9. Dynamic programming on trees (10.2).
Complexity classes XP and FPT (0). Small vertex covers (10.1).
- Assignment 3.
- Lecture 10. Kernelization (0). Color coding (0).
Enumerating maximal cliques (0).
- Lecture 11. Chernoff bounds, with an application to
load balancing (13.9-13.10).
- Lecture 12. The mathematics behind hashing (13.6).
Finding closest points via hashing (13.7).
- Bloom filters and disjunct matrices (Research-related extra lecture,
given only this year. No lecture notes are provided, and the topic is not exam-relevant.)
Literature
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.
Learning Outcomes
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
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. (Clarification: It is expected to show this in both the assingments and the home exam.)
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
any time.
- 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.
Submission Instructions
- 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, they can
be hard to trace). Moreover, 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.