This is the list from There Are 75 Famous Problems ,
with one line of Input and Output for each problem. Many names do not tell
you what the problem is.
These are my own short versions, not the originals. The exact definitions are
in each entry of the Stony Brook Algorithm Repository (algorist.com).
Problem In Out
Dictionaries n records, each with a key a structure that finds, inserts and deletes a record by its key Priority Queues records with ordered keys a structure that always hands back the smallest, and stays fast as records come and go Suffix Trees and Arrays a reference string a structure that finds every place a query string sits inside it Graph Data Structures a graph a representation that is small to store and quick to walk Set Data Structures a universe of objects and a family of subsets a representation that tests membership and takes unions and intersections quickly Kd-Trees n points in k dimensions a tree splitting the space so each point sits in its own region
Problem In Out
Sorting n items the same items in increasing order Searching n keys and a query key where the query sits among them Median and Selection n numbers the one with half below it and half above Generating Permutations an integer n every ordering of n things, or a random one, or the next one Generating Subsets an integer n every subset of 1..n, or a random one, or the next one Generating Partitions an integer n every way to split n, or a random one, or the next one Generating Graphs a vertex count, an edge count, or an edge probability a graph that meets them — every such graph, a random one, or the next Calendrical Calculations a month, a day and a year the weekday it fell on Job Scheduling jobs with "this one before that one" constraints a schedule finishing in the least time, or on the fewest machines Satisfiability clauses built from ands, ors and nots on boolean variables whether some assignment makes every clause true
Problem In Out
Clique a graph the largest set of vertices all joined to each other Independent Set a graph the largest set of vertices with no edge between any two Vertex Cover a graph the smallest set of vertices touching every edge Traveling Salesman Problem a weighted graph the cheapest cycle through every vertex exactly once Hamiltonian Cycle a graph an order visiting every vertex exactly once Graph Partition a weighted graph, a size bound and a cost bound a split into parts no bigger than the size bound, cutting no more than the cost bound Vertex Coloring a graph a coloring of the vertices using the fewest colors, so that no two neighbors match Edge Coloring a graph the fewest colors for the edges so that edges meeting at a vertex differ Graph Isomorphism two graphs a relabeling that turns one graph into the other, if such a relabeling exists Steiner Tree a graph and a subset of its vertices the smallest tree connecting that subset Feedback Edge/Vertex Set a directed graph the fewest edges or vertices to remove so that no cycle is left
Problem In Out
Robust Geometric Primitives a point and a segment, or two segments which side the point is on, or whether the segments cross — without rounding errors giving a wrong answer Convex Hull n points the smallest convex polygon holding them all Triangulation a point set or a polyhedron its interior cut into triangles Voronoi Diagrams n points the region around each point closer to it than to any other Nearest Neighbor Search n points and a query point the closest one Range Search n points and a query polygon the points falling inside it Point Location a plane cut into regions, and a query point the region it falls in Intersection Detection segments, or two polygons which pairs cross, or the shape they share Bin Packing items with sizes, bins with capacities a packing using as few bins as possible Medial-Axis Transform a polygon the points inside that have more than one nearest point on the boundary — its skeleton Polygon Partitioning a polygon a cut into as few simple pieces as possible, usually convex ones Simplifying Polygons a polygon with n vertices one with fewer vertices that still looks like it Shape Similarity two shapes how alike they are Motion Planning a robot, a room with obstacles, a start and an end the shortest path that gets the robot across without hitting anything Maintaining Line Arrangements n lines and segments the cells, edges and vertices they cut the plane into Minkowski Sum two point sets or polygons every sum of a point from one and a point from the other