Advanced Algorithms (Autumn 2019)

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. Successful completion of Linear Algebra and Probability is also required.

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
• Solve problems on big data efficiently, also in frameworks for parallel and distributed computation
• 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 in weekly assignment sheets that will be discussed in exercise sessions.

Mandatory activities

At least 11 weekly take-home assignments will be given out. Assignments are submitted in the next week and will be discussed in the exercise session. Each assignment provides the same amount of points. At least 50% of total points over all assignments must be achieved before you can take the exam. Students may be required to present their solutions during the exercise session.

Submissions in groups of at most 3 students are allowed, provided that all group members are able to present all parts of the solution.

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

Jon Kleinberg, Éva Tardos: "Algorithm Design", 2006, Pearson
Steven Skiena: "The Algorithm Design Manual", 2nd edition, 2008, Springer
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: "Introduction to Algorithms", 3rd Edition, 2009, The MIT Press

Ordinary exam

Exam type:
B: Oral exam, internal (7-trinsskala)
Exam variation:
B1I: Oral exam with time for preparation. Inhouse. The preparation will take place at the university.
Exam description:

Students are expected to present a randomly chosen lecture topic and answer questions by the examiner. Questions may also refer to material covered on assignment sheets.

Preparation time: 30 minutes.

Duration of the oral exam: 30 minutes.

Time and date