TDA251/DIT280, Period 2, 2011: Algorithms Advanced Course
Instructor
Assistants
- Leonid Molokov, EDIT 6476, molokov(at)chalmers.se
- Birgit Grohe, grohe(at)chalmers.se
Announcements
- Student representatives: Jonas Hugo (hugoj), Jonathan Daugaard (daugaard).
-
Exercises 1-3.
Exercises 4-6.
Exercises 7-9.
Exercises 10-11.
Exercises 12-13.
Deadlines have expired.
- No further resubmissions please! And a clarification: If some exercises
do not get labeled "OK" in the end, this does not entail failing the
course. It may only influence the grade.
-
Take-home exam. Deadline has expired.
-
Exam answers. Compare your answers with these.
- Exam review: After grading we will not send individual exam feedback, but feel free to ask if you want a motivation of your grade, or if you have
specific questions about some items in the exam.
Course Description
This course is part of the master's programme CS-ALL (Computer Science -
Algorithms, Languages and Logic) but is also of interest for various other
programmes. The goal is to develop 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.
;-) Students who took this course also took:
- Discrete Optimization
- Algorithms for Machine Learning and Inference
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,
- understand some pieces of current research on algorithms.
Prerequisites
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:
- Time complexity and O-notation.
- Greedy algorithms and dynamic programming.
- Recurrences and divide-and-conquer.
- Some fundamental data structures and graph algorithms.
- Polynomial-time reductions and NP-completeness.
Grading
Grading is based on compulsory hand-in exercises and a take-home
exam. (Details on how the exam works will be announced.)
We do not use a point system but we record the exercise comments and apply the
following grading criteria: 5/VG means that your solutions are on the whole correct and well explained, perhaps with minor difficulties; 3/G means that
you show a basic understanding and have an idea how to approach the exercises, but with substantial difficulties; and 4/G is between these two. You may ask
at any time during the course what your expected grade would be, based on your
performance shown so far.
There is no formal re-exam, but it is possible to improve your grade later by
follow-up assignments. (But, of course, this is not only a formality, you
must really achieve an improvement that justifies the higher grade.) You can
express your interest before January, and the assignment should be finished
before the end of study period 3.
General 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.
- 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 other persons, unless you explicitly acknowledge
the sources and add your own explanations.
- You are also responsible for not giving others the opportunity to copy from your work. (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.
Times and Places
Tuesday 10:00-11:45, room HB3: lecture
Wednesday 8:00-10:00 and 10:00-12:00, room ML13: exercises
Thursday 13:15-15:00, room EB: lecture
Consultation times: by appointment. You can book a time by email.
Scheduled exercise sessions: They are aimed to practise problem solving
in small groups with supervision. The problems, normally more advanced
exercises chosen from the course book, are announced in the week before, and
we expect all students that want to participate in the exercise session to
have read and understood the problems, and ideally, to have already written
down sketches of solutions. There is no point in coming unprepared! If
problems are too hard, formulate at least some good questions that help you
overcome the difficulties. Groups can be built informally, they may change
from week to week, and supervisors will circulate between the groups to help
you step by step towards a full solution of each problem. The sessions are not
compulsory (and independent from the homework exercises), but they should be a
very good preparation for solving more algorithmic problems, not only in the
course but also in your future professional life.
Choose only one time (8-10 or 10-12) and, please, consider also the early time
slot.
Topics
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.
Lectures do not necessarily correspond to single topics. Numbers in parentheses refer to relevant sections in the textbook. Minor changes of the
contents are always possible.
- NP-completeness (8) - Not an independent course topic, but it will be
considered sometimes in connection with the problems we are studying.
- Approximation algorithms and schemes (11.1-11.5, 11.8) - If you cannot
compute the best solution in reasonable time, compute at least a good one.
For some NP-hard problems we can even get solutions arbitrarily close to
optimum.
- Linear programming (LP) and network flows (11.6, 7.1-7.3, 7.5-7.13)
- LP is a standard tool in optimization. Here we use it as a black box for
designing approximation algorithms. Network flows is a specific graph problem
that is efficiently solvable and has unexpected applications that do not even
resemble flows. That is, we can reduce various problems to LPs and flows.
- Randomized algorithms (13.2, 13.4-13.7, 13.9-13.10) - Random decisions
solve some algorithmic problems surprisingly simply and efficiently. Quicksort
and hashing are famous examples, but there are more.
- Helpful input structure: small parameters, trees, etc. (10.1-10.3) -
Worst-case analysis can be overly pessimistic because your inputs are not that
nasty. But your algorithms have to take advantage of the structured input.
Lecture Notes
-
Lecture 1. Approximation algorithms. Examples: Load Balancing. Center
Selection.
-
Lecture 2. Approximation algorithms continued: Set Cover. Pricing method.
Example: Weighted Vertex Cover.
-
Lecture 3. Disjoint Paths. An approximation scheme for Knapsack.
-
Lecture 4. Approximation algorithms from Linear Programming. Example:
Vertex Cover. - Network Flow. Max-Flow-Min-Cut-Theorem.
-
Lecture 5. Complexity of Network Flow. Briefly about various applications:
Bipartite Matching. Disjoint Paths. Menger's Theorem. Circulations. Example:
Survey Design.
-
Lecture 6. Further network constructions: Airline Scheduling. Project
Selection. Baseball Elimination.
-
Lecture 7. Minimum Cost Bipartite Perfect Matching.
- No lecture notes about basic probability theory, because this is a
prerequisite rather than part of the course.
-
Lecture 8. Global Minimum Cut randomized.
-
Lecture 9. Max-3-SAT. Median. Quicksort.
-
Lecture 10. Hashing. Closest Points.
-
Lecture 11. Chernoff bounds. Decentralized Load Balancing. XP and FPT.
Example: Vertex Cover.
-
Lecture 12. Vertex Cover kernelization. Color coding. Example: paths
of fixed length. Dynamic programming on trees.
Exercises
- Solutions to the hand-in exercises must be submitted individually
(not in groups!) by email to "ptr..." The subject line should contain the
course code and exercise number. Please send only plain text or PDF
attachments, no other formats. Write your name, personal number, and email
address also on the submitted attachments. (We may want to print them.)
Preferably send all solutions of the week in one document, rather than a
separate mail or file for each exercise.
- A check list for your submissions:
- Name and contact email on the actual submission?
- Have you really answered the given questions and come to conclusions?
- Are all answers and claims motivated?
- Are all steps of your reasoning logically strict?
- If you describe an algorithm: Explain how and why it works, do not only
provide uncommented pseudocode.
- If you could not solve an exercise, point out where you got stuck.
This may help us to give further hints.
- Avoid unnecessary additional writing. In particular, you need not prove
facts that are already known.
- If you get exercise feedback: Complete and improve your solutions
accordingly and resubmit as soon as possible. The earlier you resubmit, the
more chances you have. (The number of attempts is not limited. There will be only one final deadline for everything.) It may be appropriate to send an
entirely reworked solution, or it may be enough to clarify an open question -
you can decide by yourself, based on the comments.
- Recommended book exercises for self-study: 11.2, 11.7, 11.9, 11.10,
12.2, 12.3, 7.3-7.7, 7.13, 7.20a, 7.21, 7.29, 7.45, 7.46, 13.1-13.3, 13.8,
13.9, 13.11, 13.13, 13.15, 13.18b, 10.1, 10.3, 10.5a, 10.9.