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

Instructor

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

Assistants

• Jonatan Kilhamn, EDIT 5453, jonatan.kilhamn(at)gmail.com
• Prasanth Kolachina, EDIT 6113A, prasanth.kolachina(at)cse.gu.se
• Joel Gustafsson
• Sebastian Norlin

Announcements

• Student representatives: Vishnu Reveendra Nadhan (nadhan), Sy Hai Dinh (hasy), Abdul Sattar (gussattasa), Robin Åstedt (gusstedro) - Email: Add "(at)student.chalmers.se", or "(at)student.gu.se" if the address begins with "gu".
• The home exam. Deadline has expired. Solutions.
• (Peter) Compare your exam answers to the published answers. I shall send exam comments (and grade motivations) upon request at 23-24 January.
• (Peter) I am completely unreachable from 25 January until 11 February.
• Individual follow-up assignments for possible raise of your grade: Express your interest by sending a mail, no later than Monday 26 February.

Lecture Times and Rooms

Office hours:
Prasanth: Thursday 13-14
Jonatan: Friday 10-11 (not 22 Dec)

If you want to book a consultation time (outside the schedule) for questions or help, please send a mail.

Topics and Assignments

• Lecture 1. Approximation algorithms: Load balancing (11.1). Center selection (11.2).
• Lecture 2. Non-constant approximation ratio: Set cover (11.3). Pricing (primal-dual) method, example: vertex cover (11.4).
• Assignment 1.
• Lecture 3. Different "approximability": Disjoint paths (11.5). Knapsack (11.8).
• Lecture 4. Approximation by linear programs (11.6). Reductions and approximation (0). Maximum flow and minimum cut - short repetition (7.1-7.2), preparing for reductions of various problems to flows and cuts.
• Lecture 5. Disjoint paths and Menger's theorem (7.6). Circulations with demands and lower capacity bounds (7.7). Survey design (7.8). Airline scheduling (7.9).
• Lecture 6. Reductions to min-cut. Image segmentation (7.10). Project selection (7.11). Baseball elimination (7.12).
• Assignment 2.
• Lecture 7. Elementary probability theory - repetition (13.12, 13.3). Randomized algorithms: Global minimum cut (13.2).
• Lecture 8. Monte Carlo versus Las Vegas algorithms (0). Max 3-Sat and the Probabilistic Method (13.4). Rigorous analysis of median finding and Quicksort (13.5).
• Lecture 9. Dynamic programming on trees (10.2). Complexity classes XP and FPT (0). Small vertex covers (10.1).
• Assignment 3.
• Lecture 10. Kernelization (0). Color coding (0). Enumerating maximal cliques (0).
• Lecture 11. Chernoff bounds, with an application to load balancing (13.9-13.10).
• Lecture 12. The mathematics behind hashing (13.6). Finding closest points via hashing (13.7).
• Bloom filters and disjunct matrices (Research-related extra lecture, given only this year. No lecture notes are provided, and the topic is not exam-relevant.)

Literature

The course is based on parts of this textbook (also used in our basic Algorithms course) and perhaps additional materials.

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 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 minor difficulties.
4/G: Mainly good solutions, but also larger difficulties or gaps.
3/G: You show a basic understanding and can manage the majority of exercises, however with substantial difficulties. (Clarification: It is expected to show this in both the assingments and the home exam.)
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.

Not only the problem solving itself, 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 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.
• In the take-home exam you must work completely on your own and direct questions to the teachers only.

Submission Instructions

• 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 submitted file (not only in the mail).
• A check list for your solutions:
  - Have you really solved the given problems and come to conclusions?
  - Are all answers and claims motivated?
  - Is every step of your reasoning conclusive?
  - If 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.
• 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, they can be hard to trace). 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, to avoid long chains of only incremental improvements. Also, no resubmission deadlines are set during the course; there will be only one final deadline for all resubmissions.