Masterpieces in Theoretical Computer Science (7.5 hp)
Course Overview
The course covers a small number of seminal results ("masterpieces")
in theoretical computer science. It is primarily intended for PhD
students in Computer Science but PhD students from other programs are
also welcome.
The course consists of lectures and discussion meetings on the
different results chosen (which can vary from year to year), as well
as student presentations at the end of the course.
The course is given in English.
Prerequisites
The parts of the mandatory content of the computer science Master's
program at KTH that are related to TCS. In particular, algorithms and
data structures, NP-completeness, and basic mathematical maturity.
Learning Outcomes
After passing the course, the student should be able to:
- Read and follow research papers in different areas of
theoretical computer science.
- Discuss research questions in the areas covered in class.
- Explain possible generalizations and limitations of the results
discussed in class.
- Coherently present other people's research.
Examination
Pass/Fail. A passing grade is needed on each of the following items:
- Attendance: at most two discussion meetings can be missed (at most
one from any "category" of masterpieces)
- Written reports: for the discussion meeetings, the students hand in
brief written reports discussing questions they were assigned
- Active participation: students are expected to actively participate
in the discussion meetings
- Presentation: the student presentations
