CS294-3: Algorithms in the "Real World"

Fluid Flow Image

Taught at UC Berkeley, Fall 1997
Instructor: Guy Blelloch
Time and place:Wed-Fri 12:30-2:00, 310 Soda Hall
Credit: 3 Units
Prerequisites: An advanced undergrad course in algorithms (CS170 or equivalent will suffice).
  • Course overview
  • Topics, Lecture Notes and Assignments
  • Information on algorithms available on the web
  • Companies that sell products that use various algorithms
  • Class List and results from midsemester questionnaire.

    • Course Overview:

    Although all but the simplest algorithms are often derided as being impractical, in reality sophisticated algorithms are used in many applications. The goal of the class is to get an appreciation of where algorithms are used and to understand the various considerations and tradeoffs used in designing algorithms (e.g. time, space, generality, and quality of the solution). I encourage both theory and system's students to take the class. Problems we will consider include:
  • Compression (how are gifs encoded?)
  • Delaunay triangulation (how does the Ford Motor Company use it?)
  • Linear programming (is Karmakar's algorithm worth a patent?)
  • Integer programming (How much does Delta Airlines save a year?)
  • Text searching and indexing (How do Lycos, HotBot and Alta Vista work?)
  • Pattern matching (its use in the human genome project?)
  • Traveling salesman (how is it used in biology?)
  • Clustering (Who has American Express clustered you with?)
  • N-body algorithms (How are they used to solve fluid flow problems?)
    • We will spend 2 or 3 lectures on each topic. Each student will be expected to either scribe a class (take notes and format them) or give a 30 minute presentation on one of the topics, complete a set of homeworks, and take a final. The grade will be partitioned as follows:
  • Assignments -- 50%
  • Take home Final -- 30%
  • Quality of scribenotes or lecture -- 20%

    • Topic List and Approximate Schedule

    This is a priliminary topic list and schedule. It will surely be modified based on the interests of the students, schedule of possible guest speakers, and extra days required by some topics.

    We will cover one topic each week or so (2 or 3 lectures). Information on each topic (e.g. readings, web pointers) will be filled out during the semester before the classes.

  • Introduction (Aug 27)
  • Data Compression (Aug 29, Sept 3, 5)
  • Cryptography (Sept 10, 12, 17)
  • Linear Programming (Sept 19, 26, No class on the 24th)
  • Integer Programming (Oct 1, 3)
  • Triangulation and Meshing (Oct 8, 10, 15)
  • The N-body Problem (Oct 17, 22)
  • VLSI Layout (Oct 24, 29, 31)
  • Pattern Matching in Computational Biology (Nov 5, 7)
  • Indexing and Search Engines (Nov 12, 14, 19)
  • Clustering (Nov 21, 26)
  • Thanksgiving (Nov 28)
  • Review (Dec 3, 5)

    • We might also look at one of the following topics if we have time and there is interest:

  • Robot navigation
  • Linear System's solvers
  • Graphics
  • Speech recognition
  • Computer vision
  • Machine learning

    • 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 Linear Programming - FAQ
  • comp.graphics.algorithms FAQ
  • Yahoo: Science:Computer Science:Algorithms
  • The use of combinatorial algorithms in VLSI routing problems
  • Robotics faq
  • Sequence analysis
  • Computational Gene recognition (a bibliography).
  • Machine Learning resources.

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

  • 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.

  • 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 Traveling Salesman problems. For Shortest Path, travel times and distances are calculated and the streets can be listed. The Traveling 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."

  • 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)

    • Relevant Books

    See the lists within each of the topic pages

    Help on giving presentations:

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