Exam
There is a 5-hour long individual, written, closed-book exam at the end of the course, where you can only use blank paper, pencils, and an eraser, that is no help: no books, no slides, no notes, no electronic devices, etc:
Exam: at the end of period 3, please see Ladok, and don’t forget to register for the exam.
First re-exam: June 2025, time and place to be announced
Second re-exam: August 2025, time and place to be announced
Previous exams: 2025, 2024, 2023, 2022, 2021, 2020, 2019, 2018, 2017, and 2016.
There will be a question on establishing NP-completeness for some problem, and at least half the points of that question must be earned in order to pass the exam. The exam questions will be drawn from the following list or will be very similar to questions in this list:
Probabilistic Analysis: Exercises 5.2-{1,2,5,6} of CLRS4.
Randomised Algorithms: Exercises 5.3-{2,3,4} of CLRS4.
Amortised Analysis: Exercises 16.1-{1,3} of CLRS4; Exercises 16.2-{1,2} of CLRS4; and Exercise 16.3-2 of CLRS4.
NP-Completeness: Exercise 34.5-2 of CLRS4 by following the hint in one step; Exercises 34.5-{5,6,7} of CLRS4; Problem 34-1ab of CLRS4 by following the hint in one step; Exercise 35.3-2 of CLRS4; and Problem 35-1a of CLRS4 by following the hint in one step; exercises not in CLRS4 (version of 2025-06-19).
Approximation Algorithms: Exercises 35.1-5 of CLRS4; Exercise 35.4-2 of CLRS4; and Problems 35-{1bcde,3} of CLRS4.
Since it is a closed-book exam, the questions will be asked in a self-contained way.
Exam study groups are allowed and even encouraged, as the exam is individual. The exam topics are taught as early as possible towards maximising the time available for exam preparation. Exam preparation sessions under the supervision of the head teacher (and assistants) cannot be organised, as that would 'burn' the CLRS4 questions tackled in such sessions.
Expected Effort
One higher-education credit (ECTS credit) translates under Swedish university law into an expected 26.67 hours of work for the average student. Hence 133.33 hours are expected on this 5-credit course.
The exam is worth 3 credits. The actual preparation and taking of the exam are expected to take 52 hours. Recall also that 21 hours are spent on attending the lectures and that 60 hours are expected on working for the 2 credits for the assignments.
All this does not clash with other courses you are taking, as university studies are legally defined to take 400 hours of work per study period (normally 10 weeks), and the standard 15 credits targeted in a study period are calibrated to reach that total.