TDA251/DIT280, Period 2, 2016: Algorithms Advanced Course
Teaching Staff
Email: add "(at)chalmers.se".
- Instructor: Peter Damaschke, EDIT 6478, (ptr)
- Instructor: Devdatt Dubhashi, (dubhashi)
- Instructor: Alexander Schliep, EDIT 41258, (schliep)
- Instructor/Course Responsible: Muhammad Azam Sheikh, EDIT 6220, (azams)
- For general matters and/or contents, you are welcome to contact me!
- Assistant: Aristide Tossou, (aristide)
- Assistant: Jonatan Kilhamn, (jonkil)
- Assistant: Birgit Grohe, (grohe)
- Assistant: Prasanth Kolachina, (prasanth.kolachina(at)cse.gu.se)
Announcements
- Exam Review: Friday, 10 February, between 09:00 - 11:00 in room EDIT 6128.
- Final Exam, and its
Solution.
- Old exams with solutions for practice purpose.
Exam2011, and its
solution.
Exam2014, and its
solution.
- Student Representatives: Jacob Gideflod,
Maxim Goretskyy,
Elin Blomgren.
- Deadline expired: Exercises:1-2,
Exercise: 3,
Exercises: 4-5,
Exercises: 6-8,
Exercise: 9,
Exercises: 10-11(local domains only), and the
Schedule .
- Final Deadline (last chance for resubmissions): 2017-01-06.
- Final Exam: We'll publish the exam on the course webpage on Jan. 13, kl 8:00. Deadline: Jan. 14, kl 20:00. Submission will be via FIRE.
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 & 4.
Different "approximability": Disjoint paths (11.5). Knapsack (11.8). Approximation by linear programs (11.6). Reductions and approximation (0).
- Lecture 5 & 6.
Network flow recap (7.1,7.2), Applications to graph problems (7.5 - 7.6)
Aircraft scheduling (7.9), Image segmentation (7.10), Baseball elimination (7.12),
choosing good augmenting paths (7.3, if time permits).
- Lecture 7.
Probability theory for randomized algorithms (13.12), Global minimum cut (13.2).
- Lecture 8.
Random Variables and their Expectation, Linearity of Expectation (13.3), Quicksort (13.5).
- Lecture 9 & 10.
Max 3-Sat - randomized approximation and the Probabilistic Method (13.4).
Mathematics behind hashing (13.6).
Finding closest points (13.7).
Chernoff bounds with an application (13.9, 13.10).
- Lecture 11 (only accessible via domains chalmers/gu).
Using structure of problem instances for algorithmic improvements: Fixed parameter tractable,
Vertex cover (10.1 & slides).
- Lecture 12 (only accessible via domains chalmers/gu).
Stringology-I: Motivation, Background. Counting frequent items using tries, hashes and Bloom filters.
Cache-behaviour as hidden cost in efficient algorithms and data structures. (slides)
- Lecture 13 (only accessible via domains chalmers/gu).
Stringology-II: Index-data structures for exact and approximate string matches. Suffix trees. (Along with the slides: Adjeroh, Bell and Mukherjee. The Burrows-Wheeler Transform. Springer, 2008
Suffix trees and suffix arrays - Springer. Free access through Chalmers)
- Lecture 14 (only accessible via domains chalmers/gu).
Stringology-III: Suffix trees finished. Efficient algorithms for approximate string matches.
Times and Places
Lectures:
- Monday 13:15-15:00, room SB-H7
- Thursday 8:00-9:45, room SB-H7
Deviations:
- Nov. 7 and 28, Monday 13:15-15:00, room SB-H4
- Nov. 10 and Dec. 1, Thursday 8:00-9:45, room SB-H5
Consultation times:
- Monday 10:00-12:00, room EDIT-6128
- A meeting outside the schedule can be booked individually or in small groups, by sending an email to Azam.
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.
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
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.
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.)
- 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
- There will be 6 exercises, one every week starting from the first week. Click here for the details.
- Solutions to the hand-in exercises must be submitted individually (not
in groups!) through the FIRE system. See the Submission Details below.
- A check list for your submissions:
- Have you written your name, personal number, and email address on the submitted
attachments? (We may want to print them.)
- 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 (that is the stuff which we have discussed in lectures/course material).
Submission Details
-
The link to the Fire submission system: Here -
First create an account in the Fire system. You do this only once.
- As all exercises are individual, you don't have to create a group in Fire.
- To create an account: Go to the submission system. Use only the
link on the course homepage. Bookmark it (you will need it again), click on
"Click here to register as a student" and fill in your email address,
preferably the Chalmers address. You will get a mail with a web address. Click
the address, it leads you to a page where you can fill in your data: name,
personal security number, and a password. Spell your name correctly as
"Firstname Surname" (only the most commonly used first name is needed, with big
initial letters) and write your personal number as yymmdd-xxxx with the dash,
i.e., the minus sign. Log on using the account you just created.
- To submit a solution: Log on to Fire again. Upload the file that
make up your solution. Finally (easy to forget), press the "submit" button.
Fire will close exactly at the given deadlines, therefore, do not wait until
the last minute.
-
Solutions should be submitted as one PDF file (also if you submit several
exercises of the week), created with a word processor or latex or by scanning
handwritten sheets - provided that they are readable.
- Feedback/Resubmit: From the grader you will receive a mail with comments and a label "pass" or
"fail" is assigned to your assignment. You can also download
the comments from Fire. A "fail" is given in order to enable possible resubmissions of corrected or
improved solutions.
In case of a "fail", 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 limited to 3. However, 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.