DD2445/FDD3445 Complexity Theory Autumn 2017: Administrative InformationFollow these shortcut links to go directly to information about instructors, prerequisites, learning outcomes, examination and problem sets in general (with a description of the grading and peer evaluation process). Go to the main course webpage to find course news, short overview of course, schedule, course material, and list of problem sets.
InstructorsThe main instructor on the course was Jakob Nordström, who was responsible for all aspects of the course. Sagnik Mukhopadhyay was co-instructor and was among other things grading problem sets and giving lectures when the main instructor was travelling. We used 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). Office hours are by appointment only—send an e-mail to agree about a time to meet. 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).
PrerequisitesThe course is open to anyone, but the main target audience are Master's and PhD students in computer science and mathematics. The course is also suitable for PhD students in mathematics or computer science who have not previously taken a dedicated course on computational complexity theory. 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 are given in English. Although the formal prerequisites are quite limited, it should be noted that this is a somewhat demanding course. (But hopefully even more fun!) Before the Course StartsThere 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 instructor if you have questions).
RegistrationYou will need to formally register for the course in order for the instructor to be able to report your results. 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.
Students with DisabilitiesIf 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 OutcomesAfter having completed the course, the student should be able to:
Examination
Problem Sets and Peer EvaluationTo pass the course, students will be required to solve and hand in solutions to four 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.
Grading CriteriaThe grades for Master's students taking DD2445 are determined according to the following principles:
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 StudentsIf you are a PhD student, you can take this course as a research-level doctoral course with course code FDD3445. 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 and peer evaluation, 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
When you are working on the problem sets, discussions of ideas in groups of two are allowed—and indeed, encouraged—but you should always produce your solutions completely on your own, from start to finish, and you should understand all aspects of them fully. It is not allowed to write down draft solutions together and then just add the finishing touches individually. You should also clearly acknowledge any collaboration. For each problem set, state at the beginning if you have been collaborating with someone and if so with whom. Note that collaboration is on a per-problem-set basis—you should not talk about different problems on the same problem set with different people. 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. (This does happen from time to time, unfortunately, as tends to be the case in advanced courses like this, so please do not be afraid to ask if something looks strange.) But when you alert the instructors about potential issues, please make sure to post private messages on Piazza, 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 then 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 and Peer Evaluation ProcessThe 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 SetStudents 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 SolutionsAfter 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 EvaluationSimultaneously, 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:
Please make sure to leave the solutions together with the evaluation comments in the DD2445 mailbox at the CSC service centre at Osquars backe 2, 4th floor. Or, if you leave the problem set solutions in the mailbox outside, mark clearly that the papers should be put in the DD2445 mailbox and nowhere else. If you have no possiblity to submit papers in person, you can also scan a PDF copy of the peer-evaluated solutions and submit by e-mail.
Step 4: Final GradingFinally, 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-upThere are a number of reasons why this approach will be used. It is intended to:
Problem sets with peer evaluation have been used a number of years now for the courses DD2445 Complexity Theory and DD2442 Seminars on Theoretical Computer Science, and so far this approach has been quite successful. However we are continuously evaluating how this works, and the set-up might be modified during the course based on the conclusions from such evaluations. If you have any views or comments regarding the peer evaluation, please feel free to contact the main instructor on Piazza or by e-mail.
|