Course syllabus

Jump to today

TDA251/DIT251, Period 2, 2024: Advanced Algorithms

Instructor

Assistants

  • Isabel Ljungberg, isalju(at)chalmers.se
  • Bart Jelle van der Steenhoven, bartj(at)chalmers.se
  • Ida Dahl (student TA)

Announcements

  • Student representatives: Julia Kaufmann (julkau), Han Wu (hanwu), Yingjue Ma (yingjue), Edvard Heinmetz (gusheined), Huoyan Tan (gushuota).
  • Assignment 2 has been posted; see below. Deadline: Thursday, 28 November, 23:59.
  • Lecture 7 begins with conditional probabilities.
  • Tentative deadline for assignment 3: on Thursday, 12 December.
  • The planned last lecture date (if nothing unexpected happens) is Thursday, 12 December.
  • Peter: The time of my absence is, presumably, 20 December - 1 January. I will not be reachable during that time.

Teaching

It consists of 12 planned lectures (Monday 13-15, Thursday 10-12) and 3 compulsory assignments. The latter are also part of the assessment (besides a compulsory final home exam). The lecture hall is KC. See also TimeEdit.

Consultation times: by appointment.

Lecture Contents

Numbers in parentheses are corresponding sections in the textbook. (But some topics are not in the textbook.) Notes of future lectures are preliminary and might be updated as the course proceeds. Likewise, the remaining schedule is always preliminary, and minor changes are always possible. The Lecture Notes are in the "Files" section.

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

Compulsory Assignments

Literature

Large parts of the course are based on selected sections from the book

Jon Kleinberg, Eva Tardos: Algorithm Design. Pearson/Addison-Wesley 2006 (but any edition is fine).

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.

The material might be perceived as "graph-heavy", but this should not be surprising, as graphs are general structures that appear nearly everywhere. The course examples also come from other fields like scheduling, packing, decision making, geometry, and algebra.

Learning Outcomes

See also the course plan. 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,
  • know selected topics of current research on algorithms.

Grading

Grading is based on assignments and a home exam that are both compulsory and have equal weight. The assignments are usual problem solving exercises. In the home exam you will get some specific algorithmic problem, too, but it can be treated in a more essayistic form. The report will be evaluated based on depth, factual correctness, and clarity of presentation. The detailed exam problem(s) and instructions are posted in December, and the submission deadline is in the exam period in January.

We do not use any point system, but we record the feedback comments and apply the following grading criteria.

5: 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 motivated; notations are well defined. There are at most some minor weak points.
4: Your submissions mainly fulfill the above criteria, but with noticeable errors, difficulties, or gaps.
3: 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 get "OK" in order to pass the course, but omissions can lower your grade. We may communicate unofficial preliminary grades for your orientation.

Re-exam: You as a Chalmers student can improve your grade later on by improving your assignments and/or home exam or by doing follow-up assignments. (Be aware that this is not merely a formality. You must really achieve an improvement that justifies the higher grade.) Express your interest well in advance, such that we can clarify the requirements in your case. Two re-exam submission deadlines will be announced.

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. 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 notations, and expressing the solutions 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. To avoid unwanted similarities it is recommended to write always alone, from scratch and from memory. All sources of help 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!).
  • 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, study programme, and email address also in the PDF.
  • If you could not solve an exercise: Submit anyway what you have, and try to point out precisely where you got stuck. This may help us give further hints. Especially the first submission for every problem does not have to be perfect. Some problems can be challenging, and feedback and improvements are a normal part of the learning process in this course.
  • If you get feedback on an exercise: Improve your solution accordingly and resubmit as soon as possible.
  • Always 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.

Further remarks: Clear technical writing, besides solving the problems, is an important aspect of the assignments. Slight formulation details can make a difference: Even if two authors had the same solution in mind, one write-up can be comprehensible and the other one not. However, if you think that some comments are wrong or based on misunderstandings (we are not free of mistakes!), do not hesitate to ask and discuss your doubts.

Fire Submission System

Use the link that is provided here: Fire

To create an account: Go to the Fire submission system. Bookmark the link (you will need it again), click on "Click here to register as a student" and fill in your student email address. You will get a mail with a web address. Click this address, it leads you to a page where you can fill in your data: name, personal 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 have just created.

To submit a solution: Log on to Fire again. Upload the file(s) that make up your solution. Finally press the "submit" button. (This is easy to forget.) Fire will close exactly at the given deadlines, therefore, do not wait until the last minute.

Follow the submission instructions and submit your solutions as PDF files only. You should later receive a mail with comments.

 

Course summary:

Date Details Due