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

- Jonatan Kilhamn
- Prasanth Kolachina
- Joel Gustafsson
- Sebastian Norlin

- Course start: Monday 30 October 13:15.
- Be aware that you are supposed to have the knowledge from the first course in Algorithms (or equivalent).
- The plan is to give three compulsory assignments, ca. every other week.
- Home exam, preliminary time window: from Monday 8 January 14:00 (release) until Tuesday 9 January 18:00 (deadline).

The list is preliminary, and small changes are always possible.

- Approximation algorithms: Load balancing (11.1). Center selection (11.2).
- Non-constant approximation ratio: Set cover (11.3). Pricing method, example: vertex cover (11.4).
- Assignment 1: approximation.
- Different "approximability": Disjoint paths (11.5). Knapsack (11.8).
- Approximation by linear programs (11.6). Reductions and approximation (0).
- Maximum flow and minimum cut - short repetition (7.1-7.2). Disjoint paths and Menger's theorem (7.6). Circulations with demands and lower capacity bounds (7.7).
- Reductions of various problems to flows and cuts: Survey design (7.8). Airline scheduling (7.9). Image segmentation (7.10). Project selection (7.11). Baseball elimination (7.12).
- Assignment 2: reductions to flows and cuts.
- Elementary probability theory - repetition (13.12, 13.3). Randomized algorithms (details will be provided).
- Problems with special input (details will be provided).
- Some "advanced advanced" topics, if time allows.

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

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

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.

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

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

- 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). Moroever, 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.