Advanced Algorithms (Autumn 2023)
Official course description:
Course info
Programme
Staff
Course semester
Exam
Abstract
This course will introduce students to techniques for solving complex programming tasks arising in modern IT systems. The focus in the course is on algorithm design and analysis.
Description
This course is the final course for the Algorithms specialisation. It gets students as close as possible to research in the field.
The course covers, among other topics, algorithms for numerical problems, algorithms for big data, optimization algorithms, randomized algorithms, lower bounds for computational problems, exponential-time and fixed-parameter tractable algorithms, and frameworks for parallel/distributed computation.
Formal prerequisites
As this is the final course for the Algorithms specialisation, prior knowledge of the design and analysis of data structures and algorithms (divide and conquer, greedy algorithms, dynamic programming, and basic graph algorithms) is required. This is obtained by successful completion of the preceding Master course on Algorithm Design.
The course also requires familiarity with linear algebra and some experience with probability theory. Therefore, successful completion of Linear Algebra and Probability is a prerequisite.
Intended learning outcomes
After the course, the student should be able to:
- Design and analyze algorithms for basic numerical problems
- Use randomization in the design and analysis of efficient algorithms
- Efficiently solve optimization problems using approximation algorithms
- Identify problems that are unlikely to admit efficient algorithms and argue for their difficulty via computational complexity theory
- Solve hard computational problems using efficient exponential-time algorithms
- Identify parameters in computational problems that enable efficient algorithms, design and analyze parameterized algorithms
Learning activities
We will spend 8 hours a week on lectures and exercises for the first 14 weeks of the semester.
You are expected to revise the lecture material in self-study, and you can gain more experience with algorithmic problem-solving through mandatory assignments that will be discussed in exercise sessions. These assignments combine theoretical problems and more practical implementation tasks.
Mandatory activities
At least 6 mandatory take-home assignments will be given out. The pedagogical purpose of the mandatory activities is to allow participants to study the theoretical material covered in the lectures in more depth and in a more applied manner.
Assignments will be graded "approved" or "not approved". Group submissions are allowed, provided that all group members are able to present all parts of the solution.Written formative feedback will be provided by the teacher.
Students need at least 5 approved assignments to be admitted to the exam. Otherwise, the student will receive the grade NA (not approved) at the ordinary exam, and the student will use an exam attempt.
If the student fails to hand in a mandatory activity or they receive a "not-approved", they must hand in a retry within at most two weeks after the initial deadline.
The student will receive the grade NA (not approved) at the ordinary exam, if the mandatory activities are not approved and the student will use an exam attempt.
Course literature
Basic literature on algorithms
- Jon Kleinberg, Éva Tardos: "Algorithm Design", 2006, Pearson (as used in the Algorithm Design course)
Randomized algorithms
- Michael Mitzenmacher, Eli Upfal: "Probability and Computing: Randomized Algorithms and Probabilistic Analysis", 2nd Edition, 2017, Cambridge University Press
Approximation algorithms
- Vijay V. Vazirani: "Approximation Algorithms", 2003, Springer (relevant chapters will be distributed in class)
Parameterized and fine-grained complexity
- Marek Cygan et al.: "Parameterized Algorithms", 2015, Springer (free PDF version available online)
Student Activity Budget
Estimated distribution of learning activities for the typical student- Preparation for lectures and exercises: 30%
- Lectures: 12%
- Exercises: 12%
- Assignments: 30%
- Exam with preparation: 16%
Ordinary exam
Exam type:B: Oral exam, Internal (7-point scale)
Exam variation:
B1I: Oral exam with time for preparation. In-house.
30 minutes
No
30 minutes
reexam
Exam type:B: Oral exam, Internal (7-point scale)
Exam variation:
B1I: Oral exam with time for preparation. In-house.
30 minutes
No
30 minutes
Time and date
Ordinary Exam Tue, 9 Jan 2024, 09:00 - 21:00Ordinary Exam Wed, 10 Jan 2024, 09:00 - 21:00
Reexam Fri, 8 Mar 2024, 09:00 - 12:00