15-850(C) Topics

This page will be filled out during the semester as we cover the topics.

  • Data Compression (January 31)
  • Delaunay Triangulation (February 7)
  • Encryption (February 14)
  • Max Flow and Min Cost Flow (February 28)
  • Linear Programming (March 6)
  • Integer Programming (March 13)
  • The N-body Problem (April 3)
  • VLSI Layout (April 10)
  • Pattern Matching (April 17)
  • Clustering (May 1)

    • And here is a list of other topics which we considered, some of which might be covered in the off weeks.

    Data Compression

    DealerMain TalkTalk 1Talk 2
    Sleator Bauer Sleator Gleichauf

    Required Readings

    Don't panic, the first 2 are only short overviews and last is just a couple tables.
  • Introduction to data compression by Peter Gutmann.
  • Image Compression Techniques.
    This has little technical content, but is a reasonable introduction to the terminology.
  • Daniel S. Hirschberg and Debra A. Lelewer. Context Modeling for Text Compression. In Image and Text Compression, ed. James A. Storer. Kluwer, 1992.
  • A.D. Wyner and J. Ziv. The sliding-window Lempel-Ziv algorithm is asymptotically optimal. (abstract).
  • A comparison of various compression codes for text and black and white images. Shows progression of the state-of-the-art over the years.

    • Secondary Topics

  • Fractal Compression. See the Introduction to fractal compression off of the compression faq, along with What is the state of fractal compression?.
  • The PPM algorithm. See A. Moffat. Implementing the PPM data compression scheme. (abstract).
  • Compression in MPEG. See the MPEG Resources on the Web page.

    • Other Readings

  • Timothy C. Bell, John G. Cleary, and Ian H. Witten. Text compression. Prentice Hall, c1990.
  • James A. Storer. Image and Text Compression. Kluwer, 1992
  • Gilbert Held and Thomas R. Marshall. Data compression : techniques and applications : hardware and software considerations, Wiley 1991 (3rd ed.)
  • LZW explained by Steve Blackstock. A nice 200 line description of Lempel-Ziv Welch compression.
  • E. Fiala and D. Greene. Data compression with finite windows (abstract).

    • Useful Links

  • comp.compression faq
  • Compression Pointers (comprehensive, but badly organized).
  • Yet more links
  • The GIF Licensing Controversy. The GIF format is patented by ComputServe and the LZW algorithm used by the format is patented by Unisys.

    • Encryption

    DealerMain TalkTalk 1Talk 2
    Miller Rochberg Miller Wong

    Required Readings

  • Introduction to Cryptography. A good online intro with several useful links.
  • Bruce Schneier, Applied Cryptography, Wiley, 1995. Chapter 19 (Public Key Algorithms), and Chapter 24 (Example Implementations).

    • Secondary Topics

  • Digital cash. See the Millicent page. It has pointers to many other pages.
  • DES and other Block Ciphers. See Bruce Schneier, Applied Cryptography, Wiley, 1995. Chapter 12, 13 and 14.
  • KERBEROS. See J. T. Kohl. The evolution of the KERBEROS authentication service. (abstract).

    • Other Readings

  • Jennifer Seberry and Josed Pieprzyk. Cryptography: An Introduction to Computer Security Prentice-Hall, 1989. (Theoretically Oriented)
  • Douglas R. Stinson. Cryptography: Theory and Practice. CRC Press, 1995.

    • Useful Links

  • Quadralay's Cryptography Archive
  • Cryptography: The Study of Encryption (another archive).

    • Linear Programming

    DealerMain TalkTalk 1Talk 2
    Blelloch Visitor? Gleichauf Blelloch

    Required Readings

  • E. L. Johnson and G. L. Nemhauser. Recent developments and future directions in mathematical programming. (abstract).
    This is a good overview of optimization techniques including both linear and integer programming.
  • G. L. Nemhauser. The age of optimization: solving large-scale real-world problems. (abstract).
    This paper has some overlap with the previous paper but concentrates on applications.
  • Gilbert Strang. Linear Algebra and its Applications. Chapter 8 (Linear programming and game theory).
    This is the most concise and clear introduction to the simplex method I found. If you have another source you have already used and feel comfortable with, feel free to read it instead.

    • Secondary Topics

  • Interior Point Methods. See
  • "Interior Point Methods for linear programming: Computational State of the Art", Lustig, Marsten, and Shanno, (abstract.)
    This is a very good overview of interior point methods and Karmakar's algorithm. I suggest it for everyone if you have time.
  • Ignizio and Cavalier. Linear Programming. Chapter 7
  • The Interior point archive.
    Lots of useful information and many online papers.
  • Implementing Simplex. See
  • Progress in Linear Programming, Robert Bixby, (abstract.)
    This is actually a follow up on the Lustig, Marsten, and Shanno article above. Its basic theme is that we should not give up on Simplex quite so soon.
  • Implementing the simplex method for the Optimization Subroutine Library, Forrest and Tomlin, (abstract.)
    This describes IBM's implementation of Simplex for OSL, a product they sell.

    • Other Readings

  • J. P. Ignizio and T. M. Cavalier, Linear Programming, Prentice Hall, 1994
  • Jorge J. More and Stephen J. Wright. Optimization software guide. SIAM, 1993.
  • Bradley, Hax and Magnanti. Applied Mathematical Programming. Addison-Wesley, 1976.
  • G. L. Nemhauser, A.H.G. Rinnooy Kan, and M. J. Todd (ed.). Optimization. Elsevier, 1989.
  • M. Bazaraa, J. Jarvis, and H. Sherali. Linear Programming and Network Flows. Wiley, 1990.

    • Useful Links

  • Linear Programming Faq (includes a list of other web links).
  • Operations Research Page
  • Applications
  • Online Companies that sell linear programming products (see the bottom of the page).
  • Interior point archive (includes many online papers).
  • Did Karmarkar deserve a patent? (a discussion)
  • A course on linear programming and related topics with online course notes.
  • A list of applications of linear and integer programming for the DELTA airlines, American Airlines, Northwest Airlines, UPS, Coca Cola, and the federal highway commission.

    • Integer Programming

    DealerMain TalkTalk 1Talk 2
    Blelloch Blelloch Harkavy Narlikar

    Required Readings

  • Bradley, Hax and Magnanti. Applied Mathematical Programming. Chapter 9 (Integer Programming)
    This chapter both has an introduction to the various application areas of integer and mixed-integer programming and an introduction solution techniques including Branch-and-bound and cutting plane techniques.
  • R. Subramanian, R. P. Scheff, Jr., J. D. Quillinan, D. S. Wiper, and R. E. Marsten. Coldstart: Fleet assignment at Delta Air Lines. (abstract).
    The paper states that Delta saves $300 Million a year by using mixed-integer programming to schedule their fleet.

    • Secondary Topics

  • Crew Pairing. See Anbil, Tanga and Johnson, A global approach to crew-pairing optimization (abstract).
  • Financial Models. See Dahl, Meeraus and Zenios, Some financial optimization models: II Financial engineering, In Financial Optimization.
  • Branch and Bound Methods.

    • Other Readings

    Most of the readings under linear programming have material on integer programming. In addition, the following references are particularly strong on integer or mixed integer linear programming. The list also includes some applications.
  • George L. Nemhauser and Laurence A. Wolsey. Integer and combinatorial optimization. Wiley, 1988.
  • H. M Salkin and K. Mathur. Foundations of Integer Programming. North-Holland, 1989.
  • J. Abara. Applying integer linear programming to the fleet assignment problem. (abstract).
  • Stavros A. Zenios (ed.). Financial optimization. Cambridge University Press, 1993.

    • Useful Links

  • Linear Programming Faq (includes a list of other web links).
  • Operations Research Page
  • Applications
  • NEOS Guide (good background reading).
  • Online Companies that sell linear programming products (there are also 100s which are not online).
  • A list of applications of linear programming for the DELTA airlines, American Airlines, Northewest Airlines, UPS, Coca Cola, and the federal highway commission.

    • Maximum Flow and Minimum Cost Flows

    DealerMain TalkTalk 1Talk 2
    Sleator Sleator Talmor Birkedal

    Required Readings

  • Cormen, Leiserson and Rivest, Introduction to Algorithms. Chapter 27 (Maximum Flow).
  • Goldberg's algorithm for maximum flow in perspective: a computational study. R. J. Anderson and J. C. Setubal. In Network Flows and Matching.
    This has some nice experimental results that compare several different maximum flow algorithms over a variety of graph types.

    • Secondary Topics

  • Modeling Traffic. See D. J. Zawack and G. L. Thompson. A dynamic space-time network flow model for city traffic congestion. (abstract).
  • Min-Cost Flow. See
  • An Efficient implementation of a scaling minimum-cost flow algorithm, Andrew V. Goldberg. STAN-CS-92-1439.
    This gives a brief description of the successive approximation push-relabel method of Goldberg and Tarjan (the state-of-the-art). What is more interesting, however, are the experimental results.

    • Other Readings

  • R. Ahuha, T. Magnanti and J. Orlin, Network flows: theory, algorithms, and applications Prentice Hall 1993.
  • Network Flows and Matching: First DIMACS Implementation Challenge, David Johnson and Catherine McGeoch (editors). AMS, 1993.

    • Useful Links

  • Network-flow codes and models (FTP directory).
  • Bibliography on Network Flow Problems

    • Delaunay triangulation

    DealerMain TalkTalk 1Talk 2
    Blelloch Bern Ghuloum Hardwick

    Required Readings

  • F. Aurenhammer, Voronoi diagrams-- a survey of a fundamental geometric data structure, ACM Computing Surveys, 1991, 345--405.
  • Scot Drysdale, Voronoi Diagrams: Applications from Archaology to Zoology.
  • Review the applications described in Eppstein's Voronoi Diagram's Page.

    • Secondary Topics

  • Mesh Generation. See
  • The Finite element mesh generation page
  • The Meshing Research Corner (here at CMU)
  • M. Bern and D. Eppstein, Mesh generation and optimal triangulation, in "Computing in Euclidean Geometry", 2nd edition, World Scientific, 1995.
  • T.J. Baker, Developments and trends in 3-d mesh generation, Appl. Numer. Mathematics, 1989, 275--304.
  • Surface Reconstruction. See
  • G. Barequet and M. Sharir, Piecewise-linear interpolation between polygonal slices, 10th ACM Symp. Computational Geometry, 1994.
  • Application of Delaunay triangulation to Interpolation.

    • Other Readings on Algorithms

  • Preparata, Franco P. Computational geometry: an introduction. Springer-Verlag, 1988.
  • O'Rourke. Computational Geometry in C. Cambridge University Press, 1994.
  • J. Nievergelt and K. Hinrichs. Algorithms and data structures: with applications to graphics and geometry. Prentice Hall, 1993.

    • Other Readings on Applications

  • Okabe, Boots, and Sugihara, Spatial Tesselations: Concepts and Applications of Voronoi Diagrams, Wiley, 1992.
  • J.D. Boissonnat and B. Geiger, Three-dimensional reconstruction of complex shapes based on the Delaunay triangulation, in "Biomedical I Processing and Biomedical Visualization", Acharya and Goldgof, eds., SPIE, 1993, 964--975.
  • M. Polis and D. McKeown, Issues in iterative TIN generation to support large scale simulations, AUTO-CARTO 11, 1993.
  • H. Edelsbrunner and E. Muecke, Three-dimensional alpha shapes, ACM Trans. Graphics, 1994, 43--72.

    • Useful Links

  • Geometry in Action, an excellent page on applications of computational geometry
  • The computational geometry pages. Another page on computational geometry.
  • Yahoo's Geometry page.
  • Finite element mesh generation.
  • Application of Delaunay triangulation to Interpolation.
  • An experimental comparison of various Delaunay algorithms. Includes MPEG movies of the algorithms in action (if you dare wait for them to arrive from Germany).
  • Companies that sell products that use Delaunay triangulation:
  • A long list of grid generators at Silicon Graphics.
  • ANSYS
  • SDRC
  • ICEM CFD
  • Fluent (Rampant)

    • VLSI Layout

    DealerMain TalkTalk 1Talk 2
    Miller Miller Boyan Bern

    Required Readings

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

    • Secondary Topics

    Other Readings

  • T. Lengauer, Combinatorial algorithms for integrated circuit layout, Wiley 1990.
  • B. Korte, L Lovasz, H. J. Promel, and A. Schrijver (eds.). Paths, flows, and VLSI-layout. Springer Verlag, 1990.

    • Useful Links

  • Industrial CAD Sites on the Web.
  • University of Idaho's Links to VLSI information.
  • The use of combinatorial algorithms in VLSI routing problems
  • A good page of algorithms used in VLSI CAD (University of Virginia).

    • Pattern Matching

    DealerMain TalkTalk 1Talk 2
    Miller Birkedal Miller Reid-Miller

    Required Readings

  • Arthur M. Lesk. Computational molecular biology: sources and methods for sequence analysis. Oxford University Press, 1988.

    • Secondary Topics

    Other Readings

    Useful Links

  • A very good bibliography on the topic.
  • A course on Algorithms for Molecular Biology. Includes many references.
  • A bibliography on Computational Gene recognition.
  • Sequence analysis software
  • Human Genome Project Information including a Primer on Molecular Genetics.

    • The N-body Problem

    DealerMain TalkTalk 1Talk 2
    Blelloch Blelloch Leon Bauer

    Required Readings

  • The Numerical Solution of the N-Body Problem, L. Greengard (abstract).
  • N-body/Particle simulation Methods. An excellent online overview of the various n-body methods. Here is a local copy since the connection is slow.

    • Secondary Topics

    Other Readings

  • Fast algorithms for classical physics, L. Greengard (abstract).
  • A hierarchical O(N Log N) force calculation algorithm. J. E. Barnes and P. Hut. Nature, 324(4):446-449, December 1986.
  • Fast parallel tree codes for gravitational and fluid dynamical N-body problems. Salmon, Warren and Winckelmans. (abstract).
  • Scalable variants of multipole-based algorithms for molecular dynamics applications Board, Hakura, Elliot, and Rankin. (abstract).
  • Optimal parallel all-nearest-neighbours using the well-separated pairs decomposition. P.B. Callahan. In 34th Annual Symposium on Foundations of Computer Science, pages 332-340, Palo Alto, 1993. IEEE.
  • Astrophysical n-body simulations using hierarchical tree data structures. M. Warren and J. Salmon. In Proceedings of Supercomputing, 1992.

    • Useful Links

    Clustering

    DealerMain TalkTalk 1Talk 2
    Sleator Sleator Juarez Rochberg

    Required Readings

    Secondary Topics

    Other Readings

  • Everitt, Brian. Cluster analysis (2d ed.). Halsted Press, 1980.

    • Useful Links

    Other Topics

    Here are some other areas in which algorithms are used in the real world.

  • Indexing (i.e. for web crawlers)
  • Robot navigation
  • Linear System's solvers
  • Graphics
  • Speech recognition
  • Computer vision
  • Machine learning
    • Guy Blelloch, blelloch@cs.cmu.edu.