Course Analysis for DD2445 Complexity Theory, Autumn 2015Course 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. The general opinion among the students on the course was that this was a very rewarding 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, 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 worked very well (and some student found worked all too well, in that it increased coverage of the material they had to learn). Based on the conclusions from last time the course was given in 2013, there were some important changes:
The assessment by the instructor is that all of these changes had a clearly positive influence.
StudentsThe first lecture was attended by 24 students. 24 students handed in solutions to the first problem set (which mostly tested knowledge of prerequisites for the course), out of which 23 passed the problem set. There were 13 replies handed in to the course opinion poll at the end of the sixth lecture and 10 replies to the opinion poll at the end of the tenth lecture. This seems representative of how many students were attending the lectures on average. 14 MSc students passed the course. The grade distribution was 1 grades A, 5 grade B, 1 grades C, 2 grade D, and 5 grades E. A majority of the KTH students were from the MSc program in theoretical computer science TCSCM, with a few students each coming from the CS program CDATE and the mathematics program TMAKM. We also had 3 Erasmus exchange students. Also, 3 PhD students took (and passed) the research-level version of the course FDD34455. It should be said that for an advanced theoretical course like this having 14 MSc students pass has to be considered an excellent result, and this is significantly higher than the 9 students passing in 2013. At least to some extent this is probably thanks to the changes from 2013. As already mentioned, this time we had a gentler introduction during the first few lectures, and also had the lectures more spread out in time over two periods.
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/kplx15/#schedule. TeachingThe course was given in periods 1-2 in the autumn of 2015. There were 23 lectures of 2 x 45 minutes on the course, including 4 guest lectures; two each by Johan Håstad and Danupon Nanongkai 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. Ilario Bonacina, a postdoctoral researcher in the Theory Group, 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 worked very well overall, although there is still room for fine-tuning. 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. 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 the dominant source of information for the first half of the course, while the second part of the course was also based 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. Some of the guest lectures had slides that were also 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 givenThe main changes from last time the course was given in 2013 were as follows:
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 the content of the lectures was consistently rated as interesting or very interesting 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. Overall, students liked the in-class opinion polls as a way 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 (with comments like "I see no viable alternative to Piazza" ). KTH Social does not provide adequate support for mathematical typesetting, which is absolutely essential on a course like this. The main instructor has now used Piazza for four 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. Student were mostly evenly split by considering the pace of the lectures either "about right" or "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. Students were 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. It was fairly uncommon for students to prepare for upcoming lectures by reading new material. It was more common to recap old material in between lectures, but there still seems to be room for improvement here (and this would seem to be especially important for a challenging course like this with lots of conceptually hard mathematics). The problem sets were considered to be hard but rewarding. The students were given about two weeks to solve every problem set, which was found to be adequate. There was some unhappiness with the harshness of the grading of the problem sets. This was improved on later problem sets, but judging by the course evaluation we still did not get quite all the way. Students had somewhat varying opinions about the peer evaluation of problem sets and discussions of solutions on Piazza. The discussions as such were considered valuable, with comments such as: "I like the 'solution collecting' part of the peer evaluation. It has spawned some interesting comments and discussions, and given some new insights and better understanding." The rules for awarding bonus points (which were used to get the discussions going) leave room for some further fine-tuning, however. When students were complaining about the peer evaluation and discussion, the complaints sometimes reinforced the conviction that peer evaluation had indeed been very useful, as when a student wrote that the set-up was bad because it "disincentivizes partial completions. If I am aiming for C on the sets and don't want to do some problems it's hardly worth it because I'm going to have to analyze and understand all the solutions anyway, and understanding is 75% of the work in solving!" Which just seems to show that peer evaluation served to increase coverage of the course material, just as intended… 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, it was suggested that the bonus point system used to incentivize discussion on the Piazza course forum could be improved. Another suggestion worth considering is to have more problem sets but with fewer problems per pset.
Conclusions and future changesAll in all, the students who passed this course were quite happy with it, with feedback afterwards such as "[o]ne of the most interesting [courses] I have studied at KTH." 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. 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 students struggled to get an E on the course, 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 overall these changes were successful. For the next round, the following further changes could be contemplated:
As a final remark, which is valid not only for this course but for any advanced course of a mathematical nature (and which is therefore appearing in course analysis documents not for the first time), 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.
|