TDA251/DIT281, Period 2, 2018: Algorithms Advanced Course
Instructor
Assistants
- Alejandro Gómez Londoño, alejandro.gomez(at)chalmers.se
- Aristide Tossou, aristide(at)chalmers.se
- Divya Grover, divya.grover(at)chalmers.se
Announcements
- Student representatives: Simon Andrieux (simon.andrieux(at)efrei.net),
Rasmus Jemth (jemthr), David Weber Fors (guswebed). - Email: Add the standard
address for Chalmers students, or for GU students if the user name begins with
"gus".
- Here is the home exam specification.
- You should have got a mail with the grade and motivation for it. As "exam review": If the motivation suggests that we may have overlooked or misunderstood something in your submissions, then contact me (Peter). No action is needed if the motivation seems appropriate.
- The re-exam consists of individual follow-up assignments. Express your interest before the end of February. We will discuss what is needed for a higher grade. The assignments should then be finished before the end of May.
Lecture Times and Rooms
See TimeEdit.
Office hours for consultations, questions, help, until course week 7:
- Peter: by appointment (send a mail), room 6478
- Aristide: Monday 15-17, room 6453
- Divya: Friday 9-11, room 6476
Lecture Notes
- Lecture 1. Approximation algorithms. Examples: Load
Balancing. Center Selection.
- Lecture 2. Approximation algorithm for Set Cover.
Pricing method - example: Vertex Cover.
- Lecture 3. Approximation scheme for Knapsack.
Approximation by linear programming.
- Lecture 4. Reductions and approximation ratios.
Network flows and cuts.
- Lecture 5. Bipartite Matching. Disjoint Paths. Circulations. Applications of flows: survey design, airline scheduling,
- Lecture 6. Applications of cuts: image segmentation, project selection. - Probability recap, random variables.
- Lecture 7. Randomized algorithms: Repeating a random
experiment. Global Min-Cut.
- Lecture 8. Max-3-Sat. Analysis of random splitters.
- Lecture 9. XP and FPT. Small vertex covers.
- Lecture 10. Dynamic programming on subsets and trees,
with examples.
- Lecture 11. Chernoff bounds with an application to load
balancing. Veifying matrix products.
- Lecture 12. Hashing and finding closest points.
- Lecture 13. Scheduling lectures by edge coloring in bipartite graphs - a surprising application of vertex covers.
Assignments
Literature
Large parts of the course are based on selected sections from the book
Jon Kleinberg, Eva Tardos: Algorithm Design.
Pearson/Addison-Wesley 2006.
Some contents come from various other materials. 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 syllabus and
kurs-pm. 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 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 and
breadth (coverage of methods), factual correctness, and clarity of presentation. The detailed exam problems and instructions are posted in December, and the
submission deadline is in the exam period in January. (Note: The exact form of
the home exam differs from previous years. The aim is to take away time pressure
and improve quality and learning effect.)
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.
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.
Submission Instructions
- When 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.
- 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 PDF (not
only in the mail).
- 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. (It can
be hard to trace them.) 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, in order to avoid long chains of incremental
improvements.
- No resubmission deadlines are set during the course. There will be only
one final deadline for all resubmissions.