Vanwege de coronamaatregelen kan de onderwijsvorm of tentaminering afwijken. Zie voor actuele informatie de betreffende cursuspagina’s op Brightspace.

Studiegids

nl en

Complexity

Vak
2020-2021

Admission requirements

Not applicable.

Description

This course studies the computational complexity of algorithms: intuitively. this is the computational effort (e.g. number of steps needed, or compute time) required for an algorithm to solve a problem.
We will discuss complexity-theoretic asymptotic notation (O-notation), worst and average case complexities, illustrate complexities of basic algorithms, and consider proofs of optimality using adversary arguments. In the second part of the course we will discuss computational complexity classes: classes that group computational problems according to their hardness. We will focus on the P class (problems solvable in polynomial time, the "easy" problems), the more challenging NP class, and the notion of completeness of a problem for a class.

Course objectives

The students will:

  • be able to perform a complexity analysis of basic algorithms

  • be able to prove the optimality of certain algorithms

  • gain an understanding of the basics of computational complexity classes, and the importance the class of NP-complete problems

Timetable

The most recent timetable can be found on Roosters Informatica

Mode of instruction

  • Lectures

  • Tutorials

Assessment method

  • Two sets of take-home assignments

  • Final exam

The average homework grade counts as a bonus if the exam grade is> = 5.0.
The final mark is then calculated as follows:if (exam grade> = 5.0): final grade = exam grade + (average homework grade) / 10; if (exam grade

Reading list

  • Lecture notes of Dr. J. de Graaf

  • Links to other useful literature will be provided during the course

Registration

  • You have to sign up for courses and exams (including retakes) in uSis . More information about signing up for classes and exams can be found here .

Contact

Lecturer: dr. V. Dunjko

Website

Complexity