Advanced algorithms is an advanced-level graduate course for students who specialize in algorithms in the department of computer science of TU Kaiserslautern. I gave that course in the summer term of 2017.

The overarching theme of the course is how to tackle NP-hard problems; in the course I surveyed

  • pseudopolynomial algorithms
  • fixed-parameter tractability
  • randomized algorithms, and
  • approximations.

For all these topics, we discussed algorithmic design patterns and exemplary algorithms where they are successfully applied. Moreover, we also discussed the corresponding impossibility results and lower bounding techniques:

  • strong NP-hardness
  • para-NP hardness, W[1] hardness, ETH-based lower bounds
  • randomized complexity classes, and
  • gap reductions and PCP theorems

I gave this course in the summer term 2017 at TU Kaiserslautern, see the course catalog and the course website of my group there. It was a very small course (~10), but with a very active group of students, and overall a very enjoyable experience. According to the evaluation, this was felt in both ways.

My first own video lectures

I took the opportunity to try out some new technical gadgets for the course. To make a long story short, I now have nice HD videos of all my lectures:

Youtube playlist with my lecture screencasts.

What I would like to argue here is that there is little reason not to do such videos. It is neither technologically challenging, nor expensive in terms of money and time.

Extra effort for professors and lecturers is the number one reason for blocking innovations in teaching in my experience. I would like to share my experience with advanced algorithms here, to show that very little extra effort suffices to create lecture videos that offer a significant benefit for students over a traditional course.

Technical Details

The course was organized as traditional lecture with live sessions, but I used my ThinkPad X201 Tablet to take it to the digital age.

I prepared LaTeX slides for definitions, code, theorems, etc., used these as background in Xournal and wrote proofs and informal discussions on top of them by hand. I used SimpleScreenRecorder for the screencasts, and an affordable external mic for good audio quality.

I put the videos on youtube for several reasons

  • youtube supports adjusting the playback speed. (Actually an HTML5 feature, but unfortunately not included in a convenient GUI by many video platforms.) It cannot be stressed too much how helpful this is when watching lectures (speaking from my own experience).
  • youtube has by far the best support for mobile devices.
  • youtube digests almost anything that remotely looks like a video; it simply works and is fast.
  • Students are already watching videos on youtube …

It might be seen as an issue that youtube is completely public. There is no (convenient) option, e.g., to require a password before one can watch the videos. (Videos can be made private so that they are only visible to invited users, but that requires all students to log into youtube. This is inconvenient …) Personally, I do not see a problem having the videos publicly available; see also my approach to deal with mistakes. Of course, sometimes legal issues make that impossible.

PDF lecture notes

Xournal allows to save the result (slides plus handwritten notes) as one pdf. This serves as written lecture notes for convenient lookup of details. (Searching a pdf is much faster than finding the right part in the video).

You find the lecture notes on the course website at TU KL.

As a graphical learner, I find it personally extremely helpful to have exactly the same screen content in the pdfs that I also had in class. This is something (typed) scribes will not give you.

I also used these pdfs to add clarifications, see below.

How it worked

The didactic idea behind the switch between prepared slides and notes written by hand during class was to emphasize and slow down for parts that require careful thought and attention. Unlike a traditional blackboard lecture (which also serves this purpose), however, no time is lost in the transition, since I use the same pen as pointing device in the “slide mode”.

For lectures that traditionally would have been taught on the blackboard, this combination is a great alternative. There are a few advantages of blackboards—its sheer size, more physical “action” with the speaker walking around—but overall, I see the benefits of mixing in slides and interactive material and having the videos outweighing that by far.

The benefit of adjustable playback speed cannot be emphasized enough.

Errata

Every lecturer makes mistakes. The public videos make it possible for everyone to hunt for and point out my mistakes.

I would like to see this as an opportunity, rather than a daunting prospect. Correcting the videos is a lot of effort, and I did not try to do that. Instead, I added corrections and clarifications to the pdfs created in class (in blue, to make them easy to spot).

These pdfs are what students mostly work with after having seen the video or the live session once, so it is the right place to have the corrections. (And much more convenient than any separate list of errata.) Moreover, adding the annotations in Xournal is as little effort as it can be.

Did I feel embarrassed about some of my mistakes? Absolutely. In a few occasions, what I said was plain wrong. Sure, this should not happen, and I feel bad about it; with better preparation, I could have avoided it. But did it make the course and the videos less effective for the students? I do not think so. Most errors were found quickly (by my students or myself) and the correction is available for everyone (not only that motivated student who bothered to ask after class).

In summary, I think keeping the videos as they are and correcting the pdf notes is an effective and inexpensive way to deal with the mistakes all of us make.

Evaluation

This is a screenshot of the results of the official course evaluation for Advanced Algorithms. The original website is only accessible from within the university network of TU Kaiserslautern.