Topic outline
-
Teaching
Marc Hellmuth is head teacher.
Teaching assistant:Course literature
The course book Introduction to Algorithms by Cormen, Leiserson, Rivest, Stein.
The Part ``NP-completeness'' is based on Computers and Intractability by Garey and Johnson
The Part ``Fixed parameter algorithms" is based on Invitation to Fixed-Parameter Algorithms by Niedermeyer
Schedule (NOTE that rooms change from time to time )
The First Lecture starts on Sep 4 (1-4pm)
The Lecture and Tutorial on Sep 1 is cancelled (as Marc is at a conference)
The Turorial on Sep 22 will be replaced by an additional lecture.Lectures
The lectures will be offline (with changing locations - see schedule).
Recording of lectures given in the last years are available online.Tutorial
place and time : see scheduleExamination
Course examination is done in four parts:
- Home assignments (IND) worth 3ECTS,, graded A-F.
- Practical exercises (PE), worth 1.5 ECTS, graded P/F.
- A written exam ("THEO" on course documentation), worth 3 ECTS and graded A-F.
All assignments are individual and independent:
No cooperative hand-ins or hand-ins created with the help of ChatGPT, AI & Co are allowed (and will be treated as cheating/plagiarism)!
You need a passing grade on each course part to pass the course.Course grade
50% grade IND + 50% grade THEO = final grade
Written Exam
Will be offline for 4 hours (see schedule). This is NOT an open-book exam (no smartphones, tables, notebooks etc allowed).
Old Exams can be found under resources below.All students must sign up (“anmäla”) in Ladok to the written exams to be able to attend the exam. Late sign ups will not be accepted.
The sign-up in Ladok
- Opens a month before the exam
- Closes 10 days before the exam (holidays like Christmas can affect the closing date)
Lectures
All lecture-files (slides and videos of lectures in the last years) can be found under "resources" and the particular headings.
Note, that the content may be different to the current lectures.Additional reading material for interested students:- Part1 Turing Machines: Ch 1 & 2 in the course-book "Computers and Intractability" (nice summary also here: https://plato.stanford.edu/entries/turing-machine/)
- Part2 NP-completeness: Ch 2 & 3 in the course-book "Computers and Intractability"
- Part 3 Shortest Path: Ch 24 in the course-book "Intro. to Algor."
- Part 4 Dynamic Prg: Ch 25.2 and 15.3/4 in the course-book "Intro. to Algor."
- Part 5 Greedy and Matroids: Ch 16.4 and 23 in the course-book "Intro. to Algor."
- Part 6 Approximation Alg: Ch 35.1/2 in the course-book "Intro. to Algor."
- Part 7 Fixed parameter Alg: Ch 4, 7.1/4, 8.1/3 in course-book "Invitation to FPT"
- Part 8 Maximum Flow: Ch 26.1/2 in the course-book "Intro. to Algor."
News
-
[Sep 4]:
The Tutorial on Sep 22 will be replaced by an additional lecture.
Exercise 1 and PE1 are online. - [Sep 15]
Exercise 2 is online - [Sep 18]
Exercise 3 and PE2 are online - [Sep 22]
Updated script Part 5 (proof Thm 5.1 and Lemma 5.3) - [Oct 6]
Exercise 4 is online (with slightly extended deadline Friday Okt 17)
Resources
Here you can find the teaching material (incl. Slides, Script and Recordings of previous lectures).All videos can be found in the subsequent folders or collected in this channel.For all students that may have no sound on the videos, use VLC player together with the latest audio codecs! -
Here, all exercises and assignments for the individual assignments are listed. Upload latest 23:59pm of the respective date.
-
Here all practical exercises and assignments are listed. Upload latest 23:59pm of the respective date.