15-850(C): Algorithms in the "Real World"

Fluid Flow Image

This page is superseded by more recent versions of the class.

Instructors: Guy Blelloch, Gary Miller, and Danny Sleator
Time and place:W 2:00-4:20, WeH 5304 (SPRING 96)
Credit: 1 CS Core Unit / 12 University Hours / Self Enlightenment
Prerequisites: The Theory core (can be taken concurrently)
More recent version of the course (Fall 97) along with Lecture Notes and Web Notes
  • Course overview
  • Course organization
  • Course topics, schedule, and readings. (The meat)
  • Topic Assignments
  • Information on algorithms available on the web
  • Companies that sell products that use various algorithms
  • Books on reserve
  • Help on giving presentations

    • Course Overview:

    This class will study how algorithms are used in practice. Contrary to the myth that algorithm are only useful for passing the theory core, efficient algorithms are used in an very wide variety of applications. The goal of the class is to get an appreciation of where algorithms are used and to understand the various considerations beyond asymptotic time analysis (space, generality, heuristics) that make a good algorithm.

    We encourage students who have already completed their core requirements to take the class anyway. We also encourage both theory and system's students to take the class.

    Some problems we will consider:

  • Compression (how are gifs encoded?)
  • Delaunay triangulation (how does the Ford Motor Company use it?)
  • Encryption (can you find the next security hole in netscape?)
  • Linear Programing (is Karmakar's algorithm worth a patent?)
  • Max-Flow (does the power company use it?)
  • Pattern Matching (its use in the human genome project?)
  • Sparse linear systems (how are they used for graphics?)
  • Traveling salesman (how is it used in biology?)
  • Learning algorithms (does Wall Street care?)
  • .....

    • Organization:

    The class will be run as follows. Each week one student will be responsible for preparing for a particular topic/problem. This will include
    1. Preparing an html paper that outlines the various algorithms for the problem along with which ones seem to be used in practice and why, and outlines the applications of the problem.
    2. Preparing a talk on the topic.
    3. Delegating a couple algorithms for the problem to other students who will study those algorithms in more depth and present them.
    4. Giving the talk and leading a discussion.
    The idea is that the topic leader will give his/her talk (about 1 hour), followed by a break (snacks will be served). After the break we will cover the more detailed description of the algorithms followed by a discussion on the topic. The course will also include a final programming project. The goal of the project will be to see if you can outclass an algorithm that is currently being used in some application. For the final project, students can work in groups.

    Information on algorithms available on the web:

  • A comprehensive list of software products, many of which various algorithms.
  • Applications of computational geometry.
  • Finite element mesh generation.
  • Operations Research Linear Programming - FAQ
  • comp.graphics.algorithms FAQ
  • Yahoo: Science:Computer Science:Algorithms
  • The use of combinatorial algorithms in VLSI routing problems
  • A list of applications of linear programming for the DELTA airlines, American Airlines, Northewest Airlines, UPS, Coca Cola, and the federal highway commision.
  • Machine Learning Algorithms
  • Robotics faq
  • Sequence analysis
  • Computational Gene recognition (a bibliography).
  • Machine Learning resources.
  • A Java page of graph-algorithm animations

    • Companies that sell products that use various algorithms:

  • Terratech Mapping Services. Shortest Path and traveling salesman.

    "The Vehicle Routing Utilities can help you plan depot locations, vehicle journeys and fleet operations to reduce vehicle operation costs, improve customer service, reduce expenditure and determine catchment areas. Utilities solve Shortest Path and Travelling Salesman problems. For Shortest Path, travel times and distances are calculated and the streets can be listed. The Travelling Salesman function outputs the order of visits, travel times and distances together with driving instructions. The Isochrone Generator displays vehicle coverage areas against time from a first location, or any number of fixed locations."

  • Fluent (Rampant). Delaunay Triangulation.

    "Simple, fast and highly automated mesh generation using state-of-the-art Delaunay triangulation which produces optimal mesh quality."

  • CPLEX. Linear programming.

    "CPLEX's linear and mixed-integer programming solvers are known for superior performance and reliability, particularly on large or difficult problems.

  • CAPS Logistics. Flow problems and Linear programming.

    "The TOOLKIT makes quick work of all your routing and scheduling tasks. In minutes you can plan fixed, master and dynamic routes, prioritized by customers and orders. Routing data and maps are seamlessly integrated to make editing easy. And powerful interactive functions, such as "lassoing," let you zero in on particular groups of customers. For improved dispatching, the TOOLKIT also provides multiple routing algorithms to help you minimize distance, cost and time. "

  • The IBM Optimization Subroutine Library (OSL)

    • Books on Reserve:

    The following books have been put on reserve in the library.

    R. Ahuha, T. Magnanti and J. Orlin, Network flows: theory, algorithms, and applications. Prentice Hall 1993.

    Timothy C. Bell, John G. Cleary, and Ian H. Witten. Text compression. Prentice Hall, c1990.

    Everitt, Brian. Cluster analysis (2d ed.). Halsted Press, 1980. (Checked out of library.)

    Gilbert Held and Thomas R. Marshall. Data compression : techniques and applications : hardware and software considerations, Wiley 1991.

    J. P. Ignizio and T. M. Cavalier, Linear Programming, Prentice Hall, 1994

    D. S. Johnson and C. C. McGeoch. Network Flows and Matching. DIMACS series in Discrete Mathematics and Theoretical Computer Science, Volume 12, 1993.

    B. Korte, L Lovasz, H. J. Promel, and A. Schrijver (eds.). Paths, flows, and VLSI-layout. Springer Verlag, 1990. (Checked out of library.)

    T. Lengauer, Combinatorial algorithms for integrated circuit layout, Wiley 1990. (In my office.)

    Arthur M. Lesk. Computational molecular biology: sources and methods for sequence analysis. Oxford University Press, 1988. (At Mellon Library)

    J. Nievergelt and K. Hinrichs, Algorithms and data structures : with applications to graphics and geometry Prentice Hall 1993

    O'Rourke, Computational Geometry in C, Cambridge University Press, 1994. (Checked out of library.)

    Preparata, Franco P. Computational geometry : an introduction. Springer-Verlag, 1988. (Checked out)

    Bruce Schneier, Applied Cryptography, Wiley, 1995.

    N. Sherwani, Algorithms for VLSI Physical Design Automation, Kluwer, 1993.

    Douglas R. Stinson. Ctyptography: Theory and Practice. CRC Press, 1995. (At SEI library)

    James A. Storer. Image and Text Compression. Kluwer, 1992

    A. H. Watt and M. Watt, Advanced animation and rendering techniques, Addison-Wesley, 1992

    Other books

    Non on reserve, but potentially of interest.

    Storer, James A. Data Compression: Methods and Theory, Computer Science Press, 1988. (Library does not have)

    George L. Nemhauser and Laurence A. Wolsey. Integer and combinatorial optimization. Wiley, 1988. (Checked out)

    Jorge J. More and Stephen J. Wright. Optimization software guide. SIAM, 1993. (E&S: 519.3 M83O 1)

    G. L. Nemhauser, A.H.G. Rinnooy Kan, and M. J. Todd (ed.). Optimization. Elsevier, 1989. (E&S-BK 519.92 O622)

    Stavros A. Zenios (ed.). Financial optimization. Cambridge University Press, 1993. (Hunt: 332 F4912 1)

    Help on giving presentations:

  • How to Present a Paper in Theoretical Computer Science, by Ian Parberry.
    • Guy Blelloch, blelloch@cs.cmu.edu.