Introduction


Another name for the course: Extreme Algorithms

 

Consider other types of extremes:

Exercise: List some examples of "extreme engineering" or technology.


Extreme Algorithms

 

What might constitute an extremophile in the world of algorithms?

First, let's be clear about what does not:

 

What we do mean:

 

What we'd like to know:


Course overview

 

What this course is about: extreme algorithms.

We'll explore extremism with algorithms in these domains:

  • A theoretical example: the Minimum Spanning Tree (MST) problem.

  • Two classic optimization problems:
    • The Traveling Salesman Problem (TSP).
    • The Satisfiability (SAT) problem.

  • A commercially-driven algorithmic challenge: Collaborative Filtering (CF) and the Netflix Prize.

  • Algorithms that compete:
    • Chess.
    • M-N-TicTacToe.

  • A simple problem crafted for this class: Graph Drawing.

  • Perhaps others: theorem proving, planning.
 

What you will do in the course:

  • One presentation (of a paper in one of the topic areas).
  • One term project.
  • Implementations of simple algorithms for the problems we study.
  • A competition.

A tool to test your algorithms

 

In this course, we'll use a simple tool to:

  • Test-drive your implementations.
  • Run a competition.
  • For some problems, view the results graphically.

Follow these instructions.


References and further reading

 


[WP-1] Wikipedia entry on Extreme Sports.
[WP-2] Wikipedia entry on Source lines of code.
[Brad2009] R.Bradley. The Fall Guy: A record-setting, 186-foot descent. National Geographic Adventure, Dec 2009.
[Dibb2006] J.Dibbell. The Fast Supper. New York Magazine, October 2006.
[Top500] Top 500 Supercomputer sites.