Java Algorithms and Clients


As of August 17, 2015, the "default package" version of algs4.jar has been replaced with a "named package" version. To access the classes in algs4.jar, you will need to use an import statement like the ones below:

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

Note that the I/O libraries from stdlib.jar are now contained in algs4.jar, so you no longer need stdlib.jar.


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 the corresponding counterparts in java.util, our 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. You can download all of the programs as algs4.jar and the data as algs4-data.zip.


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
Whitelist.java whitelist 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
2.5 Quick.java quicksort
Quick3way.java quicksort with 3-way partitioning
QuickX.java optimized 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
WhiteFilter.java whitelist filter
BlackFilter.java blacklist 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
5.3 Quick3string.java 3-way string quicksort
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
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
GrahamScan.java 2d convex hull (Graham scan)
FarthestPair.java 2d farthest pair (rotating calipers)
ClosestPair.java 2d closest pair
FenwickTree.java Fenwich tree1
SegmentTree.java Segment tree1
PatriciaST.java PATRICIA trie symbol table2
PatriciaSET.java PATRICIA trie set2
MultiwayMinPQ.java Multiway heap3
IndexMultiwayMinPQ.java Index multiway heap3
BinomialMinPQ.java Binomial heap3
IndexBinomialMinPQ.java Index binomial heap3
FibonacciMinPQ.java Fibonacci heap3
IndexFibonacciMinPQ.java Index Fibonacci heap3
AVLTreeST.java AVL tree4
1 contributed by Ricardo Pacheco
2 contributed by John Hentosh
3 contributed by Tristan Claverie
4 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 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 digital 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



Installing Java.

Here are instructions for installing a Java programming environment on your operating system: Mac OS X, Windows, or Linux.

Installing the textbook libraries.

To use the textbook libraries, download algs4.jar and it to the classpath. Do not unjar it. Here is how to accomplish that in a variety of environments:

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.



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 your code 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 our publisher to discuss.

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

A. Here 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.