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
You will find the timetables for all courses and degree programmes of Leiden University in the tool MyTimetable (login). Any teaching activities that you have sucessfully registered for in MyStudyMap will automatically be displayed in MyTimeTable. Any timetables that you add manually, will be saved and automatically displayed the next time you sign in.
MyTimetable allows you to integrate your timetable with your calendar apps such as Outlook, Google Calendar, Apple Calendar and other calendar apps on your smartphone. Any timetable changes will be automatically synced with your calendar. If you wish, you can also receive an email notification of the change. You can turn notifications on in ‘Settings’ (after login).
For more information, watch the video or go the the 'help-page' in MyTimetable. Please note: Joint Degree students Leiden/Delft have to merge their two different timetables into one. This video explains how to do this.
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
From the academic year 2022-2023 on every student has to register for courses with the new enrollment tool MyStudyMap. There are two registration periods per year: registration for the fall semester opens in July and registration for the spring semester opens in December. Please see this page for more information.
Please note that it is compulsory to both preregister and confirm your participation for every exam and retake. Not being registered for a course means that you are not allowed to participate in the final exam of the course. Confirming your exam participation is possible until ten days before the exam.
Extensive FAQ's on MyStudymap can be found here.
Contact
Lecturer: dr. V. Dunjko
Coordinator: Education coordinator LIACS bachelors
Remarks
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.