Course Overview

The goal of this course is to give somewhat generic algorithmic
techniques to deal with computational intractability (typically, 
NP-completeness) when one needs practical solutions. The focus is on
techniques with guaranteed performance: either exact algorithms, or
algorithms with a guaranteed approximation ratio.

Learning Achievement

Competence

Course prerequisites

Grading Philosophy

Short written examination, practical work (writing software to solve
some NP-hard problem).

Course schedule

Examples of NP-hard and NP-complete problems. Examples of
polynomial-time reductions. Exact solving techniques: exhaustive
search, SAT-solvers, pseudo-polynomial algorithms. Optimization
problems and approximation algorithms. Introduction to fixed-
parameter tractability (FPT).

Course type

> Lectures and practical work: - 48 hours of face-to-face teaching. - 100 hours personal work.

Online Course Requirement

Instructor

Other information

- Level B2 CEFR in English.
- Previous studies (Bachelor level) within the domain of computer
science or similar.
- Basic knowledge of algorithmic techniques and complexity theory.

Duration: 12 weeks

Language of instruction: English
Mode of delivery: Face-to-face teaching: personal work

Site for Inquiry