About the Book

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

• By Language
  • C
  • C++
  • C#
  • Java
  • FORTRAN
  • Python
  • Mathematica
  • Pascal
  • ADA
  • Lisp
  • Binary
• By Problem
  • 1.1 Data Structures
    • Dictionaries
    • Priority Queues
    • Suffix Trees and Arrays
    • Graph Data Structures
    • Set Data Structures
    • Kd-Trees
  • 1.2 Numerical Problems
    • Solving Linear Equations
    • Bandwidth Reduction
    • Matrix Multiplication
    • Determinants and Permanents
    • Constrained and Unconstrained Optimization
    • Linear Programming
    • Random Number Generation
    • Factoring and Primality Testing
    • Arbitrary Precision Arithmetic
    • Knapsack Problem
    • Discrete Fourier Transform
  • 1.3 Combinatorial Problems
    • Sorting
    • Searching
    • Median and Selection
    • Generating Permutations
    • Generating Subsets
    • Generating Partitions
    • Generating Graphs
    • Calendrical Calculations
    • Job Scheduling
    • Satisfiability
  • 1.4 Graph Problems -- polynomial-time problems
    • Connected Components
    • Topological Sorting
    • Minimum Spanning Tree
    • Shortest Path
    • Transitive Closure and Reduction
    • Matching
    • Eulerian Cycle / Chinese Postman
    • Edge and Vertex Connectivity
    • Network Flow
    • Drawing Graphs Nicely
    • Drawing Trees
    • Planarity Detection and Embedding
  • 1.5 Graph Problems -- hard problems
    • Clique
    • Independent Set
    • Vertex Cover
    • Traveling Salesman Problem
    • Hamiltonian Cycle
    • Graph Partition
    • Vertex Coloring
    • Edge Coloring
    • Graph Isomorphism
    • Steiner Tree
    • Feedback Edge/Vertex Set
  • 1.6 Computational Geometry
    • Robust Geometric Primitives
    • Convex Hull
    • Triangulation
    • Voronoi Diagrams
    • Nearest Neighbor Search
    • Range Search
    • Point Location
    • Intersection Detection
    • Bin Packing
    • Medial-Axis Transformation
    • Polygon Partitioning
    • Simplifying Polygons
    • Shape Similarity
    • Motion Planning
    • Maintaining Line Arrangements
    • Minkowski Sum
  • 1.7 Set and String Problems
    • Set Cover
    • Set Packing
    • String Matching
    • Approximate String Matching
    • Text Compression
    • Cryptography
    • Finite State Machine Minimization
    • Longest Common Substring
    • Shortest Common Superstring
• Algorithm Links
  • Algorithm Lectures
  • Algorithm Design Manual Information
  • CSE 373 Course page
  • NIST Dictory of Algorithms and Data Structures
  • World of Mathematics
  • Programming Challenges
  • Graduate Study Opportuinties

1.7.4 Approximate String Matching

Problem: Does there exist an alignment between t and p with edit cost at most k, ie. can we transform part of t to p using at most k additions, deletions, and substitutions.

Excerpt from The Algorithm Design Manual: Approximate string matching is fundamental to text processing, because we live in an error-prone world. Any spelling correction program must be able to identify the closest match for any text string not found in a dictionary. Genbank has become a fundamental tool for molecular biology by supporting homology (similarity) searches on DNA sequences. Suppose you were to sequence a new gene in man, and you discovered that it is similar to the hemoglobin gene in rats. It is likely that this new gene also produces hemoglobin, and any differences are the result of genetic mutations during evolution.

Recommended Books

The Art of Computer Programming : Sorting and Searching by Donald Knuth	Algorithms on Strings, Trees, and Sequences by Dan Gusfield	Practical Algorithms for Programmers by A. Binstock and J. Rex
Text Algorithms by M. Crochemore and W. Rytter	Handbook of Algorithms and Data Structures by G. Gonnet and R. Baeza-Yates	Introduction to Algorithms by T. Cormen and C. Leiserson and R. Rivest and C. Stein
Introduction to Algorithms by U. Manber	Computer Algorithms by S. Baase	Time Warps, String Edits, and Macromolecules: the theory and practice of sequence comparison by D. Sankoff and J. Kruskal

Related Links