Teaching Efficient Algorithms and Intractable Problems

I teach an upper division algorithms course at UC Berkeley. Here's some of my stuff.

CS170, Berkeley’s upper division algorithms class, has two reputations. The first is a reputation for being intense, meticulous, and needlessly theory heavy. The second is a reputation for being satisfying, elegant, and intuitive.

The goal for any CS170 instructor: how do you take students who would’ve seen the course in the first way, and cause them to see the course in the second way?

My pedagogical approach focuses on two pillars:

  • Visual intuition. I prepare visual aids on OneNote and draw on them during my section. Lots of seemingly clunky and technical algorithms often have intuitive, geometric proofs, and getting students to see it in this way greatly helps them understand these algorithms. The one thing I am always asked for at the end of my sections are my notes.
  • Examples. Instead of doing a comprehensive lecture at the beginning then throwing students a bunch of questions, I like to interweave examples and conceptual discussion. This way, students are incrementally able to learn and apply their knowledge, building up a knowledge base to reach more difficult topics.

Here are some of my notes and demos from the Spring 2023 semester. I'd recommend checking out this primer on FFT to get a feel for my conceptual style.