The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

BIPM -- Bipartite Matching Codes


David Eppstein's WWW page http://www.ics.uci.edu/~eppstein/161/kmp/ contains an implementation of the Knuth-Morris-Pratt string matching algorithm in C++. It exists as a teaching example from his algorithms course notes.

He also provides a Mathematica code for the Minkowski sum problem in http://www.ics.uci.edu/~eppstein/junkyard/ukraine/ , which computes Minkowski sums of line segments (aka zonotopes). This problem is also closely related to maintaining line arrangements. The program works in any dimension, but doesn't do Minkowski sums of more complicated shapes.


  • Download Files (local site)
  • David Eppstein's Homepage
  • Link to EPPSTEIN's Knuth-Morris-Pratt Algorithm
  • Link to EPPSTEIN's Minkowski sums code in Mathematica

    Problem Links

      
    Minkowski Sum (4)
      
    String Matching (3)



    This page last modified on 2008-07-10 .
    www.algorist.com