TDA251/DIT280, Period 2, 2014: Algorithms Advanced Course
Instructor
Assistants
- Fredrik Johansson, EDIT 6447, frejohk(at)chalmers.se
- Olof Mogren, EDIT 6447, mogren(at)chalmers.se
- Prasanth Kolachina, EDIT 6113, prasanth.kolachina(at)cse.gu.se
Announcements
- Student representatives: Joanna Eriksson (joannae), Jacob Hagstedt
(suorra).
- Deadlines have expired for:
Exercises
1-2.
Exercises
3-4.
Exercises
5-6.
Exercises
7-8.
Exercises
9-10.
Exercises
11-12.
- Home
exam and
solutions.
- Compare your exam solutions with the published ones. Individual exam
comments and grade motivations are sent upon request. If you want to discuss
your grade in person, there are opportunities on Tuesdays, 10 and 17 February,
12:00-13:00, in room 6478. But please send a mail if you intend to come.
- Re-exam: If you want to do follow-up exercises to improve your grade,
request them before Friday, 20 February. (Send a request also if you have
already indicated interest earlier.) The assignments should then be finished
before the end of period 3.
Lecture Notes
Numbers indicate the related book sections. Number "0" means that the material
is not in the course book.
- Lecture 1.
Approximation algorithms: Load balancing (11.1). Center selection (11.2).
- Lecture 2.
Approximation continued: Set cover (11.3). Pricing method for vertex
cover (11.4).
- Lecture 3.
Different "approximability": Disjoint paths (11.5). Knapsack (11.8).
- Lecture 4.
Approximation by linear programs (11.6). Reductions and approximation (0).
- Lecture 5.
Network flow recap (7.1,7.2,7.5).
- Lecture 6.
Preflow-push algorithm (7.4). Probability theory for randomized
algorithms (13.12, 13.3).
- Lecture 7.
Probability theory finished (13.3). Randomized algorithms: Global
minimum cut (13.2).
- Lecture 8.
Max 3-Sat - randomized approximation and the Probabilistic Method (13.4).
Median (13.5).
- Lecture 9.
Briefly about Quicksort (13.5). Mathematics behind hashing (13.6).
Finding closest points (13.7).
- Lecture 10.
Chernoff bounds with an application (13.9, 13.10). Verifying a matrix
product (0).
- Lecture 11.
Complexity classes XP and FPT. Example: small vertex covers (10.1).
- Lecture 12.
FPT by dynamic programming on subsets, with problem examples (0).
- Lecture 13.
Dynamic programming on trees (10.2). Data anonymization via Set Cover (0).
Times and Places
Lectures:
Monday 13:15-15:00, room ED
Thursday 8:00-9:45, room ED
Exercises: This course has no scheduled classroom exercise sessions.
Exercise solutions have to be submitted in written form and are part of the
examination (see Grading). However, we will provide some form of exercise help.
Consultation times outside the schedule can be booked individually or
in small groups, by sending an email.
Course Description
This course is part of the master's programme Computer Science - Algorithms,
Languages and Logic (MPALG) but is also of interest for various other
programmes. The goal is to learn selected 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. We may also have possibilities
to reflect upon the proper use of algorithms in reality, besides their
mathematical aspects.
;-) 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 that have equal weight. (Details about the exam will be announced.)
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 very minor difficulties.
4/G: Mainly good solutions, but also some 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. You may ask at any time during the course
what your expected grade would be, based on your performance shown so far.
Not only problem solving 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.)
Some hand-in exercises may be marked as optional, but we recommend to try
them anyway if you have the time, as they can positively influence your
grade (and hopefully you find them interesting as such).
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 end of January, and
the assignment should be finished before the end of study period 3.
GU students do not have this possibility, according to GU regulations.
Homework 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, personal number, 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. Also, no
resubmission deadlines are set during the course; there will be only one final deadline for all resubmissions. 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.
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. We will be particularly watchful
if exercises appear as (alleged) innocent questions in internet forums.
- 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.
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.
The list of course topics is preliminary. Minor changes are always possible.
- NP-completeness - Not an independent course topic, but it will be
considered sometimes in connection with the problems we are studying.
- Approximation algorithms and schemes - 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 some elaboration on network flows
- 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 numerous applications. That is,
we can reduce various problems to LPs and flows.
- Randomized algorithms - 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. -
Worst-case analysis can be overly pessimistic because real inputs are not
that nasty. But your algorithms have to take advantage of the structured
input.