Java Algorithms and Clients


Java programming environment. Here are instructions for setting up an IntelliJ-based Java programming environment for Mac OS X, 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 sort1
5.3 Quick3string.java 3-way string quicksort
AmericanFlag.java American flag sort1
AmericanFlagX.java non-recursive American flag sort1
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)5
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 tree2
SegmentTree.java Segment tree2
PatriciaST.java PATRICIA trie symbol table3
PatriciaSET.java PATRICIA trie set3
MultiwayMinPQ.java Multiway heap4
IndexMultiwayMinPQ.java Index multiway heap4
BinomialMinPQ.java Binomial heap4
IndexBinomialMinPQ.java Index binomial heap4
FibonacciMinPQ.java Fibonacci heap4
IndexFibonacciMinPQ.java Index Fibonacci heap4
AVLTreeST.java AVL tree5
1 contributed by Ivan Pesin
2 contributed by Ricardo Pacheco
3 contributed by John Hentosh
4 contributed by Tristan Claverie
5 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 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. 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.

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.