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.
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
The most recent timetable can be found on Roosters Informatica
Mode of instruction
Two sets of take-home assignments
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
Lecture notes of Dr. J. de Graaf
Links to other useful literature will be provided during the course
- 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 .
Lecturer: dr. V. Dunjko