School of
Electrical Engineering
and Computer Science

DD2442/DD3343 Seminars on Theoretical Computer Science Autumn 2016: Administrative Information

Follow these shortcut links to go directly to information about instructors, prerequisites, registration, learning outcomes, examination, problem sets in general (with a description of the peer evaluation process), and scribing of lectures.

Go to the main course webpage to find course news, short overview of course, schedule, course material (with scribe notes), list of problem sets, or links to other courses.


The main instructor on the course is Jakob Nordström, who is responsible for all aspects of the course.

Ilario Bonacina is co-instructor and will also be giving lectures, help with grading of problem sets, et cetera.

We have had guest lectures by Johan Håstad and Marc Vinyals from the Theory Group at KTH, as well as by Pavel Pudlák from the Institute of Mathematics of the Czech Academy of Sciences.

We are using Piazza for teacher-student interaction on the course. Thus, questions should not be e-mailed to the instructors, but instead posted on Piazza (where you can send private notes if needed, and also ask questions anonymously).

All course participants need to be signed up at Piazza to receive announcements related to the course (but note that this does not replace the official course registration at KTH).


The course is open to anyone, but the main target audience are Master's and PhD students in computer science and mathematics. As to formal requirements, you need to have taken DD1352 Algorithms, Data Structures, and Complexity or DD2352 Algorithms and Complexity, or corresponding courses at other universities, and should feel comfortable with that material. There are no additional formal prerequisites on top of what is stated in the Study Handbook, but you will need mathematical maturity and a willingness to learn new stuff.

All lectures will be given in English.

Although the formal prerequisites are very limited, it should be noted that this is a somewhat demanding course. (But hopefully even more fun!)


You will need to formally register for the course in order for the instructors to be able to report your results. Students should register as soon as possible using the course web (earlier called my pages). Different categories of students take this course and might face different administrative problems. Please make sure that you get officially registered for the course as appropriate for your study program.

Before the Course Starts

There is no need to register beforehand in order to start attending the course—you can just show up at the first lecture (or send an e-mail to the instructors if you have questions).

Students with Disabilities

If you have a disability, you may receive support from Funka.

Please do let the main instructor know regarding any special needs that you may have. Funka does not automatically inform the teachers.

Formal Learning Outcomes

After having completed the course, the student should be able to:

  • Define and motivate basic concepts covered by the course and explain how these concepts are related to one another.
  • Describe some important research results in the area covered by the course.
  • Use tools and techniques as covered by the course to prove basic theorems and independently solve problems amenable to these methods.
  • Present theoretical computer science arguments with mathematical stringency orally and in writing.


Problem Sets and Peer Evaluation

To pass the course, students will be required to solve and hand in solutions to three problem sets. The scores on the problem sets are what will mainly determine the final grades on the course (except as explained below).

For each each problem set, each student will also have to evaluate the solutions of a fellow student (but not assign grades), who will be randomly chosen. This part of the examination will only be pass/fail as discussed in the description of the grading process below.

The KTH CSC code of honour applies to all aspects of this course including the problem sets. There are also some additional rules specific to (the problem sets of) this course. These rules are available below on this webpage and are stated on each problem set.

Scribing of Lecture Notes

Students are also required to produce scribe notes for two lectures in LaTeX (and the number and size of the problem sets has been adjusted to make sure the overall workload will be reasonable). See the scribing instructions for more details.

Grading Criteria

The grades for Master's students taking DD2442 are determined according to the following principles:

  • To pass the course, you need a pass (E) on all problem sets. The score needed for an E or higher grades will be stated on each individual problem set. For each pset, you also need to evaluate the solutions of a fellow student.
  • You also need to scribe lectures, but this part of the course is only graded pass/fail.
  • In principle, the final grade will be the arithmetic mean of the grades for all the problem sets That is, think of A-E as {5,4,3,2,1}, sum up, and divide by the number of psets.
  • If this mean is not integral, later psets will affect the rounding more than earlier psets. Also, if you have done a good job of evaluating pset solutions by fellow students, and/or of scribing lectures, this will affect the rounding upwards.
  • It is very possible that there will be some corner cases that this set of rules (or any set of rules of reasonable length), cannot exactly capture. In such cases, we will strive to be generous rather than stingy.

Note that solutions to the problem sets should be handed in strictly by the deadlines. Being able to work towards a deadline and deliver the best possible result within a given time frame (rather than a 100% polished product that arrives too late) is an important skill, and is something that you will have the opportunity to practise during the course. Having said that, exceptional circumstances, such as severe illness, can be accepted as an excuse for late problem set solutions. It should be emphasized, however, that lack of time due to work outside the university or due to many parallel courses is not considered as a legitimate reason for handing in problem set solutions late.

PhD Students

If you are a PhD student, you can take this course as a research-level doctoral course with course code DD3343. The requirements are slightly tougher and the grading is only pass/fail, but the course counts fully towards the course credit requirements in the PhD program.

For PhD students taking the research-level course, in addition to fulfilling the above requirements the average grade on the problem sets should be at least C. PhD students should also give an oral presentation of a research article in proof complexity. PhD students also have the option to take the Master's level course.

Unfinished Course?

As far as we are aware, there are no students from previous years having unfinished parts of this course, and we do not expect this to be a problem this year either. Students who are motivated and strong enough to take this course also tend to finish it. Since there is no exam on the course but only problem sets, peer evaluation, and scribing, any students who do not complete the course requirements in time will have to be dealt with on a case-by-case basis. Any bonus points collected during the course (as explained below) will be voided once the course has ended.

Information About Problem Sets

General Information

Solutions to the problems sets should be submitted as PDF files by e-mail to jakobn at kth dot se. Please use the subject line Problem set <N>: <your name> and name the PDF file PS<N>_<YourName>.pdf with any national characters converted to standard ASCII (so the solutions to the second problem set by the main instructor would have the file name PS2_JakobNordstrom.pdf, for instance). Solutions should be typeset in some math-aware system (read: LaTeX or such like). Please try to be precise and to the point in your solutions and refrain from vague statements. Some of the problems in the problem sets are meant to be quite challenging and you are not necessarily expected to solve all of them.

When you are working on the problem sets, discussions of ideas in groups of two are allowed, but you should always write down your own solution individually and understand all aspects of it fully. You should also acknowledge any collaboration. For each problem set, state at the beginning if you have been collaborating and with whom.

You can (and should) ask the instructors if anything about the problem sets is unclear, or if there seem to be typos or outright errors in the problem statements. Make sure to post private messages to the instructors on Piazza in that case, so that your questions do not accidentally give away unintended information about the problems to the other students. If there is some issue needing clarification regarding some problem, the instructors will make a public post on Piazza.

Some of the problems are "classic" and hence it might be easy to find solutions on the Internet, in textbooks or in research papers. It is not allowed to use such material in any way unless explicitly stated otherwise. You can, however, use in your solutions anything said during the lectures on in the lecture notes, unless you are specifically asked to show something that we claimed without proof in class. It is hard to pin down 100% formal rules on what all this means—when in doubt, ask the instructors.

Grading Process

The grading process will involve some peer evaluation (and hopefully tons of interaction among the students). All final grading will be done by the instructors, however. Here is how it is intended to work.

Step 1: Work on the Problem Set

Students solve the problem set, on their own or collaborating in pairs, and write down their own solutions and submit as a PDF file by e-mail before the deadline. During this phase no discussion of problem set solutions is allowed other than with the collaborating partner (but sending a private message on Piazza to the instructors asking for clarifications is of course OK, and is even highly encouraged).

Step 2: Discussion of Solutions

After the deadline, the instructors distribute the problem set solutions randomly to the students as PDF files by e-mail. All students will have a day or two to go over the received problem set solutions, compare with their own solutions, and try to figure out what might be good or bad approaches to solving the various problems on the problem set.

When a day or two has passed, the instructors give the start signal for discussions of solutions to the problems on Piazza. During this phase all students on the course should work together to find solutions (possibly many different ones) to all problems on the problem set.

During the discussions a maximum of collaboration is allowed and encouraged. There is no incentive not to collaborate here since nothing that happens after this point can lower the grade of any student. Instead, there will be bonus points for writing down correct solutions on Piazza, as well as for helping to improve on not fully correct or complete solutions. Note that a student need not have solved the problem him- or herself in order to contribute a solution on Piazza. It is sufficient to have understood and be able to present a solution. (However, just quoting from the received set of solutions verbatim is not encouraged—the bonus points are meant to award understanding, not copying skills.)

The instructors will not take part too actively in the exchange of comments, but will try to nudge the discussions in the right direction if need be.

Step 3: Peer Evaluation

Simultaneously, and using material learned during the discussion phase, each student should evaluate all the solutions in the set of received problem set solutions and write down comments on a print-out. Even if the student solved the problem set in cooperation with another student, the peer evaluation should be performed individually, not cooperating in pairs.

Here is how the solutions should be evaluated:

  • Each problem solved should be clearly marked as "correct", "incorrect", or "unknown".
  • For a "correct" solution, the key steps in the solution should be highlighted.
  • For an "incorrect" solution, the error(s) in the solution should be pointed out together with an explanation what the mistake is.
  • If a solution is truly unintelligible, it can be marked as "unknown" and a comment should be provided explaining where the evaluating student gets lost and why. Note, however, that hard-to-understand solutions can be discussed on Piazza (while giving a suitable amount of details in order to maintain the anonymity of both the student being evaluated and the student evaluating), and so this "unknown" option is expected to be very rare.
  • General comments discussing possible strong and weak points with the solution are encouraged—please use the opportunity to provide constructive feed-back to a fellow student.
  • At all times, please avoid harsh language and excessive criticism. Be polite and try to find not only negative but also positive aspects of the solutions.
  • All comments should be clearly legible. Shorter comments should be provided directly on the print-out. Longer comments can be provided on separate sheets of paper where it is clearly marked which comments pertain to which problem solution and where.

The solutions together with the evaluation comments should be should be put in the main lecturer's mailbox on the 4th floor at Osquars backe 2 or handed to the lecturer before beginning of class on the day of the peer evaluation deadline.

Step 4: Final Grading

Finally, the instructors will grade all problem set solutions and assign scores, and will at the same time evaluate the evaluations. Each student will receive both the instructor grading comments and the peer evaluation copy.

The problem set will be regarded as a pass if it reaches the threshold for E as specified in the problem set.

The problem set evaluation will be regarded as a pass if at least 50% of the solutions marked as "correct" or "incorrect" are properly identified as such (with relevant explanations), and if no solution is marked "unknown" unless there is a convincing explanation as to why this solution was not possible to understand. In particular, the instructors may look at the discussions at Piazza to check if the student has made a good faith effort to get help to figure out what is going on in the solution.

Motivation for this Set-up

There are a number of reasons why this approach will be used. It is intended to:

  • Increase the coverage of the material, so that all students will work on (essentially) all problems regardless of whether they managed to solve them themselves or not.
  • Increase in-depth learning, in that students will have to really understand the problems in order to assess someone else's solutions.
  • Encourage students to write clearly and intelligibly, so that the text can be understood by their peers.
  • Help students develop the skills to read and understand mathematical arguments as presented by others.
  • Increase the amount of feed-back provided to each student, in that more individualized comments will be provided than can possibly be done by a single instructor marking all solutions.
  • Help the students internalize the course requirements, in that they will gain a greater understanding of what is an appropriate level of detail in the solutions, what is a suitable level of mathematical rigour in the arguments, what makes solutions easy or hard to read, and how this all affects the grading of the solutions.
As a side effect, this process might also help in the final grading of the problem set solutions by the instructors, although based on previous experience this effect is fairly limited.

This new approach will be thoroughly evaluated during (and certainly after) the course, and might be modified based on the conclusions from such evaluations. One of the reasons we are doing this is that a similar approach has been used for the courses DD2445 Complexity Theory and DD2442 Seminars on Theoretical Computer Science before, and has been quite successful. If you have any views or comments regarding this, please feel free to contact the main instructor on Piazza or by e-mail.

Instructions for Scribing

An important part of the course (and part of the examination) will be to produce high-quality scribe notes from the lectures (since much of this material does not even exist in very reader-friendly format, and some of it does not exist at all). For the scribe notes we will use LaTeX (see, e.g.,, which is the default "word processing" software for math and theoretical computer science.

Files for Scribe Notes

You can submit your scribe notes either via e-mail or by using the SVN server There is a template LaTeX file (together with some auxiliary files) for scribing, and this file also contains some instructions and tips that will hopefully be useful. How to obtain the files depends on how you will submit your scribe notes.

The preferred way is to use SVN, in which case you first need to sign up for an account (just go to the SVN server and click "log in"), then send a message to the instructors to get access permission to, and finally check out this repository (e.g., by following the instructions how to work with SVN). If you use SVN, then all the files you need will automatically be in the right place, and you will also have access to all lecture notes and will be able to see how other scribes wrote up the material in their lectures and to contribute bug fixes and improvements to the notes from all the lectures.

If you prefer to submit your scribe notes by e-mail you need to download the template file ScribeNotesLecXX.tex (last updated on October 10; placed in a zip file to avoid any encoding problems in transit) together with some auxiliary files (last updated on October 10). In order for things to work, you need to place the latter files in a sibling directory of the former (i.e., standing in the directory containing the scribe note template file, the path to the auxiliary files should be ../Auxiliary). If you compile ScribeNotesLecXX.tex by doing pdflatex ScribeNotesLecXX followed by bibtex ScribeNotesLecXX a few times until you get no warning messages, then the result should be something like this PDF file. Then replace XX by the two-digit number of the lecture you are scribing. Please make sure not to modify any files in the Auxiliary directory, but only the file ScribeNotesLec<XX>.tex for the lecture you are contributing to.

Scribing Process

The scribing is intended to be a three-stage process:

  1. For each lecture, we will have first one student who scribes the lecture based on what is said in class and on the handwritten lecture notes. The scribed notes are committed to the SVN repository or sent to the instructors by e-mail.
  2. After this, a second student goes over the scribed notes carefully and proof-reads, points out passages which are perhaps hard to understand, and proposes improvements in general. This can be done by editing the text in the file ScribeNotesLecXX.tex directly (where XX will now be the two-digit number of the lecture) or by adding "meta-comments" using the command \reviewercomment (see the file ScribeNotesLecXX.tex for an example of how this is done). The revised notes are then committed to the SVN repository or sent to the instructors by e-mail.
  3. Finally, the instructors and assistants review the notes, after which they are posted online.
Depending on the quality of the notes, there might be one or a couple of iterations in the above scheme, but we are aiming (and hoping) for this number to be as close to zero as is possible.

We will need to the exact set-up in class—especially since scribe notes production has so far been slower than intended—but here is a proposed time schedule:

  • For Monday lectures the scribed lecture notes should be produced by Friday noon and the peer review should be completed by Tuesday noon the next week.
  • For Wednesday lectures the scribed lecture notes should be produced by Monday noon the next week and the peer review should be completed by Thursday noon the next week.
Comments on the suggestion above are welcome.

There is a sign-up sheet where you can register for scribing and reviewing. All students will have to scribe two lectures each and review two (other) lectures each.

Copyright © Published by: Jakob Nordström <jakobn~at-sign~kth~dot~se>
Updated 2017-06-01