Skip to main content

DD2542 Seminars on Theoretical Computer Science, Algorithms and Complexity 7.5 credits

The course 2024 discusses the approximability of NP-hard optimization problems.  This is the same topic as 2020 but some adjustments will be made, partly based on discussions with the participants.

If an optimization problem is NP-hard then, based on the assumption that P is not equal to NP, it cannot be solved optimally in polynomial time.   This motivates the study of efficient approximation algorithms that are guaranteed to find a solution within a given factor of optimal.  The course will discuss two types of results.

Algorithmic results where we design an algorithm for a given problem and shows that it has desired properties.  In particular that it runs in polynomial time and and finds a solution within a certain factor of optimal.  General methods for finding such algorithms are based on Linear Programming or Semi-Definite Programming. Vi will study basic computational problems such as Max-Cut, maximal independent set and constraint satisfaction problems.

We will also study hardness results.  We prove that for some problems it remains NP-hard even to find an approximate solution.  Many such results are based on the PCP-theorem that states that any problem in NP admits a short proof that can be verified by a probabilistic verifier that only reads a constant number of bits.  We will study the proof of the PCP-theorem and give several examples of how to use it to prove inapproximability results.

Choose semester and course offering

Choose semester and course offering to see current information and more about the course, such as course syllabus, study period, and application information.

Application

For course offering

Autumn 2024 semteo24 programme students

Application code

50547

Headings with content from the Course syllabus DD2542 (Autumn 2021–) are denoted with an asterisk ( )

Content and learning outcomes

Course contents

The course content may vary from course offering to course offering. Examples on topics are approximation algorithms, data mining, cryptography, parallel computations and probabilistic algorithms.

Intended learning outcomes

After passing the course, the student shall be able to

  • discuss advanced concepts within the area of the course
  • attack problems within the area of the course actively, both through own work and through search of relevant information
  • assimilate and present the essential contents of scientific articles within the area of the course.

Literature and preparations

Specific prerequisites

Completed course in algorithms and complexity equivalent to DD2350/DD2352.

Active participation in a course offering where the final examination is not yet reported in LADOK is considered equivalent to completion of the course.

Registering for a course is counted as active participation. The term 'final examination' encompasses both the regular examination and the first re-examination.

Recommended prerequisites

The course is open to anyone, but the main target audience are advanced Master's students and doctoral students in computer science and mathematics. 

Although the formal prerequisites are quite limited, course participants will need mathematical maturity and a willingness to learn new stuff. It should be noted that this will be a somewhat demanding course. (But hopefully even more fun!)

Equipment

No information inserted

Literature

No information inserted

Examination and completion

If the course is discontinued, students may request to be examined during the following two academic years.

Grading scale

A, B, C, D, E, FX, F

Examination

  • ÖVN1 - Exercises, 7.5 credits, grading scale: A, B, C, D, E, FX, F

Based on recommendation from KTH’s coordinator for disabilities, the examiner will decide how to adapt an examination for students with documented disability.

The examiner may apply another examination format when re-examining individual students.

Opportunity to complete the requirements via supplementary examination

No information inserted

Opportunity to raise an approved grade via renewed examination

No information inserted

Examiner

Ethical approach

  • All members of a group are responsible for the group's work.
  • In any assessment, every student shall honestly disclose any help received and sources used.
  • In an oral assessment, every student shall be able to present and answer questions about the entire assignment and solution.

Further information

Course room in Canvas

Registered students find further information about the implementation of the course in the course room in Canvas. A link to the course room can be found under the tab Studies in the Personal menu at the start of the course.

Offered by

Main field of study

Computer Science and Engineering

Education cycle

Second cycle

Add-on studies

No information inserted

Contact

Johan Håstad (johanh@kth.se)

Supplementary information

This course is usually given every second year (even years) in period 1. The language of tuition is English.

The course has replaced DD2442.