Consider other types of extremes:
- Extreme sports [WP-1]
- Combines "danger" and "counter-cultural" in some way.
- Example: kayaking down a waterfall
⇒ record: 186-foot drop in a kayak
[Brad2009]
- Extreme cuisine/dieting example [Dibb2006]
- Body-Mass-Index (BMI) = weight-in-kg / (height-in-m)2
- Normal range: 18.5 - 25.
- Less than 16.5 ⇒ severely underweight.
- Calorie Restriction Society: very low-cal, low-quantity diets
⇒ BMI around 15 for many members
- Life at extremes:
- -129°F in Antartica, 150°F in Libya
- Bacteria in antartic ice, or hydrothermal vents (extremophiles).
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:
- We don't mean a lot of code: [WP-2]
- Windows-XP: 40 million lines of code
- Debian-4.0: 283 million lines
- We don't mean fast hardware: [top500]
- Cray XT-5: 2.3 petaflops/s with 224,162 cores
- IBM BlueGene: 294,412 cores.
What we do mean:
- Algorithms that are "fastest" in their category.
- Algorithms that break theoretical "barriers".
- Algorithms that win competitions against each other or humans.
- These are closer in spirit to the individual achievements in
extreme sports.
What we'd like to know:
- What are these extreme algorithms made of?
- What separates such an algorithm from the ones in textbooks?
- Is it a single idea that makes the difference?
- New way of thinking or an unsuspecting refinement?
- How did such algorithms come about? Incremental evolution or
flash of genius?
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:
- 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.