The Accumulator class is a data type for computing the running mean, sample standard deviation, and sample variance of a stream of real numbers. It provides an example of a mutable data type and a streaming algorithm.

This implementation uses a one-pass algorithm that is less susceptible to floating-point roundoff error than the more straightforward implementation based on saving the sum of the squares of the numbers. This technique is due to B. P. Welford. Each operation takes constant time in the worst case. The amount of memory is constant - the data values are not stored.

The AcyclicLP class represents a data type for solving the single-source longest paths problem in edge-weighted directed acyclic graphs (DAGs). The edge weights can be positive, negative, or zero.

This implementation uses a topological-sort based algorithm. The constructor takes time proportional to V + E, where V is the number of vertices and E is the number of edges. Afterwards, the DistTo() and HasPathTo() methods take constant time and the PathTo() method takes time proportional to the number of edges in the longest path returned.

The AcyclicSP class represents a data type for solving the single-source shortest paths problem in edge-weighted directed acyclic graphs (DAGs). The edge weights can be positive, negative, or zero.

This implementation uses a topological-sort based algorithm. The constructor takes time proportional to V + E, where V is the number of vertices and E is the number of edges. Afterwards, the DistTo() and HasPathTo() methods take constant time and the PathTo() method takes time proportional to the number of edges in the shortest path returned.

The AdjMatrixEdgeWeightedDigraph class represents a edge-weighted digraph of vertices named 0 through V - 1, where each directed edge is of type and has a real-valued weight. It supports the following two primary operations: add a directed edge to the digraph and iterate over all of edges incident from a given vertex. It also provides methods for returning the number of vertices V and the number of edges E. Parallel edges are disallowed; self-loops are permitted.

This implementation uses an adjacency-matrix representation. All operations take constant time (in the worst case) except iterating over the edges incident from a given vertex, which takes time proportional to V.

The Arbitrage class provides a client that finds an arbitrage opportunity in a currency exchange table by constructing a complete-digraph representation of the exchange table and then finding a negative cycle in the digraph.

This implementation uses the Bellman-Ford algorithm to find a negative cycle in the complete digraph. The running time is proportional to V³ in the worst case, where V is the number of currencies.

The AssignmentProblem class represents a data type for computing an optimal solution to an N-by-NAssignment problem. The assignment problem is to find a minimum weight matching in an edge-weighted complete bipartite graph.

The data type supplies methods for determining the optimal solution and the corresponding dual solution.

This implementation uses the Successive shortest paths algorithm. The order of growth of the running time in the worst case is O(N^3 log N) to solve an N-by-N instance.

The Bag class represents a bag (or multiset) of generic items. It supports insertion and iterating over the items in arbitrary order.

This implementation uses a singly-linked list with a nested, non-static class Node and hence is the same as the LinkedBag class in algs4.jar. The Add, IsEmpty, and Count operations take constant time. Iteration takes time proportional to the number of items.

The BellmanFordSP class represents a data type for solving the single-source shortest paths problem in edge-weighted digraphs with no negative cycles. The edge weights can be positive, negative, or zero. This class finds either a shortest path from the source vertex S to every other vertex or a negative cycle reachable from the source vertex.

This implementation uses the Bellman-Ford-Moore algorithm. The constructor takes time proportional to V (V + E) in the worst case, where V is the number of vertices and E is the number of edges. Afterwards, the distTo(), hasPathTo(), and hasNegativeCycle() methods take constant time; the pathTo() and negativeCycle() method takes time proportional to the number of edges returned.

The BinaryDump class provides a client for displaying the contents of a binary file in binary.

For more full-featured versions, see the Unix utilities od (octal dump) and hexdump (hexadecimal dump). See also .

Binary standard input. This class provides methods for reading in bits from standard input, either one bit at a time (as a boolean), 8 bits at a time (as a byte or char), 16 bits at a time (as a short), 32 bits at a time (as an int or float), or 64 bits at a time (as a double or long).

All primitive types are assumed to be represented using their standard .NET representations, in little-endian (least significant byte first) order.

The client should not intermix calls to BinaryStdIn with calls to StdIn or Console.In; otherwise unexpected behavior will result.

The BinaryInsertion class provides a static method for sorting an array using an optimized binary insertion sort with half exchanges.

This implementation makes ~ N lg N compares for any array of length N. However, in the worst case, the running time is quadratic because the number of array accesses can be proportional to N^2 (e.g, if the array is reverse sorted). As such, it is not suitable for sorting large arrays (unOrderHelper.Less the number of inversions is small).

The sorting algorithm is stable and uses O(1) extra memory.

Binary standard output. This class provides methods for converting primtive type variables (boolean, byte, char, int, long, float, and double) to sequences of bits and writing them to standard output. Uses .NET representations, in little-endian (least-significant byte first).

The client must Flush() the output stream when finished writing bits and should not intermixing calls to output with calls to Console or Console.Out; otherwise unexpected behavior will result.

The BinarySearch class provides a static method for binary searching for an integer in a sorted array of integers.

The Rank operations takes logarithmic time in the worst case.

The BST class represents an ordered symbol table of generic key-value pairs. It supports the usual Put, Get, Indexer, Contains, Delete, Count, and IsEmpty methods. It also provides ordered methods for finding the Minimum, Maximum, Floor, and Ceiling. It also provides a Keys method for iterating over all of the keys. A symbol table implements the Associative array abstraction: when associating a value with a key that is already in the symbol table, the convention is to replace the old value with the new value. Unlike DictionaryTKey, TValue, this class uses the convention that values cannot be null. Setting the value associated with a key to null is equivalent to deleting the key from the symbol table.

This implementation uses a sorted array. It requires that the key type implements the IComparable interface and calls the CompareTo() method to compare two keys. It does not call either Equals() or GetHashCode(). The Put and Remove operations each take linear time in the worst case; the Contains, Ceiling, Floor, and Rank operations take logarithmic time; the Count, IsEmpty, Minimum, Maximum, and indexer operations take constant time. Construction takes constant time.

The Bipartite class represents a data type for determining whether an undirected graph is bipartite or whether it has an odd-length cycle. The IsBipartite operation determines whether the graph is bipartite. If so, the Color operation determines a bipartition; if not, the OddCycle operation determines a cycle with an odd number of edges.

This implementation uses depth-first search. The constructor takes time proportional to V + E (in the worst case), where V is the number of vertices and E is the number of edges. Afterwards, the IsBipartite and Color operations take constant time; the OddCycle operation takes time proportional to the length of the cycle.

See for a nonrecursive version that uses breadth-first search.

The BipartiteMatching class represents a data type for computing a Maximum (cardinality) matching and a Minimum (cardinality) vertex cover in a bipartite graph.

A Bipartite graph in a graph whose vertices can be partitioned into two disjoint sets such that every edge has one endpoint in either set. A Matching in a graph is a subset of its edges with no common vertices. A Maximum matching is a matching with the maximum number of edges. A Perfect matching is a matching which matches all vertices in the graph. A Vertex cover in a graph is a subset of its vertices such that every edge is incident to at least one vertex. A Minimum vertex cover is a vertex cover with the minimum number of vertices. By Konig's theorem, in any biparite graph, the maximum number of edges in matching equals the minimum number of vertices in a vertex cover.

The maximum matching problem in Nonbipartite graphs is also important, but all known algorithms for this more general problem are substantially more complicated.

This implementation uses the Alternating path algorithm. It is equivalent to reducing to the maximum flow problem and running the augmenting path algorithm on the resulting flow network, but it does so with less overhead. The order of growth of the running time in the worst case is (E + V) V, where E is the number of edges and V is the number of vertices in the graph. It uses extra space (not including the graph) proportional to V.

See also , which solves the problem in O(E sqrt(V)) using the Hopcroft-Karp algorithm and BipartiteMatchingToMaxflow, which solves the problem in O(E V) time via a reduction to maxflow.

The BipartiteX class represents a data type for determining whether an undirected graph is bipartite or whether it has an odd-length cycle. The IsBipartite operation determines whether the graph is bipartite. If so, the Color operation determines a bipartition; if not, the OddCycle operation determines a cycle with an odd number of edges.

This implementation uses breadth-first search and is nonrecursive. The constructor takes time proportional to V + E (in the worst case), where V is the number of vertices and E is the number of edges. Afterwards, the IsBipartite and Color operations take constant time; the OddCycle operation takes time proportional to the length of the cycle. See for a recursive version that uses depth-first search.

The BoruvkaMST class represents a data type for computing a Minimum spanning tree in an edge-weighted graph. The edge weights can be positive, zero, or negative and need not be distinct. If the graph is not connected, it computes a Minimum spanning forest, which is the union of minimum spanning trees in each connected component. The Weight method returns the weight of a minimum spanning tree and the Edges() method returns its edges.

This implementation uses Boruvka's algorithm and the union-find data type.

The constructor takes time proportional to E log V and extra space (not including the graph) proportional to V, where V is the number of vertices and E is the number of edges. Afterwards, the weight() method takes constant time and the edges() method takes time proportional to V.

The BoyerMoore class finds the first occurrence of a pattern string in a text string.

This implementation uses the Boyer-Moore algorithm (with the bad-character rule, but not the strong good suffix rule).

The BreadthDirectedFirstPaths class represents a data type for finding shortest paths (number of edges) from a source vertex S (or set of source vertices) to every other vertex in the digraph.

This implementation uses breadth-first search. The constructor takes time proportional to V + E, where V is the number of vertices and E is the number of edges. It uses extra space (not including the digraph) proportional to V.

The BreadthFirstPaths class represents a data type for finding shortest paths (number of edges) from a source vertex S (or a set of source vertices) to every other vertex in an undirected graph.

This implementation uses breadth-first search. The constructor takes time proportional to V + E, where V is the number of vertices and E is the number of edges. It uses extra space (not including the graph) proportional to V.

The BST class represents an ordered symbol table of generic key-value pairs. It supports the usual Put, Get, Indexer, Contains, Delete, Count, and IsEmpty methods. It also provides ordered methods for finding the Minimum, Maximum, Floor, Select, Ceiling. It also provides a Keys method for iterating over all of the keys. A symbol table implements the Associative array abstraction: when associating a value with a key that is already in the symbol table, the convention is to replace the old value with the new value. Unlike DictionaryTKey, TValue, this class uses the convention that values cannot be null. Setting the value associated with a key to null is equivalent to deleting the key from the symbol table.

This implementation uses an (unbalanced) binary search tree. It requires that the key type implements the Comparable interface and calls the CompareTo() and method to compare two keys. It does not call either Equals() or GetHashCode(). The Put, Contains, Remove, Minimum, Maximum, Ceiling, Floor, Select, and Rank operations each take linear time in the worst case, if the tree becomes unbalanced. The Count, and IsEmpty operations take constant time. Construction takes constant time.

The BTree class represents an ordered symbol table of generic key-value pairs. It supports the Put, Get, IndexerContains, Count, and IsEmpty methods.

A symbol table implements the Associative array abstraction: when associating a value with a key that is already in the symbol table, the convention is to replace the old value with the new value. Unlike DictionaryTKey, TValue, this class uses the convention that values cannot be null. Setting the value associated with a key to null is equivalent to deleting the key from the symbol table.

This implementation uses a B-tree. It requires that the key type implements the IComparable interface and calls the CompareTo() and method to compare two keys. It does not call either Equals() or GetHashCode(). The Get, Put, and Contains operations each make log_M(N) probes in the worst case, where N is the number of key-value pairs and M is the branching factor. The Count, and IsEmpty operations take constant time. Construction takes constant time.

The CC class represents a data type for determining the connected components in an undirected graph. The Id operation determines in which connected component a given vertex lies; the Connected operation determines whether two vertices are in the same connected component; the Count operation determines the number of connected components; and the Count operation determines the number of vertices in the connect component containing a given vertex. The Component identifier of a connected component is one of the vertices in the connected component: two vertices have the same component identifier if and only if they are in the same connected component.

This implementation uses depth-first search. The constructor takes time proportional to V + E (in the worst case), V is the number of vertices and E is the number of edges. Afterwards, the Id, Count, Connected, and Count operations take constant time.

The ClosestPair data type computes a closest pair of points in a set of N points in the plane and provides accessor methods for getting the closest pair of points and the distance between them. The distance between two points is their Euclidean distance.

This implementation uses a divide-and-conquer algorithm. It runs in O(N log N) time in the worst case and uses O(N) extra space. See also .

The CPM class provides a client that solves the parallel precedence-constrained job scheduling problem via the Critical path method. It reduces the problem to the longest-paths problem in edge-weighted DAGs. It builds an edge-weighted digraph (which must be a DAG) from the job-scheduling problem specification, finds the longest-paths tree, and computes the longest-paths lengths (which are precisely the start times for each job).

This implementation uses to find a longest path in a DAG. The running time is proportional to V + E, where V is the number of jobs and E is the number of precedence constraints.

The Cycle class represents a data type for determining whether an undirected graph has a cycle. The HasCycle operation determines whether the graph has a cycle and, if so, the GetCycle operation returns one.

This implementation uses depth-first search. The constructor takes time proportional to V + E (in the worst case), where V is the number of vertices and E is the number of edges. Afterwards, the HasCycle operation takes constant time; the Cycle operation takes time proportional to the length of the cycle.

The DegreesOfSeparation class provides a client for finding the degree of separation between one distinguished individual and every other individual in a social network. As an example, if the social network consists of actors in which two actors are connected by a link if they appeared in the same movie, and Kevin Bacon is the distinguished individual, then the client computes the Kevin Bacon number of every actor in the network.

The running time is proportional to the number of individuals and connections in the network. If the connections are given implicitly, as in the movie network example (where every two actors are connected if they appear in the same movie), the efficiency of the algorithm is improved by allowing both movie and actor vertices and connecting each movie to all of the actors that appear in that movie.

The DepthFirstDirectedPaths class represents a data type for finding directed paths from a source vertex S to every other vertex in the digraph.

This implementation uses depth-first search. The constructor takes time proportional to V + E, where V is the number of vertices and E is the number of edges. It uses extra space (not including the graph) proportional to V.

The DepthFirstOrder class represents a data type for determining depth-first search ordering of the vertices in a digraph or edge-weighted digraph, including preorder, postorder, and reverse postorder.

This implementation uses depth-first search. The constructor takes time proportional to V + E (in the worst case), where V is the number of vertices and E is the number of edges. Afterwards, the Preorder, Postorder, and Reverse postorder operation takes take time proportional to V.

The DepthFirstPaths class represents a data type for finding paths from a source vertex S to every other vertex in an undirected graph.

This implementation uses depth-first search. The constructor takes time proportional to V + E, where V is the number of vertices and E is the number of edges. It uses extra space (not including the graph) proportional to V.

The DepthFirstSearch class represents a data type for determining the vertices connected to a given source vertex S in an undirected graph. For versions that find the paths, see and . This implementation uses depth-first search.

The constructor takes time proportional to V + E (in the worst case), where V is the number of vertices and E is the number of edges. It uses extra space (not including the graph) proportional to V.

The Digraph class represents a directed graph of vertices named 0 through V - 1. It supports the following two primary operations: add an edge to the digraph, iterate over all of the vertices adjacent from a given vertex. Parallel edges and self-loops are permitted.

This implementation uses an adjacency-lists representation, which is a vertex-indexed array of objects. All operations take constant time (in the worst case) except iterating over the vertices adjacent from a given vertex, which takes time proportional to the number of such vertices.

The DijkstraAllPairsSP class represents a data type for solving the all-pairs shortest paths problem in edge-weighted digraphs where the edge weights are nonnegative.

This implementation runs Dijkstra's algorithm from each vertex. The constructor takes time proportional to V (E log V) and uses space proprtional to V², where V is the number of vertices and E is the number of edges. Afterwards, the Dist() and hasPath() methods take constant time and the Path() method takes time proportional to the number of edges in the shortest path returned.

The DijkstraSP class represents a data type for solving the single-source shortest paths problem in edge-weighted digraphs where the edge weights are nonnegative.

This implementation uses Dijkstra's algorithm with a binary heap. The constructor takes time proportional to E log V, where V is the number of vertices and E is the number of edges. Afterwards, the DistTo() and HasPathTo() methods take constant time and the PathTo() method takes time proportional to the number of edges in the shortest path returned.

The DijkstraUndirectedSP class represents a data type for solving the single-source shortest paths problem in edge-weighted graphs where the edge weights are nonnegative.

This implementation uses Dijkstra's algorithm with a binary heap. The constructor takes time proportional to E log V, where V is the number of vertices and E is the number of edges. Afterwards, the DistTo() and HasPathTo() methods take constant time and the PathTo() method takes time proportional to the number of edges in the shortest path returned.

See for a version on edge-weighted digraphs.

The DirectedCycle class represents a data type for determining whether a digraph has a directed cycle. The HasCycle operation determines whether the digraph has a directed cycle and, and of so, the Cycle operation returns one.

This implementation uses depth-first search. The constructor takes time proportional to V + E (in the worst case), where V is the number of vertices and E is the number of edges. Afterwards, the HasCycle operation takes constant time; the Cycle operation takes time proportional to the length of the cycle.

See to compute a topological order if the digraph is acyclic.

The DirectedCycleX class represents a data type for determining whether a digraph has a directed cycle. The HasCycle operation determines whether the digraph has a directed cycle and, and of so, the Cycle operation returns one.

This implementation uses a nonrecursive, queue-based algorithm. The constructor takes time proportional to V + E (in the worst case), where V is the number of vertices and E is the number of edges. Afterwards, the HasCycle operation takes constant time; the Cycle operation takes time proportional to the length of the cycle.

See for a recursive version that uses depth-first search. See or to compute a topological order when the digraph is acyclic.

The DirectedDFS class represents a data type for determining the vertices reachable from a given source vertex S (or set of source vertices) in a digraph. For versions that find the paths, see and .

This implementation uses depth-first search. The constructor takes time proportional to V + E (in the worst case), where V is the number of vertices and E is the number of edges.

The DirectedEulerianCycle class represents a data type for finding an Eulerian cycle or path in a digraph. An Eulerian cycle is a cycle (not necessarily simple) that uses every edge in the digraph exactly once.

This implementation uses a nonrecursive depth-first search. The constructor runs in O(E + V) time, and uses O(V) extra space, where E is the number of edges and V the number of vertices All other methods take O(1) time.

To compute Eulerian paths in digraphs, see . To compute Eulerian cycles and paths in undirected graphs, see and .

The DirectedEulerianPath class represents a data type for finding an Eulerian path in a digraph. An Eulerian path is a path (not necessarily simple) that uses every edge in the digraph exactly once.

This implementation uses a nonrecursive depth-first search. The constructor runs in O(E + V) time, and uses O(V) extra space, where E is the number of edges and V the number of vertices All other methods take O(1) time.

To compute Eulerian cycles in digraphs, see . To compute Eulerian cycles and paths in undirected graphs, see and .

The DrawingWindow class provides a basic capability for creating drawings in a .NET environment using Windows Presentation Foundation (WPF) classes. It allows you to create drawings consisting of points, lines, squares, circles, and other geometric shapes in a window to save the drawings to a file. The class also includes facilities for text, color, pictures, and simple animation.

The coordinate system follows Windows convention, meaning that an x,y coordinate starts from the top-left corner, with the y axis oriented downward.

The API is modeled after the StdDraw class with necessary adaptation for the Windows environment.

The EdgeWeightedDigraph class represents a edge-weighted digraph of vertices named 0 through V - 1, where each directed edge is of type and has a real-valued weight. It supports the following two primary operations: add a directed edge to the digraph and iterate over all of edges incident from a given vertex. It also provides methods for returning the number of vertices V and the number of edges E. Parallel edges and self-loops are permitted.

This implementation uses an adjacency-lists representation, which is a vertex-indexed array of BagItem objects. All operations take constant time (in the worst case) except iterating over the edges incident from a given vertex, which takes time proportional to the number of such edges.

The EdgeWeightedDirectedCycle class represents a data type for determining whether an edge-weighted digraph has a directed cycle. The HasCycle operation determines whether the edge-weighted digraph has a directed cycle and, if so, the Cycle operation returns one.

This implementation uses depth-first search. The constructor takes time proportional to V + E (in the worst case), where V is the number of vertices and E is the number of edges. Afterwards, the HasCycle operation takes constant time; the Cycle operation takes time proportional to the length of the cycle.

See to compute a topological order if the edge-weighted digraph is acyclic.

The EdgeWeightedGraph class represents an edge-weighted graph of vertices named 0 through V - 1, where each undirected edge is of type and has a real-valued weight. It supports the following two primary operations: add an edge to the graph, iterate over all of the edges incident to a vertex. It also provides methods for returning the number of vertices V and the number of edges E. Parallel edges and self-loops are permitted.

This implementation uses an adjacency-lists representation, which is a vertex-indexed array of @link{Bag} objects. All operations take constant time (in the worst case) except iterating over the edges incident to a given vertex, which takes time proportional to the number of such edges.

The EulerianCycle class represents a data type for finding an Eulerian cycle or path in a graph. An Eulerian cycle is a cycle (not necessarily simple) that uses every edge in the graph exactly once.

This implementation uses a nonrecursive depth-first search. The constructor runs in O(E + V) time, and uses O(E + V) extra space, where E is the number of edges and V the number of vertices All other methods take O(1) time.

To compute Eulerian paths in graphs, see . To compute Eulerian cycles and paths in digraphs, see and .

The EulerianPath class represents a data type for finding an Eulerian path in a graph. An Eulerian path is a path (not necessarily simple) that uses every edge in the graph exactly once.

This implementation uses a nonrecursive depth-first search. The constructor runs in O(E + V) time, and uses O(E + V) extra space, where E is the number of edges and V the number of vertices All other methods take O(1) time.

To compute Eulerian cycles in graphs, see . To compute Eulerian cycles and paths in digraphs, see and .

The FarthestPair data type computes the farthest pair of points in a set of N points in the plane and provides accessor methods for getting the farthest pair of points and the distance between them. The distance between two points is their Euclidean distance.

This implementation computes the convex hull of the set of points and uses the rotating calipers method to find all antipodal point pairs and the farthest pair. It runs in O(N log N) time in the worst case and uses O(N) extra space. See also and .

The FFT class provides methods for computing the FFT (Fast-Fourier Transform), inverse FFT, linear convolution, and circular convolution of a complex array.

It is a bare-bones implementation that runs in N log N time, where N is the length of the complex array. For simplicity, N must be a power of 2.

Our goal is to optimize the clarity of the code, rather than performance. It is not the most memory efficient implementation because it uses objects to represents complex numbers and it it re-allocates memory for the subarray, instead of doing in-place or reusing a single temporary array.

The FlowNetwork class represents a capacitated network with vertices named 0 through V - 1, where each directed edge is of type and has a real-valued capacity and flow.

It supports the following two primary operations: add an edge to the network, iterate over all of the edges incident to or from a vertex. It also provides methods for returning the number of vertices V and the number of edges E. Parallel edges and self-loops are permitted.

This implementation uses an adjacency-lists representation, which is a vertex-indexed array of BagItem objects. All operations take constant time (in the worst case) except iterating over the edges incident to a given vertex, which takes time proportional to the number of such edges.

The FloydWarshall class represents a data type for solving the all-pairs shortest paths problem in edge-weighted digraphs with no negative cycles. The edge weights can be positive, negative, or zero. This class finds either a shortest path between every pair of vertices or a negative cycle.

This implementation uses the Floyd-Warshall algorithm. The constructor takes time proportional to V³ in the worst case, where V is the number of vertices. Afterwards, the Dist(), HasPath(), and HasNegativeCycle() methods take constant time; the Path() and GetNegativeCycle() method takes time proportional to the number of edges returned.

The FordFulkerson class represents a data type for computing a Maximum st-flow and Minimum st-cut in a flow network.

This implementation uses the Ford-Fulkerson algorithm with the Shortest augmenting path heuristic. The constructor takes time proportional to E V (E + V) in the worst case and extra space (not including the network) proportional to V, where V is the number of vertices and E is the number of edges. In practice, the algorithm will run much faster. Afterwards, the inCut() and value() methods take constant time.

If the capacities and initial flow values are all integers, then this implementation guarantees to compute an integer-valued maximum flow. If the capacities and floating-point numbers, then floating-point roundoff error can accumulate.

The GabowSCC class represents a data type for determining the strong components in a digraph. The Id operation determines in which strong component a given vertex lies; the AreStronglyConnected operation determines whether two vertices are in the same strong component; and the Count operation determines the number of strong components.

The Component identifier of a component is one of the vertices in the strong component: two vertices have the same component identifier if and only if they are in the same strong component.

This implementation uses the Gabow's algorithm. The constructor takes time proportional to V + E (in the worst case), where V is the number of vertices and E is the number of edges. Afterwards, the Id, Count, and AreStronglyConnected operations take constant time.

For alternate implementations of the same API, see and .

The GaussianElimination data type provides methods to solve a linear system of equations Ax = B, where A is an M-by-N matrix and B is a length N vector.

This is a bare-bones implementation that uses Gaussian elimination with partial pivoting. See GaussianEliminationLite.java for a stripped-down version that assumes the matrix A is square and nonsingular. See for an alternate implementation that uses Gauss-Jordan elimination. For an industrial-strength numerical linear algebra library, see JAMA.

The GaussJordanElimination data type provides methods to solve a linear system of equations Ax = B, where A is an N-by-N matrix and B is a length N vector. If no solution exists, it finds a solution Y to YA = 0, Yb != 0, which which serves as a certificate of infeasibility.

This implementation uses Gauss-Jordan elimination with partial pivoting. See for an implementation that uses Gaussian elimination (but does not provide the certificate of infeasibility). For an industrial-strength numerical linear algebra library, see JAMA.

The GrahamScan data type provides methods for computing the convex hull of a set of N points in the plane.

The implementation uses the Graham-Scan convex hull algorithm. It runs in O(N log N) time in the worst case and uses O(N) extra memory.

The Graph class represents an undirected graph of vertices named 0 through V - 1. It supports the following two primary operations: add an edge to the graph, iterate over all of the vertices adjacent to a vertex. It also provides methods for returning the number of vertices V and the number of edges E. Parallel edges and self-loops are permitted.

This implementation uses an adjacency-lists representation, which is a vertex-indexed array of objects. All operations take constant time (in the worst case) except iterating over the vertices adjacent to a given vertex, which takes time proportional to the number of such vertices.

The HexDump class provides a client for displaying the contents of a binary file in hexadecimal.

See also . For more full-featured versions, see the Unix utilities od (octal dump) and hexdump (hexadecimal dump).

The HopcroftKarp class represents a data type for computing a Maximum (cardinality) matching and a Minimum (cardinality) vertex cover in a bipartite graph. A Bipartite graph in a graph whose vertices can be partitioned into two disjoint sets such that every edge has one endpoint in either set. A Matching in a graph is a subset of its edges with no common vertices. A Maximum matching is a matching with the maximum number of edges.

A Perfect matching is a matching which matches all vertices in the graph. A Vertex cover in a graph is a subset of its vertices such that every edge is incident to at least one vertex. A Minimum vertex cover is a vertex cover with the minimum number of vertices. By Konig's theorem, in any biparite graph, the maximum number of edges in matching equals the minimum number of vertices in a vertex cover. The maximum matching problem in Nonbipartite graphs is also important, but all known algorithms for this more general problem are substantially more complicated.

This implementation uses the Hopcroft-Karp algorithm. The order of growth of the running time in the worst case is (E + V) sqrt(V), where E is the number of edges and V is the number of vertices in the graph. It uses extra space (not including the graph) proportional to V.

See also , which solves the problem in O(E V) time using the Alternating path algorithm and BipartiteMatchingToMaxflow, which solves the problem in O(E V) time via a reduction to the maxflow problem.

The IndexMaxPQ class represents an indexed priority queue of generic keys. It supports the usual Insert and Delete-the-maximum operations, along with Delete and Change-the-key methods. In order to let the client refer to items on the priority queue, an integer between 0 and maxN-1 is associated with each key. The client uses this integer to specify which key to delete or change. It also supports methods for peeking at a maximum key, testing if the priority queue is empty, and iterating through the keys.

This implementation uses a binary heap along with an array to associate keys with integers in the given range. The Insert, Delete-the-maximum, Delete, Change-key, Decrease-key, and Increase-key operations take logarithmic time. The IsEmpty, Count, Max-index, Max-key, and Key-of operations take constant time. Construction takes time proportional to the specified capacity.

The IndexMinPQ class represents an indexed priority queue of generic keys. It supports the usual Insert and Delete-the-minimum operations, along with Delete and Change-the-key methods. In order to let the client refer to keys on the priority queue, an integer between 0 and maxN-1 is associated with each key-the client uses this integer to specify which key to delete or change. It also supports methods for peeking at the minimum key, testing if the priority queue is empty, and iterating through the keys.

This implementation uses a binary heap along with an array to associate keys with integers in the given range. The Insert, Delete-the-minimum, Delete, Change-key, Decrease-key, and Increase-key operations take logarithmic time. The Is-empty, Count, Min-index, Min-key, and Key-of operations take constant time. Construction takes time proportional to the specified capacity.

The Insertion class provides static methods for sorting an array using insertion sort.

This implementation makes ~ 1/2 N^2 compares and OrderHelper.Exchanges in the worst case, so it is not suitable for sorting large arbitrary arrays. More precisely, the number of OrderHelper.Exchanges is exactly equal to the number of inversions. So, for example, it sorts a partially-sorted array in linear time.

The sorting algorithm is stable and uses O(1) extra memory.

See InsertionPedantic.java for a version that eliminates the compiler warning.

The KMP class finds the first occurrence of a pattern string in a text string.

This implementation uses a version of the Knuth-Morris-Pratt substring search algorithm. The version takes time as space proportional to N + M R in the worst case, where N is the length of the text string, M is the length of the pattern, and R is the alphabet size.

The Knuth class provides a client for reading in a sequence of strings and Shuffling them using the Knuth (or Fisher-Yates) shuffling algorithm. This algorithm guarantees to rearrange the elements in uniformly random order, under the assumption that Math.random() generates independent and uniformly distributed numbers between 0 and 1.

See for versions that shuffle arrays and subarrays of objects, doubles, and ints.

The KosarajuSharirSCC class represents a data type for determining the strong components in a digraph. The Id operation determines in which strong component a given vertex lies; the AreStronglyConnected operation determines whether two vertices are in the same strong component; and the Count operation determines the number of strong components. The Component identifier of a component is one of the vertices in the strong component: two vertices have the same component identifier if and only if they are in the same strong component.

This implementation uses the Kosaraju-Sharir algorithm. The constructor takes time proportional to V + E (in the worst case), where V is the number of vertices and E is the number of edges. Afterwards, the Id, Count, and AreStronglyConnected operations take constant time. For alternate implementations of the same API, see and .

The KruskalMST class represents a data type for computing a Minimum spanning tree in an edge-weighted graph. The edge weights can be positive, zero, or negative and need not be distinct. If the graph is not connected, it computes a Minimum spanning forest, which is the union of minimum spanning trees in each connected component. The weight() property returns the weight of a minimum spanning tree and the Edge() property returns its edges.

This implementation uses Krusal's algorithm and the union-find data type. The constructor takes time proportional to E log E and extra space (not including the graph) proportional to V, where V is the number of vertices and E is the number of edges. Afterwards, the Weight property takes constant time and the Edges method takes time proportional to V.

For alternate implementations, see , , and .

The LazyPrimMST class represents a data type for computing a Minimum spanning tree in an edge-weighted graph. The edge weights can be positive, zero, or negative and need not be distinct. If the graph is not connected, it computes a Minimum spanning forest, which is the union of minimum spanning trees in each connected component. The weight() method returns the weight of a minimum spanning tree and the edges() method returns its edges.

This implementation uses a lazy version of Prim's algorithm with a binary heap of edges. The constructor takes time proportional to E log E and extra space (not including the graph) proportional to E, where V is the number of vertices and E is the number of edges. Afterwards, the weight() method takes constant time and the edges() method takes time proportional to V.

For alternate implementations, see , , and .

The LinearProbingHashST class represents a symbol table of generic key-value pairs. It supports the usual Put, Get, Indexer, Contains, Delete, Count, and IsEmpty methods. It also provides a Keys method for iterating over all of the keys. A symbol table implements the Associative array abstraction: when associating a value with a key that is already in the symbol table, the convention is to replace the old value with the new value. Unlike DictionaryTKey, TValue, this class uses the convention that values cannot be null. Setting the value associated with a key to null is equivalent to deleting the key from the symbol table.

This implementation uses a linear probing hash table. It requires that the key type overrides the Equals() and GetHashCode() methods. The expected time per Put, Contains, or Remove operation is constant, subject to the uniform hashing assumption. The Count, and IsEmpty operations take constant time. Construction takes constant time.

The LinearProgramming class represents a data type for solving a linear program of the form { max cx : Ax <= b, x >= 0 }, where A is a M-by-N matrix, b is an M-length vector, and c is an N-length vector. For simplicity, we assume that A is of full rank and that b >= 0 so that x = 0 is a basic feasible soution.

The data type supplies methods for determining the optimal primal and dual solutions.

This is a bare-bones implementation of the Simplex algorithm. It uses Bland's rule to determing the entering and leaving variables. It is not suitable for use on large inputs. It is also not robust in the presence of floating-point roundoff error.

The LinkedQueue class represents a first-in-first-out (FIFO) queue of generic items. So named to avoid conflict with the .NET framwork QueueT class. Since C# does not allow an inner static class with instances, the implementation is effectively the same as the Queue class implementation.

It supports the usual Enqueue and Dequeue operations, along with methods for peeking at the first item, testing if the queue is empty, and iterating through the items in FIFO order.

This implementation uses a singly-linked list with a nested, non-static class Node and hence is the same as the Queue class in algs4.jar. The Enqueue, Dequeue, Peek, Count, and IsEmpty operations all take constant time in the worst case.

The LinkedStack class represents a last-in-first-out (LIFO) stack of generic items. So named to avoid conflict with the .NET framwork StackT class. Since C# strictly does not allow static class with instances, the implementation is effectively the same as the Stack class implementation.

It supports the usual Push and Pop operations, along with methods for peeking at the top item, testing if the stack is empty, and iterating through the items in LIFO order.

This implementation uses a singly-linked list with a nested, non-static class Node and hence is the same as the Stack class in algs4.jar. The Push, Pop, Peek, Count, and IsEmpty operations all take constant time in the worst case.

The LongestCommonSubstring class provides a client for computing the longest common substring that appears in two given strings.

This implementation computes the suffix array of each string and applies a merging operation to determine the longest common substring. For an alternate implementation, see LongestCommonSubstringConcatenate.java.

The MaxPQ class represents a priority queue of generic keys. It supports the usual Insert and Delete-the-maximum operations, along with methods for peeking at the maximum key, testing if the priority queue is empty, and iterating through the keys.

This implementation uses a binary heap. The Insert and Delete-the-maximum operations take logarithmic amortized time. The Max, Count, and IsEmpty operations take constant time. Construction takes time proportional to the specified capacity or the number of items used to initialize the data structure.

The MinPQ class represents a priority queue of generic keys. It supports the usual Insert and Delete-the-minimum operations, along with methods for peeking at the minimum key, testing if the priority queue is empty, and iterating through the keys.

This implementation uses a binary heap. The Insert and Delete-the-minimum operations take logarithmic amortized time. The Min, Count, and IsEmpty operations take constant time. Construction takes time proportional to the specified capacity or the number of items used to initialize the data structure.

The NFA class provides a data type for creating a Nondeterministic finite state automaton (NFA) from a regular expression and testing whether a given string is matched by that regular expression. It supports the following operations: Concatenation, Closure, Binary or, and Parentheses. It does not support Mutiway or, Character classes, Metacharacters (either in the text or pattern), Capturing capabilities, Greedy or Relucantant modifiers, and other features in industrial-strength implementations such as Regexand Match.

This implementation builds the NFA using a digraph and a stack and simulates the NFA using digraph search (see the textbook for details). The constructor takes time proportional to M, where M is the number of characters in the regular expression. The Recognizes method takes time proportional to M N, where N is the number of characters in the text.

The NonrecursiveDFS class represents a data type for finding the vertices connected to a source vertex S in the undirected graph.

This implementation uses a nonrecursive version of depth-first search with an explicit stack and the path tracing feature found in DepthFirstPaths. The constructor takes time proportional to V + E, where V is the number of vertices and E is the number of edges. It uses extra space (not including the graph) proportional to V.

The NonrecursiveDirectedDFS class represents a data type for finding the vertices reachable from a source vertex S in the digraph. This implementation uses a nonrecursive version of depth-first search with an explicit stack.

The constructor takes time proportional to V + E, where V is the number of vertices and E is the number of edges. It uses extra space (not including the digraph) proportional to V.

The PrimMST class represents a data type for computing a Minimum spanning tree in an edge-weighted graph. The edge weights can be positive, zero, or negative and need not be distinct. If the graph is not connected, it computes a Minimum spanning forest, which is the union of minimum spanning trees in each connected component. The Weight property returns the weight of a minimum spanning tree and the Edges property returns its edges.

This implementation uses Prim's algorithm with an indexed binary heap. The constructor takes time proportional to E log V and extra space (not including the graph) proportional to V, where V is the number of vertices and E is the number of edges. Afterwards, the Weight property takes constant time and the Edges method takes time proportional to V.

For alternate implementations, see , , and .

The QuickFindUF class represents a Union-find data type (also known as the Disjoint-sets data type). It supports the Union and Find operations, along with a Connected operation for determining whether two sites are in the same component and a Count operation that returns the total number of components.

The union-find data type models connectivity among a set of N sites, named 0 through N - 1. The Is-connected-to relation must be an Equivalence relation (see text).

An equivalence relation partitions the sites into Equivalence classes (or Components). In this case, two sites are in the same component if and only if they are connected. Both sites and components are identified with integers between 0 and N - 1. Initially, there are N components, with each site in its own component. The Component identifier of a component (also known as the Root, Canonical element, Leader, or Set representative) is one of the sites in the component: two sites have the same component identifier if and only if they are in the same component.

• union(p, q) adds a connection between the two sites P and Q. If P and Q are in different components, then it replaces these two components with a new component that is the union of the two.
• find(p) returns the component identifier of the component containing P.
• connected(p, q) returns true if both P and Q are in the same component, and false otherwise.
• count() returns the number of components.

The component identifier of a component can change only when the component itself changes during a call to Union; it cannot change during a call to Find, Connected, or Count.

This implementation uses quick find. Initializing a data structure with N sites takes linear time. Afterwards, the Find, Connected, and Count operations take constant time but the Union operation takes linear time.

For alternate implementations of the same API, see , , and .

The QuickUnionUF class represents a Union-find data type (also known as the Disjoint-sets data type). It supports the Union and Find operations, along with a Connected operation for determining whether two sites are in the same component and a Count operation that returns the total number of components.

The union-find data type models connectivity among a set of N sites, named 0 through N - 1. The Is-connected-to relation must be an Equivalence relation that partitions the sites into Equivalence classes (or Components). In this case, two sites are in the same component if and only if they are connected. Both sites and components are identified with integers between 0 and N- 1.

Initially, there are N components, with each site in its own component. The Component identifier of a component (also known as the Root, Canonical element, Leader, or Set representative) is one of the sites in the component: two sites have the same component identifier if and only if they are in the same component.

• union(p, q) adds a connection between the two sites P and Q. If P and Q are in different components, then it replaces these two components with a new component that is the union of the two.
• find(p) returns the component identifier of the component containing P.
• connected(p, q) returns true if both P and Q are in the same component, and false otherwise.
• count() returns the number of components.

The component identifier of a component can change only when the component itself changes during a call to Union; it cannot change during a call to Find, Connected, or Count.

This implementation uses quick union. Initializing a data structure with N sites takes linear time. Afterwards, the Union, Find, and Connected operations take linear time (in the worst case) and the Count operation takes constant time.

For alternate implementations of the same API, see , , and .

The BST class represents an ordered symbol table of generic key-value pairs. It supports the usual Put, Get, Indexer, Contains, Delete, Count, and IsEmpty methods. It also provides ordered methods for finding the Minimum, Maximum, Floor, and Ceiling. It also provides a Keys method for iterating over all of the keys. A symbol table implements the Associative array abstraction: when associating a value with a key that is already in the symbol table, the convention is to replace the old value with the new value. Unlike DictionaryTKey, TValue, this class uses the convention that values cannot be null. Setting the value associated with a key to null is equivalent to deleting the key from the symbol table.

This implementation uses a left-leaning red-black BST. It requires that the key type implements the Comparable interface and calls the compareTo() and method to compare two keys. It does not call either equals() or GetHashCode(). The Put, Contains, Remove, Minimum, Maximum, Ceiling, and Floor operations each take logarithmic time in the worst case, if the tree becomes unbalanced. The Count, and IsEmpty operations take constant time. Construction takes constant time.

The ResizingArrayBag class represents a bag (or multiset) of generic items. It supports insertion and iterating over the items in arbitrary order.

This implementation uses a resizing array. See for a version that uses a singly-linked list. The Add operation takes constant amortized time; the IsEmpty, and Count operations take constant time. Iteration takes time proportional to the number of items.

The ResizingArrayQueue class represents a first-in-first-out (FIFO) queue of generic items. It supports the usual Enqueue and Dequeue operations, along with methods for peeking at the first item, testing if the queue is empty, and iterating through the items in FIFO order.

This implementation uses a resizing array, which double the underlying array when it is full and halves the underlying array when it is one-quarter full. The Enqueue and Dequeue operations take constant amortized time. The Count, Peek, and IsEmpty operations takes constant time in the worst case.

The ResizingArrayStack class represents a (LIFO) stack of generic items. It supports the usual Push and Pop operations, along with methods for peeking at the top item, testing if the stack is empty, and iterating through the items in LIFO order.

This implementation uses a resizing array, which double the underlying array when it is full and halves the underlying array when it is one-quarter full. The Push and Pop operations take constant amortized time, whereas he Count, Peek, and IsEmpty operations takes constant time in the worst case.

The SeparateChainingHashST class represents a symbol table of generic key-value pairs. It supports the usual Put, Get, Contains, Delete, Count, and IsEmpty methods. It also provides a Keys method for iterating over all of the keys. A symbol table implements the Associative array abstraction: when associating a value with a key that is already in the symbol table, the convention is to replace the old value with the new value. Unlike DictionaryTKey, TValue, this class uses the convention that values cannot be null. Setting the value associated with a key to null is equivalent to deleting the key from the symbol table.

This implementation uses a separate chaining hash table. It requires that the key type overrides the Equals() and GetHashCode() methods. The expected time per Put, Contains, or Remove operation is constant, subject to the uniform hashing assumption. The Count, and IsEmpty operations take constant time. Construction takes constant time.

The SequentialSearchST class represents an (unordered) symbol table of generic key-value pairs. It supports the usual Put, Get, Indexer, Contains, Delete, Count, and IsEmpty methods. It also provides a Keys method for iterating over all of the keys. A symbol table implements the Associative array abstraction: when associating a value with a key that is already in the symbol table, the convention is to replace the old value with the new value. The class also uses the convention that values cannot be null. Setting the value associated with a key to null is equivalent to deleting the key from the symbol table.

This implementation uses a singly-linked list and sequential search. It relies on the Equals() method to test whether two keys are equal. It does not call either the CompareTo() or GetHashCode() method. The Put and Delete operations take linear time; the Get and Contains operations takes linear time in the worst case. The Count, and IsEmpty operations take constant time. Construction takes constant time.

The SET class represents an ordered set of comparable keys. It supports the usual Add, Contains, and Delete methods. It also provides ordered methods for finding the Minimum, Maximum, Floor, and Ceiling and set methods for Union, Intersection, and Equality.

Even though this implementation include the method Equals(), it does not support the method GetHashCode() because sets are mutable.

This implementation requires that the key type implements the Comparable interface and calls the CompareTo() and method to compare two keys. It does not call either Equals() or GetHashCode(). The Add, Contains, Delete, Minimum, Maximum, Ceiling, and Floor methods take logarithmic time in the worst case. The Count, and IsEmpty operations take constant time. Construction takes constant time.

The SparseVector class represents a D-dimensional mathematical vector. Vectors are mutable: their values can be changed after they are created. It includes methods for addition, subtraction, dot product, scalar product, unit vector, and Euclidean norm.

The implementation is a symbol table of indices and values for which the vector coordinates are nonzero. This makes it efficient when most of the vector coordindates are zero. See also for an immutable (dense) vector data type.

The ST class represents an ordered symbol table of generic key-value pairs. It supports the usual Put, Get, Contains, Indexer, Delete, Count, and IsEmpty methods. It also provides ordered methods for finding the Minimum, Maximum, Floor, and Ceiling. It also provides a Keys method for iterating over all of the keys. A symbol table implements the Associative array abstraction: when associating a value with a key that is already in the symbol table, the convention is to replace the old value with the new value. Unlike DictionaryTKey, TValue, this class uses the convention that values cannot be null. Setting the value associated with a key to null is equivalent to deleting the key from the symbol table.

This implementation uses a balanced binary search tree. It requires that the key type implements the IComparable interface and calls the CompareTo() and method to compare two keys. It does not call either Equals() or GetHashCode(). The Put, Contains, Remove, Minimum, Maximum, Ceiling, and Floor operations each take logarithmic time in the worst case. The Count, and IsEmpty operations take constant time. Construction takes constant time.

The StaticSETofInts class represents a set of integers. It supports searching for a given integer is in the set. It accomplishes this by keeping the set of integers in a sorted array and using binary search to find the given integer.

The Rank and Contains operations take logarithmic time in the worst case.

The SuffixArray class represents a suffix array of a string of length N. It supports the Selecting the Ith smallest suffix, getting the Index of the Ith smallest suffix, computing the length of the Longest common prefix between the Ith smallest suffix and the I-1st smallest suffix, and determining the Rank of a query string (which is the number of suffixes strictly less than the query string).

This implementation uses a nested class Suffix to represent a suffix of a string (using constant time and space) and Array.Sort() to sort the array of suffixes. The Index and Length operations takes constant time in the worst case. The Lcp operation takes time proportional to the length of the longest common prefix. The Select operation takes time proportional to the length of the suffix and should be used primarily for debugging.

For alternate implementations of the same API, see , which is faster in practice (uses 3-way radix quicksort) and uses less memory (does not create Suffix objects)

The SuffixArrayX class represents a suffix array of a string of length N. It supports the Selecting the Ith smallest suffix, getting the Index of the Ith smallest suffix, computing the length of the Longest common prefix between the Ith smallest suffix and the I-1st smallest suffix, and determining the Rank of a query string (which is the number of suffixes strictly less than the query string).

This implementation uses 3-way radix quicksort to sort the array of suffixes. For a simpler (but less efficient) implementations of the same API, see . The Index and Length operations takes constant time in the worst case. The Lcp operation takes time proportional to the length of the longest common prefix. The Select operation takes time proportional to the length of the suffix and should be used primarily for debugging.

This implementation uses '\0' as a sentinel and assumes that the charater '\0' does not appear in the text.

In practice, this algorithm runs very fast. However, in the worst-case it can be very poor (e.g., a string consisting of N copies of the same character. We do not shuffle the array of suffixes before sorting because shuffling is relatively expensive and a pathologial input for which the suffixes start out in a bad order (e.g., sorted) is likely to be a bad input for this algorithm with or without the shuffle.

The SymbolDigraph class represents a digraph, where the vertex names are arbitrary strings. By providing mappings between string vertex names and integers, it serves as a wrapper around the data type, which assumes the vertex names are integers between 0 and V - 1. It also supports initializing a symbol digraph from a file.

This implementation uses an to map from strings to integers, an array to map from integers to strings, and a to store the underlying graph. The Index and Contains operations take time proportional to log V, where V is the number of vertices. The Name operation takes constant time.

The SymbolGraph class represents an undirected graph, where the vertex names are arbitrary strings. By providing mappings between string vertex names and integers, it serves as a wrapper around the data type, which assumes the vertex names are integers between 0 and V - 1. It also supports initializing a symbol graph from a file.

This implementation uses an to map from strings to integers, an array to map from integers to strings, and a to store the underlying graph. The Index and Contains operations take time proportional to log V, where V is the number of vertices. The Name operation takes constant time.

The TarjanSCC class represents a data type for determining the strong components in a digraph. The Id operation determines in which strong component a given vertex lies; the AreStronglyConnected operation determines whether two vertices are in the same strong component; and the Count operation determines the number of strong components.

The Component identifier of a component is one of the vertices in the strong component: two vertices have the same component identifier if and only if they are in the same strong component.

This implementation uses Tarjan's algorithm. The constructor takes time proportional to V + E (in the worst case), where V is the number of vertices and E is the number of edges. Afterwards, the Id, Count, and AreStronglyConnected operations take constant time. For alternate implementations of the same API, see and .

The TextInput class provides static methods for reading strings and numbers from standard input. It mimics the Java's Scanner class and adapt from the StdIn class from the textbook.

The ThreeSum class provides static methods for counting and printing the number of triples in an array of integers that sum to 0 (ignoring integer overflow).

This implementation uses a triply nested loop and takes proportional to N^3, where N is the number of integers.

The ThreeSumFast class provides static methods for counting and printing the number of triples in an array of distinct integers that sum to 0 (ignoring integer overflow).

This implementation uses sorting and binary search and takes time proportional to N^2 log N, where N is the number of integers.

The Topological class represents a data type for determining a topological order of a directed acyclic graph (DAG). Recall, a digraph has a topological order if and only if it is a DAG. The HasOrder operation determines whether the digraph has a topological order, and if so, the Order operation returns one.

This implementation uses depth-first search. The constructor takes time proportional to V + E (in the worst case), where V is the number of vertices and E is the number of edges. Afterwards, the HasOrder and Rank operations takes constant time; the Order operation takes time proportional to V.

See , , and to compute a directed cycle if the digraph is not a DAG. Also, see for a nonrecursive queue-based algorithm to compute a topological order of a DAG.

The TopologicalX class represents a data type for determining a topological order of a directed acyclic graph (DAG). Recall, a digraph has a topological order if and only if it is a DAG. The HasOrder operation determines whether the digraph has a topological order, and if so, the Order operation returns one.

This implementation uses a nonrecursive, queue-based algorithm. The constructor takes time proportional to V + E (in the worst case), where V is the number of vertices and E is the number of edges. Afterwards, the HasOrder and Rank operations takes constant time; the Order operation takes time proportional to V.

See , , and to compute a directed cycle if the digraph is not a DAG. See for a recursive version that uses depth-first search.

The TransitiveClosure class represents a data type for computing the transitive closure of a digraph.

This implementation runs depth-first search from each vertex. The constructor takes time proportional to V(V + E) (in the worst case) and uses space proportional to V², where V is the number of vertices and E is the number of edges.

For large digraphs, you may want to consider a more sophisticated algorithm. Nuutila proposes two algorithm for the problem (based on strong components and an interval representation) that runs in E + V time on typical digraphs.

The TrieSET class represents an ordered set of strings over the extended ASCII alphabet. It supports the usual Add, Contains, and Delete methods. It also provides character-based methods for finding the string in the set that is the Longest prefix of a given prefix, finding all strings in the set that Start with a given prefix, and finding all strings in the set that Match a given pattern.

This implementation uses a 256-way trie. The Add, Contains, Delete, and Longest prefix methods take time proportional to the length of the key (in the worst case). Construction takes constant time.

The TrieST class represents an symbol table of key-value pairs, with string keys and generic values. It supports the usual Put, Get, Indexer, Contains, Delete, Count, and IsEmpty methods. It also provides character-based methods for finding the string in the symbol table that is the Longest prefix of a given prefix, finding all strings in the symbol table that Start with a given prefix, and finding all strings in the symbol table that Match a given pattern. A symbol table implements the Associative array abstraction: when associating a value with a key that is already in the symbol table, the convention is to replace the old value with the new value. Unlike DictionaryTKey, TValue, this class uses the convention that values cannot be null. Setting the value associated with a key to null is equivalent to deleting the key from the symbol table.

This implementation uses a 256-way trie. The Put, Contains, Delete, and Longest prefix operations take time proportional to the length of the key (in the worst case). Construction takes constant time. The Count, and IsEmpty operations take constant time. Construction takes constant time.

The TST class represents an symbol table of key-value pairs, with string keys and generic values. It supports the usual Put, Get, Indexer, Contains, Delete, Count, and IsEmpty methods. It also provides character-based methods for finding the string in the symbol table that is the Longest prefix of a given prefix, finding all strings in the symbol table that Start with a given prefix, and finding all strings in the symbol table that Match a given pattern. A symbol table implements the Associative array abstraction: when associating a value with a key that is already in the symbol table, the convention is to replace the old value with the new value. Unlike DictionaryTKey, TValue, this class uses the convention that values cannot be null. Setting the value associated with a key to null is equivalent to deleting the key from the symbol table.

This implementation uses a ternary search trie.

The TwoPersonZeroSumGame class represents a data type for computing optimal row and column strategies to two-person zero-sum games.

This implementation solves an M-by-N two-person zero-sum game by reducing it to a linear programming problem. Assuming the payoff matrix A is strictly positive, the optimal row and column player strategies x* and y* are obtained by solving the following primal and dual pair of linear programs, scaling the results to be probability distributions.

(P)  max  y^T 1         (D)  min   1^T x
     s.t  A^T y <= 1         s.t   A x >= 1
              y >= 0                 x >= 0

If the payoff matrix A has any negative entries, we add the same constant to every entry so that every entry is positive. This increases the value of the game by that constant, but does not change solutions to the two-person zero-sum game.

This implementation is not suitable for large inputs, as it calls a bare-bones linear programming solver that is neither fast nor robust with respect to floating-point roundoff error.

The UF class represents a Union-Find data type (also known as the Disjoint-sets data type). It supports the Union and Find operations, along with a Connected operation for determining whether two sites are in the same component and a Count operation that returns the total number of components.

This implementation uses weighted quick union by rank with path compression by halving. Initializing a data structure with N sites takes linear time. Afterwards, the Union, Find, and Connected operations take logarithmic time (in the worst case) and the Count operation takes constant time. Moreover, the amortized time per Union, Find, and Connected operation has inverse Ackermann complexity. For alternate implementations of the same API, see .

The WeightedQuickUnionUF class represents a Union-Find data type (also known as the Disjoint-sets data type). It supports the Union and Find operations, along with a Connected operation for determining whether two sites are in the same component and a Count operation that returns the total number of components.

This implementation uses weighted quick union by size (without path compression). Initializing a data structure with N sites takes linear time. Afterwards, the Union, Find, and Connected operations take logarithmic time (in the worst case) and the Count operation takes constant time. For alternate implementations of the same API, see .