Course Analysis for DD2446 Complexity Theory, Autumn 2013Course data
SummaryComputers are everywhere today—at work, in our cars, in our living rooms, and in our pockets—and have changed the world beyond our wildest imagination. Yet these marvellous devices are, at the core, amazingly simple and stupid: all they can do is to mechanically shuffle zeros and ones around. What is the true potential of such automated computational devices? And what are the limits of what can be done by mechanical calculations? Complexity theory gives these deep and fascinating philosophical questions a crisp mathematical meaning. A computational problem is any task that is in principle amenable to being solved by a computer—i.e., it can be solved by mechanical application of mathematical steps. Complexity theory focuses on classifying computational problems according to their inherent difficulty, and on relating those classes of problems to each other. The goal is to understand the power of computers but also—and above all—the limitations of what problems can be solved by them, or more broadly by any type of automated computational process. DD2446 Complexity Theory aims to give an introduction to computational complexity theory, survey some of the major research results, and present some of the open problems that are the focus of current research. While the intention is to give a fairly broad coverage, there is an intentional slight bias towards areas where the Theory Group at KTH has made significant contributions to the state of the art. The students found this to be quite a challenging course. This is intentional, but the drop-out rate this year was still far too high. The main mistake by the new main instructor, who gave such a course for the first time, was to assume that 2 x 90 minutes was enough to survey the prerequisites that students were supposed to know already before starting the course. This was clearly not sufficient. Among the roughly half of the students who passed, the opinion seems to have been that this was a very rewarding course, however. Student opinions were evaluated throughout the course in anonymous written "opinion polls" after lectures. This turned out to be very helpful, since it made it possible to follow how opinions developed during the run of the course and adjust the course organization. There were substantial changes in the organization of the course compared to last time it was given. The format of lectures was back to the standard 2 x 45 minutes format, and it is hard to see how the course could be given in a satisfactory way without this set-up. We used Piazza for teacher-student interaction, which was a very positive experience. We had peer evaluation of problem sets, which needed some initial tuning but worked very well during the latter half of the course. In view of the many changes, however, there were also some aspects of the course that did not turn out quite as well as hoped for. Some adjustments could be made already during the run of the course thanks to feed-back from the opinion polls, but there is also room for improvement when the course is given next time, in particular concerning the following aspects:
StudentsThe first lecture was attended by 24 students and the second lecture by 22 students. There were 15 replies handed in to the course opinion at the end of the third lecture, and at the fourth lecture the number of students was down to 13. The rest of the course appears to have been followed by 12 students, who handed in solutions to all 4 problem sets. 9 MSc students passed the course, out of which 2 from Stockholm University. The grade distribution was 5 grades A, 1 grade B, 0 grades C, 1 grade D, and 2 grades E. Most of the KTH students were from the MSc programs in mathematics TCSCM and TMTHM. The course only attracted one student from the CS program CDATE, and this student failed. No PhD students took the course (but some listened to some of the lectures). It should be said that for an advanced theoretical course like this having 9 students pass is not bad, but it should be possible to raise this figure. In 2011, the course had 18 registered students, out of which 14 passed. In 2010, there were 20 registered students out of which 13 passed (all according to VIS). The 2010 and 2011 offerings of the course were probably significantly less demanding, simply because they had half the amount of lectures. But regardless of this, with a gentler introduction during the first few lectures, and by spreading lectures out in time, it should be possible to have more students pass the course.
Formal Learning OutcomesAfter having completed the course, the student should be able to:
Actual course contentA fairly detailed description of the course content can be found in the schedule at www.csc.kth.se/utbildning/kth/kurser/DD2446/kplx13/#schedule. TeachingThe course was given in period 1 in the autumn of 2013. There were 17 lectures of 2 x 45 minutes on the course, including 2 guest lectures by Per Austrin in the Theory Group. The students were very happy with the quality of both the regular lectures and the guest lectures. All lectures were given in English. The students were asked about the preferred language of tuition in one of the opinion polls, and although a clear majority had Swedish as their mother tongue almost all preferred having lectures in English.
ExaminationThe course examination was done by 4 problem sets. The solutions to each problem sets were then peer evaluated by randomly assigning solutions to students (with the final grading and scoring done by the instructor). Problem sets were graded A-E and the peer evaluation pass/fail (where the point was mostly to make sure that students made a reasonable effort to read and understand each other's solutions). In order to get an A, students had to score an average of A or B on the problem sets and also read up on and present a research paper. Using problem sets is the traditional way of examining advanced TCS courses. The students found the problems challenging but interesting, and seemed mostly happy with this form of examination. The use of peer evaluation was an experiment inspired by the pedagogical courses at KTH. It did not work perfectly out of the box, but after a few adjustments of the rules (based on student feed-back) the system functioned pretty well and students seemed to find it useful. The requirement to read and present a paper was introduced partly to align the examination with the learning outcomes—one purpose of the course is that students should learn enough to be able to make sense of research literature in the area—and partly to train not only written but also oral skills.
Course literatureAs has been the case for previous course offerings, the textbook for the course was Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak. This textbook seems to work reasonably well. Other possible textbooks could be Computational Complexity: A Conceptual Perspective by Oded Goldreich or Introduction to the Theory of Computation by Michael Sipser, but for now there seems to be no obvious benefit from switching to another textbook. The Arora-Barak textbook was used mostly for the first half of the course, while the second part of the course was based to a greater extent on research papers. Students also received copies of the lecturer's hand-written lecture notes for each lecture, and going by the student feed-back this seems to have been much appreciated. These lecture notes were also scanned to PDF and posted on the course webpage.
PrerequisitesIn the prerequisites on the course webpage, it said that "[t]he course is open to anyone, but the main target audience are Master's students in computer science. 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. You need to have taken DD1352 Algorithms, Data Structures, and Complexity or DD2352 Algorithms and Complexity (or the older version DD2354 Algorithms and Complexity mentioned in the Study Handbook), 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." In view of the fact that all KTH students who passed the course were from MSc programs in mathematics, the description about main target audience should be updated to reflect this.
Changes from last time the course was givenThe changes to the course compared to last time it was given were fairly substantial. The most important modification was the amount of lectures. Due to budget constraints, in the last few offerings of DD2446 the amount of lectures has been halved while the amount of material covered has been supposed to be kept at the same level. Looking at the course evaluation and course analysis from the last time the course was given, it seems clear that such a set-up simply was not working very well (not very surprisingly). This time, the format of lectures was therefore changed back to the traditional 2 x 45 minutes for a total of 17 lectures. There was no increased funding for the course, however, and so the additional time for lectures was paid by the main instructor's own research grants. Another change was that the social wiki-style forum Piazza was used for teacher-student interaction. This worked very well. An especially valuable feature of Piazza is that it has support for LaTeX formatting of math, which is almost indispensable for a course like this. We also experimented with peer evaluation of problem set solutions, and this was a positive experience.
Course evaluationThe course was evaluated by number of "course opinion polls" conducted at various intervals during the course, namely on: These opinion polls were also used to adjust the course planning as we went along.In view of the large number of opinion polls, it was decided not to ask students to also fill in a course evaluation form after the course. With hindsight, however, it would have made sense to conduct such an evaluation as well in order to get a more systematic overview of student opinion. Below follows an attempt at a summary of the course opinion polls (which can be read in their entirety by following the links above). Most students found the course quite hard, but the content of the lectures was consistently rated as interesting or very interesting in the course opinion polls. Most students referred to the course webpage on a daily or weekly basis, and everybody found the course webpages very good or fairly good. The frequent use of course opinion polls was the topic of some jokes, but overall student clearly seem to like this possibility to interact with the lecturer and affect the course planning during the course. Student feed-back on the use of Piazza was positive and students had a clear preference for this tool over KTH Social. Some quotes:
The regular lectures were well attended, and were consistently rated as very good or fairly good (except by one student who rated them as "OK/neutral"). Student were mostly evenly split by considering the pace of the lectures either "about right" or "a bit too fast," and this was the case even for the first lectures. The lecturer's opinion, however, is that the first three-four lectures clearly went too fast given the background knowledge of the students.
During the lectures, we tended to make the first lecture to be 50 minutes long and then only have a 10-minute break (instead of 45 minutes followed by a 15-minute break). The students were specifically asked in a course opinion poll what they thought about this, and they seemed to be happy with it. The problem sets were considered to be hard. The time given for the problem sets, which was one week for the first problem set, was considered to be a bit on the short side. For later problem sets up to two weeks were given, and this seemed to work better. There were complaints among the students that the number of credits for the course was too low. The main instructor believes that the students were right in this and that the amount of credits should be raised from 6 to 7.5 ECTS credits. When asked about what aspects of the course should stay the same in a future course offering, students commented that most aspects should stay the same. Regarding aspects that could be improved, in addition to increasing the number of credits it was also suggested to give the course over two periods instead of just one to give students more time to digest the material. The main instructor believes this is a very good idea and would like to try it out next time the course is given.
Conclusions and future changesAll in all, the students who passed this course were quite happy with it, but the drop-out rate during the first few lectures was too high. One central question is to what extent we could and should offer advanced, research-level courses at KTH CSC and if the school is willing to pay what such courses cost. On the one hand, if we want MSc students to come into contact with research, which seems to be the officially stated goal, then that should be a strong argument for giving this kind of courses. On the other hand, a serious problem is that in the system of accounting for courses used at KTH CSC, courses have to attract 25-30 students before they are considered to "break even." For an advanced theoretical course, having such a number of students is simply not realistic. Even at major North American universities with sizeable TCS groups, having 10-15 students attending and passing an advanced TCS course is a very good number. The main instructor believes that the following changes should be made the next time this course is offered.
As a final remark, which is valid not only for this course but for any advanced course of a mathematical nature, it should be stressed again that course funding is a big challenge. This time, half of the course was paid for by the instructor's own research grants. It is not clear that this is a sustainable, long-term model of funding. This seems unfortunate, since one explicit goal of our education of MSc students is to get more connections to research in their courses, and a course like this provides exactly such connections.
|