2023/2024
Computational Complexity
Type:
Mago-Lego
Delivered by:
Big Data and Information Retrieval School
When:
1 module
Online hours:
52
Open to:
students of one campus
Language:
English
ECTS credits:
3
Contact hours:
10
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.