Prospectus

nl en

Complexity

Course
2021-2022

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

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< 5.0): final grade = exam grade

The teacher will inform the students how the inspection of and follow-up discussion of the exams will take place.

Reading list

  • Lecture notes of Dr. J. de Graaf

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

Registration

Aanmelding voor vakken verloopt via uSis. Hiervoor is de uSis-code van het vak nodig, die te vinden zijn in de Studiegids. Meer info over het inschrijven voor vakken of tentamens is hier te vinden.

MyTimetable

In MyTimetable kun je alle vak- en opleidingsroosters vinden, waarmee jij je persoonlijke rooster kunt samenstellen. Onderwijsactiviteiten waarvoor je in uSis staat ingeschreven, worden automatisch in je rooster getoond. Daarnaast kun je My Timetable gemakkelijk koppelen aan een agenda-app op je telefoon en worden roosterwijzigingen automatisch in je agenda doorgevoerd; bovendien ontvang je desgewenst per e-mail een notificatie van de wijziging.

Vragen? Bekijk de video-instructie, lees de instructie of neem contact op met de ISSC helpdesk.

Brightspace

Inschrijving voor vakken verloopt via uSis. Wanneer je je hier inschrijft voor een bepaald vak krijg je automatisch ook toegang tot de omgeving van dit vak via Brightspace.

Voor meer informatie over Brightspace kun je op deze link klikken om de handleidingen van de universiteit te bekijken. Bij overige vragen of problemen kan contact opgenomen worden met de helpdesk van de universiteit Leiden.

Contact

Lecturer: dr. V. Dunjko
Coordinator: Riet Derogee