TDA251/DIT281, Period 2, 2019: Algorithms Advanced Course

Instructor

• Peter Damaschke, EDIT 6478, ptr(at)chalmers.se

Assistants

• Jeremy Pope (popje)
• Marwa Naili (naili)

Announcements

• Student representatives: Sebastian Nilsson (sebnils), Athanasios Rofalis (thanosrof(at)outlook.com), Mihkel Sildnik (sildnikmihkel(at)gmail.com).
• (Peter, 22nd January) We are working on the grading. If you have submitted a home exam, you should, at some time, receive a mail with your course grade and a short motivation. As exam review, check these comments and send me a mail if you think that we might have overlooked or misunderstood something. No action is needed if the comments look correct.
• Re-exam: Express your interest by mail before 28th Februrary (to discuss the requirements). The submission deadline will be 8th April.

Lecture Times and Rooms

Office hours for consultations, questions, help, until course week 7:

• Peter: by appointment (send a mail), room 6478
• Marwa: Wednesday 8:00-11:00, room 6449
• Jeremy: Wednesday 13:15-16:00, room 5474

Lectures

• Lecture 1. Approximation algorithms. Examples: Load Balancing (11.1). Center Selection (11.2). PDF.
• Lecture 2. Approximation algorithm for Set Cover (11.3). Pricing method - example: Vertex Cover (11.4). PDF.
• Lecture 3. Approximation scheme for Knapsack (11.8). Approximation by linear programming (11.6). PDF.
• Lecture 4. Reductions and approximation ratios. Network flows and cuts (7.1-7.3). PDF.
• Lecture 5. Bipartite Matching (7.5). Disjoint Paths (7.6). Circulations (7.7). Applications of flows: survey design (7.8). PDF.
• Lecture 6. Airline scheduling (7.9). Applications of cuts: image segmentation (7.10), project selection (7.11). - Probability recap (13.12). PDF.
• Lecture 7. Random variables (13.12). Randomized algorithms: Repeating a random experiment. Global Min-Cut (13.2). PDF.
• Lecture 8. Max-3-Sat (13.4). XP and FPT. Small vertex covers (10.1). PDF.
• Lecture 9. Kernelization. Dynamic programming on subsets. PDF.
• Lecture 10. Dynamic programming on trees (10.2). Analysis of random splitters (13.5). PDF.
• Lecture 11. Chernoff bounds with an application to load balancing (13.9-13.10). Veifying matrix products. PDF.
• Lecture 12. Hashing and finding closest points (13.6-13.7). PDF.

Compulsory Assignments

• Assignment 1. Deadline: expired.
• Assignment 2. Deadline: expired.
• Assignment 3. Deadline: expired.
• Home exam. Deadline: Wednesday 15 January, 23:59. This is also the final deadline for all exercise resubmissions.

Literature

Jon Kleinberg, Eva Tardos: Algorithm Design. Pearson/Addison-Wesley 2006.

However, some contents may come from various other materials, i.e., they are not in the book. It should be possible to follow the course using the Lecture Notes only, but the book may serve as supplementary material.

Learning Outcomes

• 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

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. Feel free to ask at any time what grade you can expect based on the solutions shown so far.

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

• 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.