Algorithms (Catalog)
Data structures
Catalog reference markup
Dictionaries
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#ds-dictionaries)
Priority queues
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#ds-priority-queues)
Suffix trees and arrays
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#ds-suffix-trees-and-arrays)
Graph data structures
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#ds-graph-data-structures)
Set data structures
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#ds-set-data-structures)
Kd-trees
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#ds-kd-trees)
Solving linear equations
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#np-linear-equations)
Bandwidth reduction
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#np-bandwidth-reduction)
Matrix multiplication
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#np-matrix-multiplication)
Determinants and permanents
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#np-determinants-and-permanents)
Constrained/unconstrained optimization
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#np-optimization)
Linear programming
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#np-linear-programming)
Random number generation
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#np-random-number-generation)
Factoring and primality testing
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#np-factoring-primality)
Arbitrary-precision arithmetic
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#np-arithmetic)
Knapsack problem
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#np-knapsack)
Discrete Fourier transform
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#np-fourier)
Sorting
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#cp-sorting)
Searching
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#cp-searching)
Median and selection
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#cp-median-selection)
Generating permutations
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#cp-gen-permutations)
Generating subsets
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#cp-gen-subsets)
Generating partitions
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#cp-gen-partitions)
Generating graphs
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#cp-gen-graphs)
Calendrical calculations
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#cp-calendar)
Job scheduling
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#cp-job-scheduling)
Satisfiability
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#cp-satisfiability)
Connected components
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#gp-pt-connected-components)
Topological sorting
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#gp-pt-topological-sorting)
Minimum spanning tree
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#gp-pt-mst)
Shortest path
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#gp-pt-shortest-path)
Transitive closure and reduction
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#gp-pt-transitive)
Matching
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#gp-pt-matching)
Eulerian cycle/Chinese postman
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#gp-pt-eulerian-cycle)
Edge and vertex connectivity
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#gp-pt-edge-vertex-connectivity)
Network flow
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#gp-pt-network-flow)
Drawing graphs nicely
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#gp-pt-drawing-graphs)
Drawing trees
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#gp-pt-drawing-trees)
Planarity detection and embedding
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#gp-pt-planarity)
Clique
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#gp-np-clique)
Independent set
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#gp-np-independent-set)
Vertex cover
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#gp-np-vertex-cover)
Traveling salesman problem
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#gp-np-tsp)
Hamiltonian cycle
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#gp-np-hamiltonian)
Graph partition
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#gp-np-graph-partition)
Vertex coloring
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#gp-np-vertex-coloring)
Edge coloring
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#gp-np-edge-coloring)
Graph isomorphism
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#gp-np-graph-isomorphism)
Steiner tree
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#gp-np-steiner-tree)
Feedback edge/vertex set
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#gp-np-feedback)
Robust geometric primitives
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#cg-primitives)
Convex hull
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#cg-convex-hull)
Triangulation
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#cg-triangulation)
Voronoi diagrams
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#cg-voronoi)
Nearest-neighbor search
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#cg-nearest-neighbor)
Range search
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#cg-range-search)
Point location
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#cg-point-location)
Intersection detection
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#cg-intersection-detection)
Bin packing
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#cg-bin-packing)
Medial-axis transform
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#cg-medial-axis-transform)
Polygon partitioning
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#cg-polygon-partitioning)
Simplifying polygons
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#cg-simplifying-polygons)
Shape similarity
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#cg-shape-similarity)
Motion planning
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#cg-motion-planning)
Maintaining line arrangements
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#cg-line-arrangements)
Minkowski sum
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#cg-minkowski)
Set cover
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#ss-set-cover)
Set packing
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#ss-set-packing)
String matching
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#ss-string-matching)
Approximate string matching
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#ss-string-matching-approximate)
Text compression
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#ss-text-compression)
Cryptography
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#ss-cryptography)
Fininte state machine minimization
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#ss-finite-state)
Longest common substring/subsequence
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#ss-longest-common)
Shortest common superstring
[the catalog](/docs/books/algorithm-design-manual/algorithms-catalog#ss-shortest-common)
Dictionaries
![](/assets/images/ac-f1-0d5be4b739387980fb72f97dd523e2c5.png)
Input description: A set of records, each identified by one or more keys.
Problem description: Build and maintain a data structure to efficiently locate, insert, and delete the record associated with any query key .
Priority queues
![](/assets/images/ac-f2-37824419f720fe9b692226b09b632662.png)
Input description: A set of records with totally ordered keys.
Problem description: Build and maintain a data structure for providing quick access to the smallest or largest key in the set.
Suffix trees and arrays
![](/assets/images/ac-f3-202ee277d8eeba27c42c9a46a4ab3ad8.png)
Input description: A reference string .
Problem description: Build a data structure for quickly finding all places where an arbitrary query string occurs in .
Graph data structures
![](/assets/images/ac-f4-f19c54a5915556437ef340266f11802d.png)
Input description: A graph .
Problem description: Represent the graph using a flexible, efficient data structure.
Set data structures
![](/assets/images/ac-f5-82d20feb5b5979837f3e0e0650cd8193.png)
Input description: A universe of items on which is defined a collection of subsets .
Problem description: Represent each subset so as to efficiently
- test whether ,
- compute the union or intersection of and , and
- insert or delete members of .
Kd-trees
![](/assets/images/ac-f6-d628d767348345db3690d7c68a41aa99.png)
Input description: A set of points (or more complicated geometric objects) in dimensions.
Problem description: Construct a tree that partitions space by half-planes such that each object is contained in its own box-shaped region.
Numerical problems
Solving linear equations
![](/assets/images/ac-f7-e8b9337d278925d0b92a4732c9cb90f8.png)
Input description: An matrix and an vector , together representing linear equations on variables.
Problem description: What is the vector such that ?
Bandwidth reduction
![](/assets/images/ac-f8-b7fc0500325a60f796456643ca7c384f.png)
Input description: A graph , representing an matrix of zero and non-zero elements.
Problem description: Which permutation of the vertices minimizes the length of the longest edge--i.e., minimizes ?
Matrix multiplication
![](/assets/images/ac-f9-c6b68eab9af280b287eb7266942ad170.png)
Input description: An matrix and a matrix .
Problem description: Compute the matrix .
Determinants and permanents
![](/assets/images/ac-f10-f42a747031bc3092db879e25e37b1e28.png)
Input description: An matrix .
Problem description: What is the determinant or permanent of the matrix ?
Constrained/unconstrained optimization
![](/assets/images/ac-f11-7b916c4a0961e37a56104a07356e3427.png)
Input description: A function .
Problem description: Which point maximizes (or minimizes) the function ?
Linear programming
![](/assets/images/ac-f12-5cc2bfd4663407e966d0a9e8c49fca6c.png)
Input description: A set of linear inequalities on variables
and a linear optimization function .
Problem description: Which variable assignment maximizes the objective function while satisfying all inequalities ?
Random number generation
![](/assets/images/ac-f13-cb17d03f5d265d67d6075f0af46d8dd9.png)
Input description: Nothing, or perhaps a seed.
Problem description: Generate a sequence of random integers.
Factoring and primality testing
![](/assets/images/ac-f14-845536c1ca1fc74ea9af4d30e2e083b8.png)
Input description: An integer .
Problem description: Is a prime number? If not, what are its factors?
Arbitrary-precision arithmetic
![](/assets/images/ac-f15-56665bf31a37f3177b3f872ee08e1abd.png)
Input description: Two very large integers, and .
Problem description: What is , , , and ?
Knapsack problem
![](/assets/images/ac-f16-8ca89f8fedd7b271a8a4fdfa3afec7ad.png)
Input description: A set of items , where item has size and value . A knapsack capacity .
Problem description: Find the subset of that maximizes the value of given ; that is, all the items fit in a knapsack of size .
Discrete Fourier transform
![](/assets/images/ac-f17-1d769b9d09cce734b766a4fa30568bfb.png)
Input description: A sequence of real or complex values , , sampled at uniform intervals from a function .
Problem description: The discrete Fourier transform for .
Combinatorial problems
Sorting
![](/assets/images/ac-f18-57c3510b5ae330f85be24ae22f32e9d2.png)
Input description: A set of items.
Problem description: Arrange the items in increasing order.
Searching
![](/assets/images/ac-f19-621533c67d35083ba2452cbe774d77ab.png)
Input description: A set of keys , and a query key .
Problem description: Where is in ?
Median and selection
![](/assets/images/ac-f20-d0df49c81fee7baa60ad9602086de725.png)
Input description: A set of numbers or keys, and an integer .
Problem description: Find the key greater than or equal to exactly of the keys.
Generating permutations
![](/assets/images/ac-f21-a12b25292af12e4fa306d88e72b47856.png)
Input description: An integer .
Problem description: Generate
- all, or
- a random, or
- the next permutation of length .
Generating subsets
![](/assets/images/ac-f22-7fffa57b10d2058e2a3cd6531f503899.png)
Input description: An integer .
Problem description: Generate
- all, or
- a random, or
- the next subset of the integers .
Generating partitions
![](/assets/images/ac-f23-9872dcd2ecfdf94d3f93a6521c242521.png)
Input description: An integer .
Problem description: Generate
- all, or
- a random, or
- the next integer or set partitions of length .
Generating graphs
![](/assets/images/ac-f24-29406f82ec9373fcd267b4466fd87ae4.png)
Input description: Parameters describing the desired graph, including the number of vertices , and the number of edges or edge probability .
Problem description: Generate
- all, or
- a random, or
- the next graph satisfying the parameters.
Calendrical calculations
![](/assets/images/ac-f25-bc4f51e29e8f2908730ce2f839a1491b.png)
Input description: A particular calendar date : month, day, and year.
Problem description: Which day of the week did fall on according to the given calendar system?
Job scheduling
![](/assets/images/ac-f26-ca806c1118a4e38aca7d910cc0943f43.png)
Input description: A directed acyclic graph , with vertices representing jobs, and edge implies task must be done before task .
Problem description: Which schedule of tasks completes the job using the minimum amount of time or processors?
Satisfiability
![](/assets/images/ac-f27-b27feaae6c18f6a35ce70450f8ec935b.png)
Input description: A set of clauses in conjunctive normal form.
Problem description: Is there a truth assignment to the Boolean variables such that every clause is simultaneously satisfied?
Graph Problems - Polynomial Time
Connected components
![](/assets/images/ac-f28-27b106f7b3ec393c909234a398254c98.png)
Input description: A directed or undirected graph .
Problem description: Identify the different pieces or components of , where vertices and are in different components when no path exists from to in .
Topological sorting
![](/assets/images/ac-f29-84aac756a7044efb0a6a273b26362773.png)
Input description: A directed acyclic graph , also known as a partial order or poset.
Problem description: Find a linear ordering of the vertices of such that for each edge , vertex is to the left of vertex .
Minimum spanning tree
![](/assets/images/ac-f30-0b82fd434abca3ce9db7ad066e3201af.png)
Input description: A graph with weighted edges.
Problem description: Find a subset of edges that define a tree of minimum weight on .
Shortest path
![](/assets/images/ac-f31-99c9635bdaca1808d6240db1a9880ef1.png)
Input description: An edge-weighted graph , with vertices and .
Problem description: Find the shortest path from to in .
Transitive closure and reduction
![](/assets/images/ac-f32-57d8b1e4484bd40d51afac221775d67e.png)
Input description: A directed graph .
Problem description: For transitive closure, construct a graph with edge iff there is a directed path from to in . For transitive reduction, construct a graph with the smallest number of edges such that a directed path from to exists in iff there is a directed path from to in .
Matching
![](/assets/images/ac-f33-36b53bef65f97ad06cc1e39038eddfa3.png)
Input description: A (weighted) graph .
Problem description: Find the largest set of edges from such that every vertex in is incident to at most one edge of .
Eulerian cycle/Chinese postman
![](/assets/images/ac-f34-3b73f42574b63bc03faef6c9fb84ded6.png)
Input description: A graph .
Problem description: Find the shortest tour visiting every edge of .
Edge and vertex connectivity
![](/assets/images/ac-f35-e2e57158d8bbece6ae49d6b4faf7cd11.png)
Input description: A graph . Optionally, a pair of vertices and .
Problem description: What is the smallest subset of vertices (or edges) whose deletion will disconnect , or that will separate from ?
Network flow
![](/assets/images/ac-f36-6912497613bb0a29ccdbf8207cf45a0b.png)
Input description: A directed graph , where each edge has a capacity . A source node and sink node .
Problem description: What is the maximum flow you can route from to while respecting the capacity constraint of each edge?
Drawing graphs nicely
![](/assets/images/ac-f37-1f05c64f4c40c28699c2c29717bb625f.png)
Input description: A graph .
Problem description: Draw a graph to accurately reflect its structure.
Drawing trees
![](/assets/images/ac-f38-041b0f38ffc2e271c63a5e7fd727fceb.png)
Input description: A tree , which is a graph without any cycles.
Problem description: Create a nice drawing of the tree .
Planarity detection and embedding
![](/assets/images/ac-f39-4cb3b86759d7992923ef535b53f0f17d.png)
Input description: A graph .
Problem description: Can be drawn in the plane such that no two edges cross? If so, produce such a drawing.
Graph Problems - NP-Hard
Clique
![](/assets/images/ac-f40-efac7ffe2d2db40bcde6dea1fb52a5d8.png)
Input description: A graph .
Problem description: What is the largest subset of vertices such that all pairs are connected, that is, for all , ?
Independent set
![](/assets/images/ac-f41-ef61a499db9193183c0ad04a78d81f11.png)
Input description: A graph .
Problem description: What is the largest subset of vertices such that there is no edge where and ?
Vertex cover
![](/assets/images/ac-f42-7209c263043e0893063fc78e70077855.png)
Input description: A graph .
Problem description: What is the smallest subset such that every edge contains at least one vertex of ?
Traveling salesman problem
![](/assets/images/ac-f43-2bdc2a14338cb77c3c248ed9668dc17f.png)
Input description: A weighted graph .
Problem description: Find the cycle of minimum cost, visiting each vertex of exactly once.
Hamiltonian cycle
![](/assets/images/ac-f44-f129fa86dd138b5ceb5fc077d98b1573.png)
Input description: A graph .
Problem description: Find a tour of the vertices using only edges from , such that each vertex is visited exactly once.
Graph partition
![](/assets/images/ac-f45-6df90a4158caabb2c67db0bddc04810f.png)
Input description: A (weighted) graph and integers and .
Problem description: Partition the vertices into roughly equal-sized subsets such that the total cost of edges spanning the subsets is at most .
Vertex coloring
![](/assets/images/ac-f46-210d1f9d28b4781242d8f5cd4dd25fe8.png)
Input description: A graph .
Problem description: Color the vertices of using the minimum number of colors such that for all , vertices and have different colors.
Edge coloring
![](/assets/images/ac-f47-6e89f85458d78a79b169be1439dc460b.png)
Input description: A graph .
Problem description: What is the smallest set of colors needed to color the edges of such that no two edges of the same color share a common vertex?
Graph isomorphism
![](/assets/images/ac-f48-2d53de55f954dc79b92be7414f540126.png)
Input description: Two graphs, and .
Problem description: Find a mapping from the vertices of to the vertices of such that and are identical, that is, is an edge of iff is an edge of .
Steiner tree
![](/assets/images/ac-f49-091168bb7ea5da20e7d9d89eceef09ab.png)
Input description: A graph and specified subset of vertices . Or set of geometric points .
Problem description:
Feedback edge/vertex set
![](/assets/images/ac-f50-1534911d47228284900952ebcd1e858b.png)
Input description: A (directed) graph .
Problem description: What is the smallest set of edges or vertices whose deletion leaves an acyclic graph?
Computational geometry
Robust geometric primitives
![](/assets/images/ac-f51-1cddf562b4a0812b4c8371e5fe2c5c4b.png)
Input description: A point and line segment , or two segments , .
Problem description: Does lie on, over, or under ? Does intersect ?
Convex hull
![](/assets/images/ac-f52-631230ef0371080a22b40a61992dbed4.png)
Input description: A set of points in -dimensional space.
Problem description: Find the smallest convex polygon (or polyhedron) containing all the points of .
Triangulation
![](/assets/images/ac-f53-189144231ff68bb43725483a852aff41.png)
Input description: A set of points, a polygon, or a polyhedron.
Problem description: Partition the interior of the point set or polyhedron into triangles.
Voronoi diagrams
![](/assets/images/ac-f54-51cb088abd839b703176e94e401457f4.png)
Input description: A set of points .
Problem description: Decompose space into regions such that all points in the region around are closer to than to any other point in .
Nearest-neighbor search
![](/assets/images/ac-f55-94d13e7083480573aec92217d1683235.png)
Input description: A set of points in dimensions, and query point .
Problem description: Which point in is closest to ?
Range search
![](/assets/images/ac-f56-bcee72a9fbab385d4898a8017a566892.png)
Input description: A set of points in dimensions, and a query region .
Problem description: Which points in lie within ?
Point location
![](/assets/images/ac-f57-112132259379d144c96f78a8f33a6ad2.png)
Input description: A decomposition of the plane into polygonal regions, and a query point .
Problem description: Which region contains the query point ?
Intersection detection
![](/assets/images/ac-f58-8ceebff56c092a21b177e076891b60a6.png)
Input description: A set of lines and line segments , or a pair of polygons or polyhedra and .
Problem description: Which pairs of line segments intersect each other? What is the intersection of and .
Bin packing
![](/assets/images/ac-f59-5121986d0f0fe88112b3d6924fb6fb85.png)
Input description: A set of items with sizes . A set of bins with capacities .
Problem description: Store all the items using the fewest number of bins.
Medial-axis transform
![](/assets/images/ac-f60-bd2031a8ad10db67a12a5aa1d760ebd5.png)
Input description: A polygon or polyhedron .
Problem description: Find the skeleton of , the set of points that have more than one closest point on the boundary of .
Polygon partitioning
![](/assets/images/ac-f61-1e9fbf26870d017d09aac9ba33d8f5ea.png)
Input description: A polygon or polyhedron .
Problem description: Partition into a small number of simple (typically convex) pieces.
Simplifying polygons
![](/assets/images/ac-f62-66b26dfbc8de70ffca1b03accb6ca1c2.png)
Input description: A polygon or polyhedron , with vertices.
Problem description: Find a polygon or polyhedron containing only vertices, such that the shape of is as close as possible to .
Shape similarity
![](/assets/images/ac-f63-0075908354b82987d28a65ac5c1eb732.png)
Input description: Two polygonal shapes, and .
Problem description: How similar are and .
Motion planning
![](/assets/images/ac-f64-13edf50974b1198f507e67f9088a0a61.png)
Input description: A polygonal-shaped robot starting at position in a room containing polygonal obstacles, and a goal position .
Problem description: Find the shortest route taking to without intersecting any obstacles.
Maintaining line arrangements
![](/assets/images/ac-f65-44c9cf9c3306495ad164b66395ac0030.png)
Input description: A set of lines .
Problem description: What is the decomposition of the plane defined by .
Minkowski sum
![](/assets/images/ac-f66-6c94069d72e504b26f51d1156e650331.png)
Input description: Point sets or polygons and , containing $$ and vertices respectively.
Problem description: What is the convolution of and , that is, the Minkowski sum ?
Set and string problems
Set cover
![](/assets/images/ac-f67-fd6db9ac61e57b8257c3dbd47709e1ac.png)
Input description: A collection of subsets of the universal set .
Problem description: What is the smallest subset of whose union equals the universal set, that is,
Set packing
![](/assets/images/ac-f68-81cd5474950dba284c61a7f5bee7cb15.png)
Input description: A collection of subsets of the universal set .
Problem description: Select a small collection of mutually disjoint subsets from whose union is the universal set.
String matching
![](/assets/images/ac-f69-791b3e3966636b665dc74f7f04acb30a.png)
Input description: A text string of length . A pattern of length .
Problem description: Find an/all instances of pattern in the text.
Approximate string matching
![](/assets/images/ac-f70-7dea95902cac99cbd445eb1b3370823f.png)
Input description: A text string and a pattern string .
Problem description: What is the minimum-cost way to transform to using insertions, deletions, and substitutions?
Text compression
![](/assets/images/ac-f71-6a679803975edc9ebc06dd079009cedd.png)
Input description: A text string .
Problem description: Create a shorter text string such that can be correctly reconstructed from .
Cryptography
![](/assets/images/ac-f72-2f8f7b3ded2d69784c3eff080bcc9dfa.png)
Input description: A plaintext message or encrypted text , and key .
Problem description: Encode using giving , or decode giving .
Fininte state machine minimization
![](/assets/images/ac-f73-976ecfe535bfbd52ec898ac965450196.png)
Input description: A deterministic finite automaton .
Problem description: Create the smallest deterministic finite automaton such that behaves identically to .
Longest common substring/subsequence
![](/assets/images/ac-f74-d00acf06d8af38145c98c4d5516146ae.png)
Input description: A set of strings .
Problem description: What is the longest string such that all the characters of appear as a substring or subsequence of each , ?
Shortest common superstring
![](/assets/images/ac-f75-e000e364020c5fa0bdbd60519b7dab89.png)
Input description: A set of strings .
Problem description: Find the shortest string that contains each string as a substring of .