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