Master
2022/2023
Computational Complexity
Type:
Elective course
Area of studies:
Applied Mathematics and Informatics
Delivered by:
Big Data and Information Retrieval School
Where:
Faculty of Computer Science
When:
2 year, 1 module
Mode of studies:
distance learning
Online hours:
82
Open to:
students of one campus
Instructors:
Bruno Frederik Bauwens
Master’s programme:
Магистр по наукам о данных (заочная)
Language:
English
ECTS credits:
5
Contact hours:
8
Course Syllabus
Abstract
This course teaches the basics of computational complexity theory, approximation, and probabilistic algorithms for solving intractable problems including those from data analysis. You will learn:
- definitions of the complexity classes P, NP, and PSPACE,
- techniques to prove that a problem is NP-complete, and
- approaches to solving such problems including exponential algorithms other than exhaustive search, approximation algorithms, and efficient algorithms for special cases.
Learning Objectives
- Be able to recognize whether computational problems are in P, are in NP, are NP-hard, or are PSPACE-hard, by either giving an efficient algorithm or presenting a reduction from a well-known NP-complete or PSPACE-complete problem
- Know various techniques to deal with NP-hard search and optimization problems, both theoretically and at a practical level. We focus on (1) solving hard problems for special inputs, (2) improving exhaustive search, (3) efficiently finding approximate solutions.
- Understand the hardness of several variants of clustering.
- Be aware of other computational complexity classes, relations between these classes, and some open questions in computational complexity.
- Throughout the course, we pay special attention to the Travelling Salesman problem, and the final project asks you to apply the techniques mastered throughout the course to design and implement an algorithm solving this problem in the most efficient way you can think of.
Expected Learning Outcomes
- Be able to recognize whether computational problems are in P, are in NP, are NP-hard, or are PSPACE-hard, by either giving an efficient algorithm or presenting a reduction from a well-known NP-complete or PSPACE-complete problem
- Know various techniques to deal with NP-hard search and optimization problems, both theoretically and at a practical level. We focus on (1) solving hard problems for special inputs, (2) improving exhaustive search, (3) efficiently finding approximate solutions.
- Understand the hardness of several variants of clustering.
- Be aware of computational complexity classes, relations between these classes, and some open questions in computational complexity.
Course Contents
- 1. Easy and hard problems
- 2. NP and NP-completeness
- 3. Dealing with Hardness
- 4. Approximation algorithms
- 5. Probabilistic and space complexity
- 6. Clustering
Assessment Elements
- QuizzesWeekly quizzes.
- Staff-graded Assignments
- Final project
- Final exam
- Programming Assignments
Interim Assessment
- 2022/2023 1st module0.2 * Quizzes + 0.2 * Final exam + 0.25 * Programming Assignments + 0.15 * Final project + 0.2 * Staff-graded Assignments
