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.
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
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.