CS 297: Championship Algorithms

• Instructor: Prof. Rahul Simha

• Office Hours: Tuesdays 4-5.30pm, Phillips 717, or by appointment.

• Class Time/Place: Thursdays 6.10-8.40pm, Tompkins 205

• Prerequisites: A course in algorithms, curiosity.

• What the course is about:

  What kinds of algorithms win championships? Yes, there are algorithm competitions and there are winning algorithms. Curiosity leads us to ask: what does it take to win such a championship? What do the "best of the best" algorithms have in them?

  What are well-known algorithm competitions and which algorithms have won? In this course, we will look at a few algorithm competitions and learn what it takes to write a competitive algorithm.

  What will you learn in this course? First, the theme is a great excuse to learn about some interesting and useful areas in computer science. For example:

  • Chess and game-playing algorithms. What you'll learn: the basics of game trees. We will of course want to look at ideas in the program that defeated world (human) champion Garry Kasparov.
  • Collaborative filtering algorithms. These are algorithms that make recommendations - if you've shopped at Amazon, you know what this means. What you'll learn: how such algorithms work. We will look at the winner of the $1,000,000 NetFlix recommendation-algorithm competition.
  • Logic algorithms. These are algorithms that solve the so-called Satisfiability problem, one of the most useful problems (you'd be surprised at the number of applications). We will look at recent winners, while also learning about basic ideas in logic from an algorithmic point of view.

  We will also look at some other competitions. Most importantly, we will learn about what it takes to go beyond basic code that implements an algorithm - exactly what differentiates the winners?

• Course objectives. Students will learn about the problems and some of the algorithms, and work in teams to develop code, perhaps towards some competition problems or an entirely new problem.