Course Analysis for DD2445 Complexity Theory, Autumn 2017Course 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. DD2445 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, and we do expect to lose a few students who are simply too far from knowing the prerequisites for the course, but still it would be desirable to decrease the drop-out rate. Compared to previous years, we had slightly fewer MSc students passing the course than usual, but it also seemed to be the case that the students were weaker than has usually been the case. The general opinion among the students on the course was nevertheless that this was a very rewarding course. As usual for this course, student opinions were evaluated throughout the course in anonymous written "opinion polls" after lectures as well as through a traditional course evaluation. The in-class opinion polls were quite helpful for the main instructor, since they made it possible to follow how opinions developed during the run of the course and adjust the course organization. As last time the course was given, we used Piazza for teacher-student interaction, which was again a very positive experience. We had peer evaluation of problem sets, which the instructor found to be working very well, and which the students were slightly happier with than usual (so maybe we managed to tweak the set-up in some nice way this year — there are always some minor adjustments). Of course, there is also the problem that some students find that the peer evaluation works all too well, in that it increases coverage of the material they have to learn, but this might be a disadvantage that we will have to live with. Last time the course was given during the autumn of 2015 there were a number of substantial modifications. These influenced the course in a clearly positive way, and the course evaluation revealed no need for further drastic changes. One area for improvement that was identified, however, was that when a postdoctoral researcher is helping out with grading of problem sets, it is essential that the main instructor communicates clearly how the grading should be done and what is the expected level of student solutions. This is especially so since postdoctoral researchers in the Theory Group are international and so less familiar with the environment at KTH. The main instructor paid more attention to this aspect during the autumn of 2017, and the assessment is that this had a positive effect. One other change was in how the lectures were organized. During the first half of the course we tended to deal with some new selection of material every lecture, with the material being finished at the end of the lecture so that next lecture could start on something new. Towards the end of the course we instead had more of a set-up with "overlapping" lectures, where the second half of a lecture would introduce some new material, which was then finished during the first half of the next lecture. The intention was that this would give the students a better chance to digest the material by hearing it twice. Somewhat disappointingly, however, the students did not seem to like this too much (but it is not clear whether this improved their learning or not).
StudentsThe first lecture was attended by 15 students, which was clearly less than in 2015 (24 students). This might partly have been due to the fact that there was confusion about the schedule. Advanced courses like DD2445 never get official lecture rooms scheduled, and instead the lectures are given in the seminar rooms at Lindstedtsvägen 3/5. For unknown reasons, however, this year the official KTH schedule had added lecture rooms elsewhere on campus, which, needless to say, was quite confusing both for the students and the instructor. 15 students handed in solutions to the first problem set (which mostly tested knowledge of prerequisites for the course), out of which 13 passed the problem set. Both of these numbers are only slightly above half of what was the case in 2015. There were 12 replies handed in to the course opinion poll at the end of the fourth lecture and 10 replies to the opinion poll at the end of the ninth lecture. This seems representative of how many students were attending the lectures on average, although some lectures had markedly fewer students attending. 8 MSc students passed the course. The grade distribution was 1 grade A, 4 grades B, 2 grades C, 1 grade D, and 0 grades E. Also, 3 PhD students took the research-level version of the course FDD34455. Very unusually, 1 of these students failed. It should be said that for an advanced theoretical course like this having 8 MSc students pass is not a bad result. It is a bit of a disappointment, though, considering that 14 MSc students passed in 2015. It is roughly in line with the 9 MSc students passing in 2013. Based on the comparisons with 2013 and 2015, it should be said that the students were clearly weaker this year. However, it is an important question whether the course organization can be modified to support the students better, and this will be discussed further below.
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/DD2445/kplx17/#schedule. TeachingThe course was given in periods 1-2 in the autumn of 2017. There were 23 lectures of 2 x 45 minutes on the course, including 5 guest lectures by Sagnik Mukhopadhyay, a postdoctoral researcher in the TCS Group. The students were very happy with the quality of both the regular lectures and the guest lectures. All lectures were given in English, which is necessary for exchange students and PhD students to be able to follow. As usual, the students were asked about the preferred language of tuition in one of the in-class opinion polls. Although a clear majority have Swedish as their mother tongue, almost all preferred having lectures in English. In addition to giving guest lectures, Sagnik Mukhopadhyay also assisted with grading of problem sets.
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 instructors). 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. Peer evaluation has now been used by the instructor on a number of advanced courses in theoretical computer science (inspired by the pedagogical courses at KTH), and this set-up works very well overall. The requirement to read and present a paper is there 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, though is is a problem that it contains quite a lot of typos. 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 and lecture notes from the instructor (partly to address errors in the exposition in the textbook). Students also received copies of the lecturer's hand-written lecture notes for each lecture, and going by the student feedback 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 says 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. 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." According to student feedback the prerequisites were clearly worded and accurate.
Changes from last time the course was givenAs mentioned above, since the course changed somewhat significantly from 2013 to 2015, this time we tried to keep most things stable. The main instructor paid more attention this time around to coordinating with the postdoc assisting with the grading of the problem sets. It seems that the grading worked better this year than in 2015 going by the responses in the in-class opinion polls.
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 some extent to adjust the course planning as we went along. After the course we had a more traditional course evaluation as well in order to get a more systematic overview of student opinions. Below follows an attempt at a summary of the course opinion polls and the course evaluation (which can be read in their entirety by following the links above). Most students found the course quite hard, but also very interesting. The content and quality of the lectures were consistently rated very positively in the course opinion polls and also in the course evaluation. Most students referred to the course webpage on a daily or weekly basis, and students found the course webpages very good or fairly good. A change from last time was the the course webpage was (essentially) split in two, with more "dynamic" material on one page (course news, schedule, course material, and list of problem sets) and more "static" material on another (information about instructors, prerequisites, learning outcomes, examination, grading, and peer evaluation process). This year, students were neutral as to the value of the in-class opinion polls. Usually, the view this positively as an opportunity to interact with the lecturer and affect the course planning during the course. Student feedback on the use of Piazza was positive and students had a clear preference for this tool over the standard tools offered by KTH. For a course like this, it is absolutely crucial to have adequate support for mathematical typesetting in the discussion forum. The main instructor has now used Piazza for many courses at KTH, and intends to stick with this tool also in the future, at least for courses with a significant mathematical content. The regular lectures were well attended, and overall tended to be rated as very good or fairly good. The pace of the lectures was considered to be "about right" (which might be seen as an improvement from last time, when the student were mostly evenly split between "about right" and "a bit too fast"). A much appreciated feature was that students received hand-outs of the hand-written lecture notes, so that they could focus on following the lecture. (Except that you can never make everybody happy — there were also questions why the lecture notes could not be typed up in LaTeX…) Students were a bit split on whether spending 3 lectures on prerequisites was a good idea or not, but from an instructor point of view it was absolutely clear that this was needed. During the lectures, we tended to make the first half 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, as well as in the course evaluation afterwards, and they seemed to be happy with it. Less than half of the students prepared for upcoming lectures by reading new material, or went over old material in between lectures. This presents a similar picture to 2015. This leaves lots of room for improvement! (And this would seem to be especially important for a challenging course like this with lots of conceptually hard mathematics.) As mentioned above, towards the end of the course we experimented with having "overlapping" lectures, where the second half of a lecture would introduce some new material, which was then finished during the first half of the next lecture. The purpose of this was to enchance student learning by exposing students to the material twice. According to the course evaluation the students were mostly negative as to the value of this — the main instructor is not so sure. More data points are needed on this. The problem sets were considered to be hard, but adequate and rewarding. The students were given about two weeks to solve every problem set, which was found to be adequate. In 2015 there was some unhappiness with the harshness of the grading of the problem sets. This seems to have improved significantly this year. One proposal that the students were asked to assess in the course evaluation was to have the same total number of problems but distribute them over twice as many problem sets, in order to make students work continuously on the course material but also to distribute the workload more evenly. The instructor can see pros and cons with this. The students were clearly positive. Compared to previous years, students were unusually happy with the peer evaluation of problem sets and discussions of solutions on Piazza. As always, the rules for awarding bonus points (which were used to get the discussions going) stimulate some discussions, but from the instructor's point of view having such rules does seem to be essential to stimulate lively discussions. The students were asked whether they thought some or all of the peer review assignments should be changed to mandatory sessions with oral presentation of solutions, where participation would be mandatory and each student would have to sign up for being ready to present solutions to at least a certain number of problems (to train not only written but also oral presentation skills). The responses were mixed, and the instructor is not completely convinced of the merits of the idea, mostly because it is not clear whether the increased workload on the instructor side would be worth the pay-off. 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, one suggestion was to have smaller but more frequent problem sets. Another suggestion was that the handwritten notes by the lecturer should instead be typed up on a computer.
Conclusions and future changesAll in all, the students who passed this course were quite happy with it, with feedback such as:
As has been mentioned in other course analyses, one central question is to what extent we could and should offer advanced, research-level courses at KTH and if the (now not CSC but EECS) 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, 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. This does not mean that we should not try to attract more students—indeed, it is worth thinking about how to try to do this. Another question is whether the drop-out rate during the first lectures can be decreased. Realistically, however, we can see that a significant number of the students who passed the course really struggled to do so, and so it does not seem unlikely that many of the students who dropped out might simply have lacked the required background knowledge, and might have realized this once they started working on the first problem set (which was when the drop out happened, as tends to be the case). As described above, several aspects of the course were changed for the 2015 version as compared to last time the course was given in 2013, and these changes were kept in 2017. Further changes were made, but no really substantial ones. The following challenges, listed already in 2015, remain:
|