Package edu.princeton.cs.algorithms

Class Summary

Class	Description
AcyclicLP	The AcyclicLP class represents a data type for solving the single-source longest paths problem in edge-weighted directed acyclic graphs (DAGs).
AcyclicSP	The AcyclicSP class represents a data type for solving the single-source shortest paths problem in edge-weighted directed acyclic graphs (DAGs).
AdjMatrixEdgeWeightedDigraph	The AdjMatrixEdgeWeightedDigraph class represents a edge-weighted digraph of vertices named 0 through V - 1, where each directed edge is of type DirectedEdge and has a real-valued weight.
Alphabet	Compilation: javac Alphabet.java Execution: java Alphabet A data type for alphabets, for use with string-processing code that must convert between an alphabet of size R and the integers 0 through R-1.
Arbitrage	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.
AssignmentProblem	Compilation: javac AssignmentProblem.java Execution: java AssignmentProblem N Dependencies: DijkstraSP.java DirectedEdge.java Solve an N-by-N assignment problem in N^3 log N time using the successive shortest path algorithm.
Average	The Average class provides a client for reading in a sequence of real numbers and printing out their average.
Bag<Item>	The Bag class represents a bag (or multiset) of generic items.
BellmanFordSP	The BellmanFordSP class represents a data type for solving the single-source shortest paths problem in edge-weighted digraphs with no negative cycles.
BinaryDump	Compilation: javac BinaryDump.java Execution: java BinaryDump N < file Dependencies: BinaryStdIn.java Data file: http://introcs.cs.princeton.edu/stdlib/abra.txt Reads in a binary file and writes out the bits, N per line.
BinarySearch	The BinarySearch class provides a static method for binary searching for an integer in a sorted array of integers.
BinarySearchST<Key extends Comparable<Key>,Value>
Bipartite	The Bipartite class represents a data type for determining whether an undirected graph is bipartite or whether it has an odd-length cycle.
BipartiteMatching	Compilation: javac BipartiteMatching.java Execution: java BipartiteMatching N E Dependencies: FordFulkerson.java FlowNetwork.java FlowEdge.java Find a maximum matching in a bipartite graph.
BlackFilter	Compilation: javac BlackFilter.java Execution: java BlackFilter blacklist.txt < input.txt Dependencies: SET In.java StdIn.java StdOut.java Data files: http://algs4.cs.princeton.edu/35applications/tinyTale.txt http://algs4.cs.princeton.edu/35applications/list.txt Read in a blacklist of words from a file.
BoruvkaMST	The BoruvkaMST class represents a data type for computing a minimum spanning tree in an edge-weighted graph.
BoyerMoore	Compilation: javac BoyerMoore.java Execution: java BoyerMoore pattern text Reads in two strings, the pattern and the input text, and searches for the pattern in the input text using the bad-character rule part of the Boyer-Moore algorithm.
BreadthFirstDirectedPaths	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.
BreadthFirstPaths	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.
BST<Key extends Comparable<Key>,Value>
BTree<Key extends Comparable<Key>,Value>	Compilation: javac BTree.java Execution: java BTree B-tree.
Cat	The Cat class provides a client for concatenating the results of several text files.
CC	The CC class represents a data type for determining the connected components in an undirected graph.
ClosestPair
CollisionSystem
Complex	Compilation: javac Complex.java Execution: java Complex Data type for complex numbers.
Count	Compilation: javac Count.java Execution: java Count alpha < input.txt Create an alphabet specified on the command line, read in a sequence of characters over that alphabet (ignoring characters not in the alphabet), computes the frequency of occurrence of each character, and print out the results.
Counter	The Counter class is a mutable data type to encapsulate a counter.
CPM	The CPM class provides a client that solves the parallel precedence-constrained job scheduling problem via the critical path method.
Cycle	The Cycle class represents a data type for determining whether an undirected graph has a cycle.
Date	The Date class is an immutable data type to encapsulate a date (day, month, and year).
DeDup	Compilation: javac DeDup.java Execution: java DeDup < input.txt Dependencies: SET StdIn.java StdOut.java Data files: http://algs4.cs.princeton.edu/35applications/tinyTale.txt Read in a list of words from standard input and print out each word, removing any duplicates.
DegreesOfSeparation	The DegreesOfSeparation class provides a client for finding the degree of separation between one distinguished individual and every other individual in a social network.
DepthFirstDirectedPaths	The DepthFirstDirectedPaths class represents a data type for finding directed paths from a source vertex s to every other vertex in the digraph.
DepthFirstOrder	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.
DepthFirstPaths	The DepthFirstPaths class represents a data type for finding paths from a source vertex s to every other vertex in an undirected graph.
DepthFirstSearch	The DepthFirstSearch class represents a data type for determining the vertices connected to a given source vertex s in an undirected graph.
Digraph	The Digraph class represents a directed graph of vertices named 0 through V - 1.
DigraphGenerator	The DigraphGenerator class provides static methods for creating various digraphs, including Erdos-Renyi random digraphs, random DAGs, random rooted trees, random rooted DAGs, random tournaments, path digraphs, cycle digraphs, and the complete digraph.
DijkstraAllPairsSP	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.
DijkstraSP	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.
DirectedCycle	The DirectedCycle class represents a data type for determining whether a digraph has a directed cycle.
DirectedDFS	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.
DirectedEdge	The DirectedEdge class represents a weighted edge in an EdgeWeightedDigraph.
DoublingRatio	The DoublingRatio class provides a client for measuring the running time of a method using a doubling ratio test.
DoublingTest	The DoublingTest class provides a client for measuring the running time of a method using a doubling test.
Edge	The Edge class represents a weighted edge in an EdgeWeightedGraph.
EdgeWeightedDigraph	The EdgeWeightedDigraph class represents a edge-weighted digraph of vertices named 0 through V - 1, where each directed edge is of type DirectedEdge and has a real-valued weight.
EdgeWeightedDirectedCycle	The EdgeWeightedDirectedCycle class represents a data type for determining whether an edge-weighted digraph has a directed cycle.
EdgeWeightedGraph	The EdgeWeightedGraph class represents an edge-weighted graph of vertices named 0 through V - 1, where each undirected edge is of type Edge and has a real-valued weight.
FarthestPair	Compilation: javac FarthestPair.java Execution: java FarthestPair < input.txt Dependencies: GrahamScan.java Point2D.java Given a set of N points in the plane, find the farthest pair (equivalently, compute the diameter of the set of points).
FFT	Compilation: javac FFT.java Execution: java FFT N Dependencies: Complex.java Compute the FFT and inverse FFT of a length N complex sequence.
FileIndex
FlowEdge	The FlowEdge class represents a capacitated edge with a flow in a FlowNetwork.
FlowNetwork	The FlowNetwork class represents a capacitated network with vertices named 0 through V - 1, where each directed edge is of type FlowEdge and has a real-valued capacity and flow.
FloydWarshall	The FloydWarshall class represents a data type for solving the all-pairs shortest paths problem in edge-weighted digraphs with no negative cycles.
FordFulkerson	The FordFulkerson class represents a data type for computing a maximum st-flow and minimum st-cut in a flow network.
FrequencyCounter	The FrequencyCounter class provides a client for reading in a sequence of words and printing a word (exceeding a given length) that occurs most frequently.
GabowSCC	The GabowSCC class represents a data type for determining the strong components in a digraph.
GaussianElimination	Compilation: javac GaussianElimination.java Execution: java GaussianElimination Gaussian elimination with partial pivoting.
Genome	Compilation: javac Genome.java Execution: java Genome - < input.txt (compress) Execution: java Genome + < input.txt (expand) Dependencies: BinaryIn.java BinaryOut.java Compress or expand a genomic sequence using a 2-bit code.
GrahamScan
Graph	The Graph class represents an undirected graph of vertices named 0 through V - 1.
GraphGenerator	The GraphGenerator class provides static methods for creating various graphs, including Erdos-Renyi random graphs, random bipartite graphs, random k-regular graphs, and random rooted trees.
GREP	Compilation: javac GREP.java Execution: java GREP regexp < input.txt Dependencies: NFA.java Data files: http://algs4.cs.princeton.edu/54regexp/tinyL.txt This program takes an RE as a command-line argument and prints the lines from standard input having some substring that is in the language described by the RE.
Heap	The Heap class provides a static methods for heapsorting an array.
HexDump	Compilation: javac HexDump.java Execution: java HexDump < file Dependencies: BinaryStdIn.java Data file: http://introcs.cs.princeton.edu/stdlib/abra.txt Reads in a binary file and writes out the bytes in hex, 16 per line.
Huffman	Compilation: javac Huffman.java Execution: java Huffman - < input.txt (compress) Execution: java Huffman + < input.txt (expand) Dependencies: BinaryIn.java BinaryOut.java Data files: http://algs4.cs.princeton.edu/55compression/abra.txt http://algs4.cs.princeton.edu/55compression/tinytinyTale.txt Compress or expand a binary input stream using the Huffman algorithm.
IndexMaxPQ<Key extends Comparable<Key>>	The IndexMaxPQ class represents an indexed priority queue of generic keys.
IndexMinPQ<Key extends Comparable<Key>>	The IndexMinPQ class represents an indexed priority queue of generic keys.
Insertion	The Insertion class provides static methods for sorting an array using insertion sort.
InsertionX	The InsertionX class provides static methods for sorting an array using an optimized version of insertion sort (with half exchanges and a sentinel).
Interval1D	The Interval1D class represents a one-dimensional closed interval.
Interval2D	The Interval2D class represents a closed two-dimensional interval, which represents all points (x, y) with both xleft <= x <= xright and yleft <= y <= right.
KMP	Compilation: javac KMP.java Execution: java KMP pattern text Reads in two strings, the pattern and the input text, and searches for the pattern in the input text using the KMP algorithm.
Knuth	The Knuth class provides a client for reading in a sequence of strings and shuffling them using the Knuth (or Fisher-Yates) shuffling algorithm.
KosarajuSharirSCC	The KosarajuSharirSCC class represents a data type for determining the strong components in a digraph.
KruskalMST	The KruskalMST class represents a data type for computing a minimum spanning tree in an edge-weighted graph.
KWIK	Compilation: javac KWIK.java Execution: java KWIK file.txt Dependencies: StdIn.java StdOut.java In.java SuffixArray.java Data files: http://algs4.cs.princeton.edu/63suffix/tale.txt % java KWIK tale.txt 15 majesty most gracious majesty king george th rnkeys and the majesty of the law fir on against the majesty of the people se them to his majestys chief secreta h lists of his majestys forces and of the worst w the best and the worst are known to y f them give me the worst first there th for in case of the worst is a friend in e roomdoor and the worst is over then a pect mr darnay the worst its the wisest is his brother the worst of a bad race ss in them for the worst of health for you have seen the worst of her agitati cumwented into the worst of luck buuust n your brother the worst of the bad rac full share in the worst of the day pla mes to himself the worst of the strife f times it was the worst of times it wa ould hope that the worst was over well urage business the worst will be over i clesiastics of the worst world worldly
LazyPrimMST	The LazyPrimMST class represents a data type for computing a minimum spanning tree in an edge-weighted graph.
LinearProbingHashST<Key,Value>	Compilation: javac LinearProbingHashST.java Execution: java LinearProbingHashST Symbol table implementation with linear probing hash table.
LinearRegression	The LinearRegression class performs a simple linear regression on an set of N data points (yi, xi).
LinkedBag<Item>	The LinkedBag class represents a bag (or multiset) of generic items.
LinkedQueue<Item>	The LinkedQueue class represents a first-in-first-out (FIFO) queue of generic items.
LinkedStack<Item>	The LinkedStack class represents a last-in-first-out (LIFO) stack of generic items.
LongestCommonSubstring	Compilation: javac LongestCommonSubstring.java Execution: java LongestCommonSubstring file1.txt file2.txt Dependencies: SuffixArray.java StdOut.java In.java Reads in two text strings, replaces all consecutive blocks of whitespace with a single space, and then computes the longest common substring.
LookupCSV	Compilation: javac LookupCSV.java Execution: java LookupCSV file.csv keyField valField Dependencies: ST.java In.java StdIn.java StdOut.java Data files: http://algs4.cs.princeton.edu/35applications/DJIA.csv http://algs4.cs.princeton.edu/35applications/UPC.csv http://algs4.cs.princeton.edu/35applications/amino.csv http://algs4.cs.princeton.edu/35applications/elements.csv http://algs4.cs.princeton.edu/35applications/ip.csv http://algs4.cs.princeton.edu/35applications/morse.csv Reads in a set of key-value pairs from a two-column CSV file specified on the command line; then, reads in keys from standard input and prints out corresponding values.
LookupIndex	Compilation: javac LookupIndex.java Execution: java LookupIndex movies.txt "/" Dependencies: ST.java Queue.java In.java StdIn.java StdOut.java Data files: http://algs4.cs.princeton.edu/35applications/aminoI.csv http://algs4.cs.princeton.edu/35applications/movies.txt % java LookupIndex aminoI.csv "," Serine TCT TCA TCG AGT AGC TCG Serine % java LookupIndex movies.txt "/" Bacon, Kevin Animal House (1978) Apollo 13 (1995) Beauty Shop (2005) Diner (1982) Few Good Men, A (1992) Flatliners (1990) Footloose (1984) Friday the 13th (1980) ...
LRS	Compilation: javac LRS.java Execution: java LRS < file.txt Dependencies: StdIn.java SuffixArray.java Data files: http://algs4.cs.princeton.edu/63suffix/tinyTale.txt http://algs4.cs.princeton.edu/63suffix/mobydick.txt Reads a text string from stdin, replaces all consecutive blocks of whitespace with a single space, and then computes the longest repeated substring in that text using a suffix array.
LSD	Compilation: javac LSD.java Execution: java LSD < input.txt LSD radix sort an array of extended ASCII strings, each of length W.
LZW	Compilation: javac LZW.java Execution: java LZW - < input.txt (compress) Execution: java LZW + < input.txt (expand) Dependencies: BinaryIn.java BinaryOut.java Compress or expand binary input from standard input using LZW.
MaxPQ<Key>	The MaxPQ class represents a priority queue of generic keys.
Merge	The Merge class provides static methods for sorting an array using mergesort.
MergeBU	The MergeBU class provides static methods for sorting an array using bottom-up mergesort.
MergeX	The MergeX class provides static methods for sorting an array using an optimized version of mergesort.
MinPQ<Key>	The MinPQ class represents a priority queue of generic keys.
MSD	Compilation: javac MSD.java Execution: java MSD < input.txt Reads extended ASCII string from standard input and MSD radix sorts them.
Multiway	The Multiway class provides a client for reading in several sorted text files and merging them together into a single sorted text stream.
NFA	Compilation: javac NFA.java Execution: java NFA regexp text Dependencies: Stack.java Bag.java Digraph.java DirectedDFS.java % java NFA "(A*B|AC)D" AAAABD true % java NFA "(A*B|AC)D" AAAAC false % java NFA "(a|(bc)*d)*" abcbcd true % java NFA "(a|(bc)*d)*" abcbcbcdaaaabcbcdaaaddd true Remarks ----------- - This version does not suport the + operator or multiway-or.
Particle
PictureDump
Point2D	The Point class is an immutable data type to encapsulate a two-dimensional point with real-value coordinates.
PolynomialRegression	The PolynomialRegression class performs a polynomial regression on an set of N data points (yi, xi).
PrimMST	The PrimMST class represents a data type for computing a minimum spanning tree in an edge-weighted graph.
Queue<Item>	The Queue class represents a first-in-first-out (FIFO) queue of generic items.
Quick	The Quick class provides static methods for sorting an array and selecting the ith smallest element in an array using quicksort.
Quick3string	Compilation: javac Quick3string.java Execution: java Quick3string < input.txt Reads string from standard input and 3-way string quicksort them.
Quick3way	The Quick3way class provides static methods for sorting an array using quicksort with 3-way partitioning.
QuickFindUF	The QuickFindUF class represents a union-find data structure.
QuickUnionUF	The QuickUnionUF class represents a union-find data structure.
QuickX	The QuickX class provides static methods for sorting an array using an optimized version of quicksort (using Bentley-McIlroy 3-way partitioning, Tukey's ninther, and cutoff to insertion sort).
RabinKarp
RandomSeq	The RandomSeq class is a client that prints out a pseudorandom sequence of real numbers in a given range.
RedBlackBST<Key extends Comparable<Key>,Value>
ResizingArrayBag<Item>	The ResizingArrayBag class represents a bag (or multiset) of generic items.
ResizingArrayQueue<Item>	The ResizingArrayQueue class represents a first-in-first-out (FIFO) queue of generic items.
ResizingArrayStack<Item>	The ResizingArrayStack class represents a last-in-first-out (LIFO) stack of generic items.
RunLength	Compilation: javac RunLength.java Execution: java RunLength - < input.txt (compress) Execution: java RunLength + < input.txt (expand) Dependencies: BinaryIn.java BinaryOut.java Compress or expand binary input from standard input using run-length encoding.
Selection	The Selection class provides static methods for sorting an array using selection sort.
SeparateChainingHashST<Key,Value>	Compilation: javac SeparateChainingHashST.java Execution: java SeparateChainingHashST A symbol table implemented with a separate-chaining hash table.
SequentialSearchST<Key,Value>	The SequentialSearchST class represents an (unordered) symbol table of generic key-value pairs.
SET<Key extends Comparable<Key>>	The SET class represents an ordered set of comparable keys.
Shell	The Shell class provides static methods for sorting an array using Shellsort with Knuth's increment sequence (1, 4, 13, 40, ...).
Simplex	Compilation: javac Simplex.java Execution: java Simplex Given an M-by-N matrix A, an M-length vector b, and an N-length vector c, solve the LP { max cx : Ax <= b, x >= 0 }.
SparseVector	Compilation: javac SparseVector.java Execution: java SparseVector A sparse vector, implementing using a symbol table.
ST<Key extends Comparable<Key>,Value>	The ST class represents an ordered symbol table of generic key-value pairs.
Stack<Item>	The Stack class represents a last-in-first-out (LIFO) stack of generic items.
StaticSETofInts	The StaticSETofInts class represents a set of integers.
Stopwatch	The Stopwatch data type is for measuring the time that elapses between the start and end of a programming task (wall-clock time).
StopwatchCPU	The StopwatchCPU data type is for measuring the CPU time used during a programming task.
SuffixArray	The SuffixArray class represents a suffix array of a string of length N.
SuffixArrayX	The SuffixArrayX class represents a suffix array of a string of length N.
SymbolDigraph	The SymbolDigraph class represents a digraph, where the vertex names are arbitrary strings.
SymbolGraph	The SymbolGraph class represents an undirected graph, where the vertex names are arbitrary strings.
TarjanSCC	The TarjanSCC class represents a data type for determining the strong components in a digraph.
ThreeSum	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).
ThreeSumFast	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).
TopM	The TopM class provides a client that reads a sequence of transactions from standard input and prints the M largest ones to standard output.
Topological	The Topological class represents a data type for determining a topological order of a directed acyclic graph (DAG).
Transaction	The Transaction class is an immutable data type to encapsulate a commercial transaction with a customer name, date, and amount.
Transaction.HowMuchOrder	Compares two transactions by amount.
Transaction.WhenOrder	Compares two transactions by date.
Transaction.WhoOrder	Compares two transactions by customer name.
TransitiveClosure	The TransitiveClosure class represents a data type for computing the transitive closure of a digraph.
TrieSET	The TrieSET class represents an ordered set of strings over the extended ASCII alphabet.
TrieST<Value>	The TrieST class represents an symbol table of key-value pairs, with string keys and generic values.
TST<Value>	Compilation: javac TST.java Execution: java TST < words.txt Dependencies: StdIn.java Symbol table with string keys, implemented using a ternary search trie (TST).
UF	The UF class represents a union-find data type (also known as the disjoint-sets data type).
Vector	The Vector class represents a d-dimensional mathematical vector.
WeightedQuickUnionUF	The WeightedQuickUnionUF class represents a union-find data structure.
WhiteFilter	Compilation: javac WhiteFilter.java Execution: java WhiteFilter whitelist.txt < input.txt Dependencies: SET In.java StdIn.java StdOut.java Data files: http://algs4.cs.princeton.edu/35applications/tinyTale.txt http://algs4.cs.princeton.edu/35applications/list.txt Read in a whitelist of words from a file.
Whitelist	The Whitelist class provides a client for reading in a set of integers from a file; reading in a sequence of integers from standard input; and printing to standard output those integers not in the whitelist.