bild
School of
Electrical Engineering
and Computer Science

Course Analysis for DD2442 Seminars on Theoretical Computer Science, Autumn 2016

Course data

Course DD2442 Seminars on Theoretical Computer Science
ECTS credits 7.5 ECTS credits
Semester/period Autumn 2016, periods 1-2
Examination Problem sets, peer evaluation, scribing of lecture notes
Lectures 24 lectures of 2 x 45 minutes (including 6 guest lectures)
Course literature research papers; hand-written lecture notes; slides for one lecture
# students attending first lecture 18
# students completing some course requirement 11 students handed in solutions to the first problem set (out of which 8 passed the problem set)
# students passed 3 MSc students passed the course (grade A: 1, grade B: 0, grade C: 1, grade D: 1, grade E: 0); 2 PhD students passed the research-level version DD3343
Main instructor Jakob Nordström
Other instructors Ilario Bonacina served as co-instructor, giving lectures and grading the problem sets. We 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.

Summary

DD2442 is an advanced MSc-level course in theoretical computer science with varying content which is given every second year (alternating with DD2445 Complexity Theory). There is also a PhD-level course code DD3343 for PhD students who want to take this course as part of their course credit requirements in the PhD program. The general idea of the course is to cover some area of active research in theoretical computer science. Lectures are often based on research or survey papers in that area, and/or on lecture notes from similar advanced courses at other universities, since the material might be so recent that there are no good textbooks yet. In the autumn of 2016 the topic of the seminar course was proof complexity.

Very simply put, proof complexity can be said to be the study of how to provide a short and efficiently verifiable certificate of the fact that a given propositional logic formula (typically in conjunctive normal form, or CNF) is unsatisfiable. Note that for satisfiable formulas there are very succinct certificates—just list a satisfying assignment—but for unsatisfiable formulas it is not quite clear what to do. It is widely believed that it is not possible in general to give short certificates for unsatisfiable formulas, which if proven would imply PNP. One important research direction in proof complexity is to approach this distant goal by establishing lower bounds for stronger and stronger proof systems. Another reason to study proof complexity is that any algorithm for the satisfiability problem (a so-called SAT solver) uses some method of reasoning for deciding whether a formula is satisfiable or unsatisfiable. Studying the proof systems corresponding to these methods of reasoning and proving upper and lower bounds for them tells us something about the potential and limitations of such SAT solvers.

This course had a bias towards the first reason above, and therefore focused on the strongest proof systems for which it is currently known how to prove lower bounds. After a brief introduction to proof complexity, the lectures surveyed some recent research in the area and presented some of the many problems that still remain open. While the intention was to give a fairly broad coverage, there was intentionally a slight bias towards topics which are of particular interest in the context of the research conducted at the Theory Group at KTH, which has one of the largest research groups in proof complexity in the world today.

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.

One other reason for so few students passing the course, however, is a serious problem that arose already in 2014 and unfortunately was not possible to avoid in 2016 either. The problem is that the KTH system somehow does not seem well adapted to deal with courses that are given only every second year. Official information about the course in the KTH schedule was again wrong (claiming, for instance, that the course was given only in period 1 rather than in both periods 1 and 2), which again meant that some students discovered at the start of the course that they could not accommodate the course in their personal schedules, since they had not been given correct information. We have been working on solving this problem since 2014 together with all relevant parties at KTH CSC, and it remains unclear why correct information from KTH CSC cannot be properly transmitted to KTH central administration. The failure is not for a lack of effort from the KTH CSC side.

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. 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 again was a mostly positive experience. We used problem sets for examination, including peer evaluation of solutions by students. This is a set-up which the main instructor thinks works very well, and which the students also seemed to be happy with. Another part of the examination, which is less commonly used for the advanced courses in TCS, was that students had to take turns scribing lecture notes. This is an excellent way of stimulating in-depth study and understanding, but it is also very work-intensive for the instructors.

Last time the course was given during the autumn of 2014 there were a number of substantial modifications. These influenced the course in a clearly positive way, and the course evaluation back then revealed no need for further drastic changes. Most aspects of the course organization were therefore kept the same in 2016. However, it could also be said that the seminar course always changes quite dramatically from one edition to the next, in the sense that it is always covering a completely new topic.

Students

The first lecture was attended by 18 students. This was higher than the exceptionally low figure of 10 students in 2014, but still clearly lower than could and would have been expected. The assessment is that the low figures for both 2014 and 2016 were due to conflicting and incorrect information in the official KTH schedule system.

11 students handed in solutions to the first problem set, out of which 8 passed the problem set. 8 students handed in the second problem set, out of which 6 passed.

There were 12 replies handed in to the course opinion poll at the end of the 4th lecture and 8 replies to the opinion poll at the end of the 17th lecture. The second number is representative of how many students were attending the lectures on average.

3 MSc students passed the course. The grade distribution was 1 grade A, 0 grades B, 1 grades C, 1 grade D, and 0 grades E. Also, 3 PhD students took the research-level version of the course, out of which 2 passed. For comparison, in 2012 — before the problems with getting the right information into the central KTH system started — we had 10 MSc students and 4 PhD students passing. It should be said that for an advanced theoretical course like this having a double-digit number of students passing would be an excellent result. Unfortunately, both in 2014 and 2016 the number has been significantly lower.

Regardless of the administrative problems, however, it is also an important question how the course organization can be modified to support the students better, and this will be discussed further below.

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.

Actual course content

A fairly detailed description of the course content can be found in the schedule at www.csc.kth.se/DD2442/semteo16/#schedule.

Teaching

The course was given in periods 1-2 in the autumn of 2016. There were 24 lectures of 2 x 45 minutes on the course, most of which were given by Jakob Nordström or Ilario Bonacina. We had a total of 6 lectures by Johan Håstad and Marc Vinyals from the Theory Group at KTH and by Pavel Pudlák from the Institute of Mathematics of the Czech Academy of Sciences. The students were very happy with the quality of both the regular lectures by Jakob Nordström and also satisfied by the lectures by Ilario Bonacina. The material covered in the lectures was considered interesting. The pace of the lectures was mostly adequate, or sometimes a bit too fast, which is roughly what the main instructor is aiming for. Some of the PhD students found the pace a bit too slow at times, but that is natural.

The guest lecturers got slightly more mixed reviews, but the students were clearly positive to the concept of having guest lectures.

All lectures were given in English, which is necessary for exchange students and PhD students to be able to follow.

In addition to giving lectures, Ilario Bonacina also assisted with grading of problem sets.

Examination

The main part of the course examination consisted of 3 problem sets, which the students were supposed to solve individually or in pairs. 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 addition to this, each students also had to scribe two lectures (i.e., typing up proper lecture notes with nicely formatted mathematics) and review two set of notes scribed by some other student.

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.

Having students scribe lectures is something that is done much less frequently. This really stimulates in-depth learning, and also gives valuable hands-on practice in technical writing. However, it is an extremely work-intensive form of examination from the instructor point of view.

Course literature

There is no textbook covering the material taught in this course. The students received detailed hand-written lecture notes for most lectures, and also received references to relevant research papers. For the introductory lecture there were slides.

Prerequisites

In the prerequisites on the course webpage, it says that "[t]he 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."

The feedback from the students over the last few editions of the course has been consistent that this is a reasonable description.

Changes from last time the course was given

Since the Seminars on TCS course deals with a new topic every time it is given, it is a new course every time it is given. In this sense, there are lots of changes in between different editions.

In another sense, though, the general set-up with lectures, problem sets, and peer evaluation has been the same for the last few editions of the course.

Perhaps the biggest change this time around was that we had students scribe lectures. Going by the evaluations, it seems that the students learned a lot by this, but it is questionable whether it was worth the significant extra effort required by the instructors.

Course evaluation

The 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.

Since so few students passed the course, it was decided that it was not worth the effort to also have a traditional course evaluation after the course. All the questions normally asked in the evaluation had already been covered in the in-class opinion polls, and since the students filling in the final pool are (for natural reasons) mostly the students who have passed the course, the few extra answers would not have given much extra information. For larger courses, the final course evaluation can otherwise be a good opportunity to check if and how student opinions have changed during the course.

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 interesting (but also quite hard).

The content and quality of the regular lectures were consistently rated positively or very positively in the course opinion polls (with a slightly higher rating for the main instructor). The regular lectures were well attended by course participants. The pace of the lectures was considered to between "about right" and "a bit too fast", which seems reasonable for an advanced course like this. A much appreciated feature was that students received hand-outs of the hand-written lecture notes, so that they could focus on following the lectures.

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. Usually the students are happy with this, but for this course the reviews were more mixed.

The problem sets were considered to be hard, but adequate and rewarding. The students were given 2-4 weeks to solve every problem set, which was slightly longer than usual (because we also had one fewer problem set than is usual for this course).

Compared to previous years, students were a bit disappointed with the discussions of solutions on Piazza. For some reason it seems that the discussion activity was lower than usual, perhaps to some extent because there were fewer students taking the course than usual.

Otherwise, student feedback on the use of Piazza was mostly positive. From an instructor point of view, it is absolutely crucial for a course like this to have adequate support for mathematical typesetting in the discussion forum. For this reason KTH Social just does not work. 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.

Most students referred to the course webpage on a weekly basis, and students found the course webpages to be good. A change from last time, based on student feedback, 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, peer evaluation, and scribing).

This year, students were mostly neutral as to the value of the in-class opinion polls. This is in constrast to what is usually the case, namely that students view this positively as an opportunity to interact with the lecturer and affect the course planning during the course.

Perhaps the most disappointing findings from the instructor side was that less than half of the students prepared for upcoming lectures by reading new material, or by going over old material from previous lectures. 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.)

The students were asked whether having office hours for the course would be helpful, but the response was neutral. Reasons for why the students did not see the need for this could be that they could anyway ask questions on Piazza and also in connection with the lectures.

When asked about what aspects of the course should stay the same in a future course offering, it seems that the student were happy with the course organization and thought that most things should stay the same. The combination of scribing, problem sets and peer-reviewing was considered to have worked well.

Regarding aspects that could be improved, one suggestion was to have smaller but more frequent problem sets.

Conclusions and future changes

All in all, the students who passed this course were quite happy with it.

As described above, several aspects of the course were changed for the 2014 version as compared to the previous time the course was given in 2012, and these changes were kept in 2016.

The main modification this year was to require scribing. In the end this turned out to be very work-intensive, and so this instructor will probably be reluctant to try it again for the next few years. (Until it has been forgotten how much work it was, which, going by previous experience, will take five years…)

Going forward, the one big challenge is to modify the set-up in ways that would encourage (or make it necessary for) student to work more on the material in between lectures and prepare for lectures. This needs to be thought through carefully, however — for instance, a flipped classroom set-up just does not seem feasible for an advanced mathematical course like this one, where even understanding the prerequisites for a lecture can be a major challenge.

The main instructor believes that next time the course is given there should be smaller and more frequent problem sets. It is true that this would create problems with the cycle of alternating problem solving weeks and peer evaluation and discussion weeks, which is why it has not been done before. However, the instructor believes that the advantages — namely, forcing the students to work on a more continuous basis, rather than just in the run-ups to four big deadlines — would outweight the disadvantages.

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