Teaching scheme

Credits: 4

3 hours lecture + 0 hours tutorial

Course Objectives

1. To introduce the fundamentals of computational complexity theory.

2. To discuss basic concepts such as computational models, computational complexity measures (e.g., time and space complexity measures), complexity classes, reducibility and completeness notions.

3. To familiarize the concepts of randomized and approximation algorithms and discuss the related complexity classes.