Algorithms in the "Real World"

Fluid Flow Image


  • Course Versions
  • Course Topics
  • Lecture Notes
  • Information on algorithms available on the web
  • Companies that sell products that use various algorithms

  • Course Versions


  • Spring 2018
  • Fall 2015
  • Spring 2014
  • Spring 2013
  • Spring 2012
  • Fall 2010
  • Fall 2009
  • Fall 2008
  • Fall 2007
  • Fall 2006
  • Fall 2005
  • Fall 2004
  • Fall 2003
  • Spring 2003 (undergraduate version)
  • Fall 2002
  • Fall 2001
  • Fall 2000
  • A workshop on Algorithms in the "Real World". May 25-26, 2000.
  • Fall 1999
  • Fall 1997
  • Spring 1996

  • Course Topics


  • Data Compression
  • Cryptography
  • Linear Programming
  • Integer Programming
  • Triangulation and Meshing
  • The N-body Problem
  • VLSI Layout
  • Pattern Matching in Computational Biology
  • Indexing and Search Engines

  • Lecture Notes (Fall 97)


    The following notes are all in compressed (gzip) postscript.
    Full Notes (300 pages, .8Mbytes compressed)
    Notes by topic
    Front Part (Abstract, TOC, and List of Algorithms) 1
    Compression 1 (Ben Zhao) 14
    Compression 2 (Gabriel Moy) 23
    Compression 3 (Ben Liblit) 33
    Cryptography 1 (Tzu-Yi Chen) 51
    Cryptography 2 (David Oppenheimer) 59
    Cryptography 3 (Marat Boshernitsan) 72
    Linear Programming 1 (Richard Davis) 80
    Linear Programming 2 (Steven Czerwinski) 95
    Integer Programming 1 (Andrew Begel) 109
    Integer Programming 2 (Stephen Chenney) 116
    Triangulation 1 (Aaron Brown) 128
    Triangulation 2 (Franklin Cho) 144
    Triangulation 3 (Michael Downes) 154
    N-body 1 (Tajh Taylor) 165
    N-body 2 (Steven Gribble) 183
    VLSI 1 (Rich Vuduc) 195
    VLSI 2 (Mehul Shah) 210
    VLSI 3 + Pattern Matching 1 (Noah Treuhaft) 220
    Pattern Matching 2 (Felix Wu) 226
    Indexing 1 (Helen Wang) 234
    Indexing 2 (Ben Horowitz) 246
    Indexing 3 and Evolutionary Trees (Amar Chaudhary) 262
    Clustering 1 (Josh MacDonald) 272
    Eric Brewer on Hotbot (Carleton Miyamoto) 280
    References and Assignments 289

    Information on algorithms available on the web:


  • A comprehensive list of software products, many of which use various algorithms.
  • Applications of computational geometry.
  • The Stony Brook Algorithm Repository. A collection of implementations of algorithms in C, C++, Pascal and Fortran that are available over the web. Each implementation is ranked.
  • Finite element mesh generation.
  • Operations Research Resources
  • comp.graphics.algorithms FAQ
  • Yahoo: Science:Computer Science:Algorithms
  • The use of combinatorial algorithms in VLSI routing problems
  • Robotics faq
  • Tools forSequence analysis in Biology
  • Machine Learning resources.

  • A small sample of companies that sell products that use various algorithms:


    Optimization
    Geometry and Meshing
    Biology
    Cryptography
    CPLEX
    CAPS Logistics
    IBM OSL
    Astrokettle
    APC
    Carmen Systems
    Lindo Systems
    LogicTools
    Fluent
    Geomagic
    Pointwise
    Ansys
    FEGS
    CFDRC
    Marc
    Femsys
    AVL
    Celera
    Curagen
    HGSI
    MLNM
    Hyseq
    Genset
    Incyte
    Variagenics
    Algorithmic Research
    RSA Security
    Entrust
    Cryptomathic
    Netegrity
    InterTrust
    Zero Knowledge
    Mach 5
    Trick's List Owen's List Netsci's list Rivest's List


    Guy Blelloch, guyb@cs.cmu.edu.