Java Algorithms and Clients

Java programming environment. Here are instructions for setting up an IntelliJ-based Java programming environment for macOS, Windows, and Linux.

Design goals. Our original goal for this book was to cover the 50 algorithms that every programmer should know. We use the word programmer to refer to anyone engaged in trying to accomplish something with the help of a computer, including scientists, engineers, and applications developers, not to mention college students in science, engineering, and computer science. The code is optimized for clarity, portability, and efficiency. While some of our implementations are as fast as their counterparts in java.util, our primary goal is to express the core algorithmic idea in an elegant and efficient manner. While we embrace some advanced Java features (such as generics and iterators), we avoid others that would interfere with the exposition (such as inheritance and concurrency).

Algorithms and clients in the textbook. The list below includes nearly 200 Java programs (some are clients, some others are basic infrastructure). Click on the program name to access the Java code; click on the description to access the javadoc; click on the data file names to access the data.

1	FUNDAMENTALS
–	BinarySearch.java	binary search
–	RandomSeq.java	random numbers in a given range
–	Average.java	average of a sequence of numbers
–	Cat.java	concatenate files
–	Knuth.java	Knuth shuffle
–	Counter.java	counter
–	StaticSETofInts.java	set of integers
–	Allowlist.java	allowlist client
–	Vector.java	Euclidean vector
–	Date.java	date
–	Transaction.java	transaction
–	Point2D.java	point
–	RectHV.java	axis-aligned rectangle
–	Interval1D.java	1d interval
–	Interval2D.java	2d interval
–	Accumulator.java	running average and stddev
1.1	ResizingArrayStack.java	LIFO stack (resizing array)
1.2	LinkedStack.java	LIFO stack (linked list)
–	Stack.java	LIFO stack
–	ResizingArrayQueue.java	FIFO queue (resizing array)
1.3	LinkedQueue.java	FIFO queue (linked list)
–	Queue.java	FIFO queue
–	ResizingArrayBag.java	multiset (resizing array)
1.4	LinkedBag.java	multiset (linked list)
–	Bag.java	multiset
–	Stopwatch.java	timer (wall time)
–	StopwatchCPU.java	timer (CPU time)
–	LinearRegression.java	simple linear regression
–	ThreeSum.java	brute-force three sum
–	ThreeSumFast.java	faster three sum
–	DoublingTest.java	doubling test
–	DoublingRatio.java	doubling ratio
–	QuickFindUF.java	quick find
–	QuickUnionUF.java	quick union
1.5	WeightedQuickUnionUF.java	weighted quick union
–	UF.java	union-by-rank with path halving
2	SORTING
2.1	Insertion.java	insertion sort
–	InsertionX.java	insertion sort (optimized)
–	BinaryInsertion.java	binary insertion sort
2.2	Selection.java	selection sort
2.3	Shell.java	shellsort
2.4	Merge.java	top-down mergesort
–	MergeBU.java	bottom-up mergesort
–	MergeX.java	optimized mergesort
–	Inversions.java	number of inversions
2.5	Quick.java	quicksort
–	Quick3way.java	quicksort with 3-way partitioning
–	QuickX.java	optimized 2-way quicksort
–	QuickBentleyMcIlroy.java	optimized 3-way quicksort
–	TopM.java	priority queue client
2.6	MaxPQ.java	max heap priority queue
–	MinPQ.java	min heap priority queue
–	IndexMinPQ.java	index min heap priority queue
–	IndexMaxPQ.java	index max heap priority queue
–	Multiway.java	multiway merge
2.7	Heap.java	heapsort
3	SEARCHING
–	FrequencyCounter.java	frequency counter
3.1	SequentialSearchST.java	sequential search
3.2	BinarySearchST.java	binary search
3.3	BST.java	binary search tree
3.4	RedBlackBST.java	red-black tree
3.5	SeparateChainingHashST.java	separate chaining hash table
3.6	LinearProbingHashST.java	linear probing hash table
–	ST.java	ordered symbol table
–	SET.java	ordered set
–	DeDup.java	remove duplicates
–	AllowFilter.java	allowlist filter
–	BlockFilter.java	blocklist filter
–	LookupCSV.java	dictionary lookup
–	LookupIndex.java	index and inverted index
–	FileIndex.java	file indexing
–	SparseVector.java	sparse vector
4	GRAPHS
–	Graph.java	undirected graph
–	GraphGenerator.java	generate random graphs
–	DepthFirstSearch.java	depth-first search in a graph
–	NonrecursiveDFS.java	DFS in a graph (nonrecursive)
4.1	DepthFirstPaths.java	paths in a graph (DFS)
4.2	BreadthFirstPaths.java	paths in a graph (BFS)
4.3	CC.java	connected components of a graph
–	Bipartite.java	bipartite or odd cycle (DFS)
–	BipartiteX.java	bipartite or odd cycle (BFS)
–	Cycle.java	cycle in a graph
–	EulerianCycle.java	Eulerian cycle in a graph
–	EulerianPath.java	Eulerian path in a graph
–	SymbolGraph.java	symbol graph
–	DegreesOfSeparation.java	degrees of separation
–	Digraph.java	directed graph
–	DigraphGenerator.java	generate random digraphs
4.4	DirectedDFS.java	depth-first search in a digraph
–	NonrecursiveDirectedDFS.java	DFS in a digraph (nonrecursive)
–	DepthFirstDirectedPaths.java	paths in a digraph (DFS)
–	BreadthFirstDirectedPaths.java	paths in a digraph (BFS)
–	DirectedCycle.java	cycle in a digraph
–	DirectedCycleX.java	cycle in a digraph (nonrecursive)
–	DirectedEulerianCycle.java	Eulerian cycle in a digraph
–	DirectedEulerianPath.java	Eulerian path in a digraph
–	DepthFirstOrder.java	depth-first order in a digraph
4.5	Topological.java	topological order in a DAG
–	TopologicalX.java	topological order (nonrecursive)
–	TransitiveClosure.java	transitive closure
–	SymbolDigraph.java	symbol digraph
4.6	KosarajuSharirSCC.java	strong components (Kosaraju–Sharir)
–	TarjanSCC.java	strong components (Tarjan)
–	GabowSCC.java	strong components (Gabow)
–	EdgeWeightedGraph.java	edge-weighted graph
–	Edge.java	weighted edge
–	LazyPrimMST.java	MST (lazy Prim)
4.7	PrimMST.java	MST (Prim)
4.8	KruskalMST.java	MST (Kruskal)
–	BoruvkaMST.java	MST (Boruvka)
–	EdgeWeightedDigraph.java	edge-weighted digraph
–	DirectedEdge.java	weighted, directed edge
4.9	DijkstraSP.java	shortest paths (Dijkstra)
–	DijkstraUndirectedSP.java	undirected shortest paths (Dijkstra)
–	DijkstraAllPairsSP.java	all-pairs shortest paths
4.10	AcyclicSP.java	shortest paths in a DAG
–	AcyclicLP.java	longest paths in a DAG
–	CPM.java	critical path method
4.11	BellmanFordSP.java	shortest paths (Bellman–Ford)
–	EdgeWeightedDirectedCycle.java	cycle in an edge-weighted digraph
–	Arbitrage.java	arbitrage detection
–	FloydWarshall.java	all-pairs shortest paths (dense)
–	AdjMatrixEdgeWeightedDigraph.java	edge-weighted graph (dense)
5	STRINGS
–	Alphabet.java	alphabet
–	Count.java	alphabet client
5.1	LSD.java	LSD radix sort
5.2	MSD.java	MSD radix sort
–	InplaceMSD.java	In-place MSD radix sort¹
5.3	Quick3string.java	3-way string quicksort
–	AmericanFlag.java	American flag sort¹
–	AmericanFlagX.java	non-recursive American flag sort¹
5.4	TrieST.java	multiway trie symbol table
–	TrieSET.java	multiway trie set
5.5	TST.java	ternary search trie
5.6	KMP.java	substring search (Knuth–Morris–Pratt)
5.7	BoyerMoore.java	substring search (Boyer–Moore)
5.8	RabinKarp.java	substring search (Rabin–Karp)
5.9	NFA.java	NFA for regular expressions
–	GREP.java	grep
–	BinaryDump.java	binary dump
–	HexDump.java	hex dump
–	PictureDump.java	picture dump
–	Genome.java	genomic code
–	RunLength.java	data compression (run-length coding)
5.10	Huffman.java	data compression (Huffman)
5.11	LZW.java	data compression (Lempel–Ziv–Welch)
6	CONTEXT
6.1	CollisionSystem.java	collision system
–	Particle.java	particle
6.2	BTree.java	B-tree
6.3	SuffixArray.java	suffix array (suffix sorting)
–	SuffixArrayX.java	suffix array (optimized)
–	LongestRepeatedSubstring.java	longest repeated substring
–	KWIK.java	keyword in context
–	LongestCommonSubstring.java	longest common substring
6.4	FordFulkerson.java	maxflow–mincut
–	FlowNetwork.java	capacitated network
–	FlowEdge.java	capacitated edge with flow
–	GlobalMincut.java	global mincut (Stoer–Wagner)⁵
–	BipartiteMatching.java	bipartite matching (alternating path)
–	HopcroftKarp.java	bipartite matching (Hopcroft–Karp)
–	AssignmentProblem.java	weighted bipartite matching
–	LinearProgramming.java	linear programming (simplex)
–	TwoPersonZeroSumGame.java	two-person zero-sum game
9	BEYOND
–	GaussianElimination.java	Gaussian elimination
–	GaussJordanElimination.java	Gauss–Jordan elimination
–	FFT.java	Fast Fourier transform
–	Complex.java	complex number
–	Polynomial.java	polynomial (integer)
–	GrahamScan.java	2d convex hull (Graham scan)
–	FarthestPair.java	2d farthest pair (rotating calipers)
–	ClosestPair.java	2d closest pair
–	FenwickTree.java	Fenwich tree²
–	SegmentTree.java	Segment tree²
–	PatriciaST.java	PATRICIA trie symbol table³
–	PatriciaSET.java	PATRICIA trie set³
–	MultiwayMinPQ.java	Multiway heap⁴
–	IndexMultiwayMinPQ.java	Index multiway heap⁴
–	BinomialMinPQ.java	Binomial heap⁴
–	IndexBinomialMinPQ.java	Index binomial heap⁴
–	FibonacciMinPQ.java	Fibonacci heap⁴
–	IndexFibonacciMinPQ.java	Index Fibonacci heap⁴
–	AVLTreeST.java	AVL tree⁵
		¹ contributed by Ivan Pesin ² contributed by Ricardo Pacheco ³ contributed by John Hentosh ⁴ contributed by Tristan Claverie ⁵ contributed by Marcelo Silva

Standard input and output libraries.

We use these standard input and output libraries from Introduction to Programming: An Interdisciplinary Approach. They are part of algs4.jar.

§	PROGRAM	DESCRIPTION / JAVADOC
1.5	StdIn.java	read numbers and text from standard input
1.5	StdOut.java	write numbers and text to standard output
1.5	StdDraw.java	draw geometric shapes in a window
1.5	StdAudio.java	create, play, and manipulate monaural sound
1.5	StdAudioStereo.java	create, play, and manipulate stereo sound
2.2	StdRandom.java	generate random numbers
2.2	StdStats.java	compute statistics
2.2	StdArrayIO.java	read and write 1D and 2D arrays
3.1	StdPicture.java	process one color image
3.1	In.java	read numbers and text from files and URLs
3.1	Out.java	write numbers and text to files
3.1	Draw.java	draw geometric shapes
3.1	DrawListener.java	interactions with Draw
3.1	Picture.java	process color images
3.1	GrayscalePicture.java	process grayscale images
–	BinaryStdIn.java	read bits from standard input
–	BinaryStdOut.java	write bits to standard output
–	BinaryIn.java	read bits from files and URLs
–	BinaryOut.java	write bits to files

Using the textbook libraries.

If you used our recommmended environment, you should be ready to go.

IntelliJ. The IntelliJ project folders that we suppply for COS 226 and Coursera are pre-configured to add algs4.jar to the Java classpath.
Windows Git Bash (autoinstaller wrapper script). The Windows installer downloads algs4.jar to C:\Program Files\LIFT-CS\algs4.jar and provides the wrapper scripts javac-algs4 and java-algs4, which add algs4.jar to the Java classpath. These wrapper scripts are available only in Git Bash, not the Command Prompt.
Mac OS X Terminal (via autoinstall wrapper script). The Mac OS X installer downloads algs4.jar to the /usr/local/lift/lib/algs4.jar folder and provides the wrapper scripts javac-algs4 and java-algs4, which add algs4.jar to the Java classpath.
Linux shell (via wrapper script). The Linux installation guide downloads algs4.jar to the /usr/local/lift folder and provides the wrapper scripts javac-algs4 and java-algs4, which add algs4.jar to the Java classpath.

Now, we'll describe how to add our textbook libraries to your Java classpath in a variety of other environments. First, download algs4.jar. Do not unjar it.

Windows Command Prompt (temporary). Download algs4.jar to, say C:\Users\username\algs4\algs4.jar. Compile and execute your program using the -classpath or -cp option.
javac -cp .;C:\Users\username\algs4\algs4.jar HelloWorld.java java -cp .;C:\Users\username\algs4\algs4.jar HelloWorld
Windows Command Prompt (permanent). Download algs4.jar to, say C:\Users\username\algs4\algs4.jar. Next, add algs4.jar to the CLASSPATH environment variable.
- Windows 8 or 10: Control Panel → System and Security → System → Advanced system settings → Advanced → Environment Variables → CLASSPATH.
  Windows 7: Start → Computer → System Properties → Advanced system settings → Environment Variables → User variables → CLASSPATH.
  Vista: Start → My Computer → Properties → Advanced → Environment Variables → User variables → CLASSPATH.
- Prepend the following to the beginning of the CLASSPATH variable:
  C:\Users\username\algs4\algs4.jar;
  The semicolons separate entries in the CLASSPATH.
- Click OK three times.
If you don't see a variable named CLASSPATH, click New and in the popup window enter CLASSPATH for the variable name. Then, perform the instructions above.
Mac OS X Terminal (temporary). Download algs4.jar to, say ~/algs4/algs4.jar. Compile and execute your program using the -classpath or -cp option.
javac -cp .:~/algs4/algs4.jar HelloWorld.java java -cp .:~/algs4/algs4.jar HelloWorld
Mac OS X Terminal (manual). Download algs4.jar to, say ~/algs4/algs4.jar. Depending on your shell, add the following line or lines to the file specified:
- Bourne-again shell (bash). Add the following line to the file ~/.bash_profile (if it exists); otherwise add it to the file ~/.bash_login (if it exists); otherwise, add it to the file ~/.profile (if it doesn't exist, create it first):
  export CLASSPATH=$CLASSPATH:~/algs4/algs4.jar
  The colons separate entries in the CLASSPATH.
- C shell (csh). Add the following line to the file ~/.cshrc (if it doesn't exist, create it first):
  if ( !($?CLASSPATH) ) then setenv CLASSPATH .:~/algs4/algs4.jar else setenv CLASSPATH .:~/algs4/algs4.jar:${CLASSPATH} endif
- Bourne shell (sh). Add the following line to the file ~/.profile (if it doesn't exist, create it first):
  export CLASSPATH=$CLASSPATH:~/algs4/algs4.jar
- T shell (tcsh). Add the following line to the file ~/.tcshrc (if it exists); otherwise add it to the file ~/.cshrc (if it doesn't exist, create it first):
  if ( !($?CLASSPATH) ) then setenv CLASSPATH .:~/algs4/algs4.jar else setenv CLASSPATH .:~/algs4/algs4.jar:${CLASSPATH} endif
Linux Command Line (manual). Follow the same instructions as for Mac OS X Terminal.
IntelliJ (manual). Download algs4.jar to a folder and add algs4.jar to the project via File → Project Structure → Libraries → New Project Library.
Eclipse (manual). Download algs4.jar to a folder and add algs4.jar to the project via Project → Properties → Java Build Path → Libaries → Add External JARs and select algs4.jar.
VSCode (manual). Download algs4.jar to a folder and add algs4.jar to the project via Java Project → Referenced Library and select algs4.jar.

Accessing the textbook libraries.

To access the classes in algs4.jar, you will need to use import statements like the ones below:

import edu.princeton.cs.algs4.MinPQ;
import edu.princeton.cs.algs4.StdIn;

Download our test data files.

To use the data, unzip algs4-data.zip. It will create a subdirectory algs4-data with all of the data files used in the textbook.

Git.

We maintain the source code in a Git repository, suitable for use with Maven or Gradle.

Maven and Gradle.

We maintain algs4.jar as a Bintray resource, for use with Maven or Gradle.

Exercise solutions.

Here is a list of solutions to selected coding exercises.

1	FUNDAMENTALS
1.2.13	Transaction.java	transaction data type
1.2.16	Rational.java	rational number data type
1.2.19	Date.java	date data type
1.3.1	FixedCapacityStackOfStrings.java	add isFull() method to stack
1.3.4	Parentheses.java	balanced parentheses
1.3.7	Stack.java	add peek() method to stack
1.3.10	InfixToPostfix.java	infix-to-postfix conversion
1.3.11	EvaluatePostfix.java	evaluate a postfix expression
1.3.14	ResizingArrayQueue.java	resizing array queue
1.3.37	Josephus.java	Josephus problem
1.4.14	FourSum.java	brute-force 4-sum
1.5.7	QuickUnionUF.java	quick union
1.5.7	QuickFindUF.java	quick find
1.5.17	ErdosRenyi.java	Erdos-Renyi simulation
2	SORTING
2.1.1	TraceSelection.java	trace of selection sort
2.1.4	TraceInsertion.java	trace of insertion sort
2.1.9	TraceShell.java	trace of shellsort
2.1.21	Transaction.java	add natural order to Transaction
2.1.22	SortTransactions.java	sort transactions
2.1.23	InsertionX.java	insertion sort with sentinel
2.1.24	InsertionX.java	insertion sort with half exchanges
2.2.2	TraceMerge.java	mergesort trace
2.2.3	TraceMergeBU.java	bottom-up mergesort trace
2.2.9	Merge.java	mergesort without static array
2.2.11	MergeX.java	improved mergesort
2.2.19	Inversions.java	count number of inversions
2.2.20	Merge.java	index sort
2.3.1	TracePartition.java	partition trace
2.3.2	TraceQuick.java	quicksort trace
2.3.5	Sort2distinct.java	sort array with 2 distinct keys
2.3.12	TraceQuick3way.java	3-way quicksort trace
2.3.16	QuickBest.java	best-case for quicksort
2.3.22	QuickX.java	Bentley-McIlroy 3-way quicksort
2.4.3	OrderedArrayMaxPQ.java	ordered array priority queue
2.4.3	UnorderedArrayMaxPQ.java	unordered array priority queue
2.4.15	MaxPQ.java	check if an array is heap-ordered
2.4.25	CubeSum.java	find a^3 + b^3 = c^3 + d^3
2.4.33	IndexMaxPQ.java	index priority queue
2.5.8	Frequency.java	count word frequencies
2.5.12	SPT.java	shortest processing time first rule
2.5.13	LPT.java	longest processing time first rule
2.5.14	Domain.java	sort by reverse domain name
2.5.16	California.java	2003 California gubernatorial election order
2.5.19	KendallTau.java	Kendall Tau distance
2.5.24	StableMinPQ.java	stable priority queue
2.5.25	Point2D.java	point comparators
2.5.27	Insertion.java	index sort
2.5.28	FileSorter.java	sort files by name
3	SEARCHING
3.1.1	GPA.java	compute GPA
3.1.2	ArrayST.java	unordered-array symbol table
3.1.5	SequentialSearchST.java	add size(), delete(), and keys()
3.1.16	BinarySearchST.java	add delete()
3.1.17	BinarySearchST.java	add floor()
3.1.29	TestBinarySearchST.java	test client
3.1.30	BinarySearchST.java	check internal invariants
3.2.6	BST.java	add height() method
3.2.10	TestBST.java	test client
3.2.13	NonrecursiveBST.java	nonrecursive BST
3.2.25	PerfectBalance.java	perfectly balanced BST
3.2.32	BST.java	order check
3.2.33	BST.java	rank/select check
4	GRAPHS
4.1.3	Graph.java	add copy constructor
4.1.13	BreadthFirstPaths.java	add distTo() method
4.1.23	BaconHistogram.java	histogram of Bacon numbers
4.1.26	DegreesOfSeparationDFS.java	degrees of separation with DFS
4.1.27	MemoryOfGraph.java	memory of Graph data type
4.1.36	Bridge.java	find bridges
4.2.3	Digraph.java	add copy constructor
4.2.21	MemoryOfDigraph.java	memory of Digraph data type
4.2.23	DirectedEulerianCycle.java	directed Eulerian cycle
4.2.31	TopologicalX.java	queue-based topologial sort
4.2.39	WebCrawler.java	web crawler
4.3.9	EdgeWeightedGraph.java	edge-weighted graph constructor
4.3.11	MemoryOfEdgeWeightedGraph.java	memory of edge-weighted graph
4.3.17	EdgeWeightedGraph.java	add toString() to EdgeWeightedGraph
4.3.21	PrimMST.java	add edges() to PrimMST
4.3.22	PrimMST.java	minimum spanning forest
4.3.22	KruskalMST.java	minimum spanning forest
4.3.33	KruskalMST.java	MST certification
4.3.43	BoruvkaMST.java	Boruvka's algorithm
4.4.2	EdgeWeightedDigraph.java	add toString() method
4.4.11	MemoryOfEdgeWeightedDigraph.java	memory of EdgeWeightedDigraph data type
4.4.12	Topological.java	topological sort in edge-weighted digraphs
4.4.12	EdgeWeightedDirectedCycle.java	directed cycle in edge-weighted digraphs
4.4.28	AcyclicLP.java	longest paths in DAGs
4.4.35	LazyDijkstraSP.java	lazy implementation of Dijkstra

Q + A

Q. What is the easiest way to execute the main() method in classes that are contained in algs4.jar?

A. If you used our autoinstaller, you can execute with a command like

% java-algs4 edu.princeton.cs.algs4.StdDraw

Q. Can I use algs4.jar in my project?

A. The library algs4.jar is released under the GNU General Public License, version 3 (GPLv3). If you wish to license the code under different terms, please contact us to discuss.

Q. There are some classic algorithms missing from your library. Can I help you add more?

A. Here are a few algorithms on our wishlist. If you wish to implement any of these and contribute to algs4.jar, send us an email and we'd be happy to include your code with an appropriate attribution. Be sure to thoroughly test and comment your code; strive for clarity; and use a style consistent with the other programs in the library.