Ämnesdisposition

  • Course information

    Fäll ihop allt Expandera allt

    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)

    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 schedule


    Examination

    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

      • note that the schedule changed (see text under TEACHING)!
      • Sep 2: update  "Part1-Slides.pdf" was updated (L is TM-recognizable if and only if .. )
      • Sep 5: update "Part1-Slides.pdf" and "Part2-Slides.pdf"
      • Sep 6: NEW Part 8 (fixed parameter algorithms) has been added.
      • Sep10: Exercise 2 (Ind1) + Programming Exercise (PE) is online
      • Sep18: Exercise 1 (part of IND1) corrected (questions regarding Q1,Q2 or Q4 directed to Axel, regarding Q3 or Q5 directed to Anna).
      • Sep18: details on lectures week 39 added (see TEACHING). No times/rooms changed in schedule.
      • Oct 1: Exercise 3 (IND2) online
      • Oct 3: Update schedule see (see text under TEACHING)!
      • Oct 8: Exercie 2 (part of IND1) corrected (questions regarding Q1-Q3 directed to Anna, Q4-Q6 to Axel). PE1 is corrected, but we are awaiting revisions from some students before upload to course page.
      • Oct 8: Exercise 4 (IND2) online
      • Oct 8: minor correction of typo in Exercise 4 (11:47)

      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!

    • Exercises (IND)

      Here, all exercises and assignments for the individual assignments are listed. Upload latest 23:59pm of the respective date.

    • Practical Exercises

      Here all practical exercises and assignments are listed. Upload latest 23:59pm of the respective date.

    • Chat

      Markerad