Java Algorithms and Clients

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. You can download all of the programs as algs4.jar and the data as

1 FUNDAMENTALS binary search random numbers in a given range average of a sequence of numbers concatenate files Knuth shuffle counter set of integers whitelist client Euclidean vector date transaction point axis-aligned rectangle 1d interval 2d interval running average and stddev
1.1 LIFO stack (resizing array)
1.2 LIFO stack (linked list) LIFO stack FIFO queue (resizing array)
1.3 FIFO queue (linked list) FIFO queue multiset (resizing array)
1.4 multiset (linked list) multiset timer (wall time) timer (CPU time) simple linear regression brute-force three sum faster three sum doubling test doubling ratio quick find quick union
1.5 weighted quick union union-by-rank with path halving
2.1 insertion sort insertion sort (optimized) binary insertion sort
2.2 selection sort
2.3 shellsort
2.4 top-down mergesort bottom-up mergesort optimized mergesort number of inversions
2.5 quicksort quicksort with 3-way partitioning optimized quicksort priority queue client
2.6 max heap priority queue min heap priority queue index min heap priority queue index max heap priority queue multiway merge
2.7 heapsort
3 SEARCHING frequency counter
3.1 sequential search
3.2 binary search
3.3 binary search tree
3.4 red-black tree
3.5 separate chaining hash table
3.6 linear probing hash table ordered symbol table ordered set remove duplicates whitelist filter blacklist filter dictionary lookup index and inverted index file indexing sparse vector
4 GRAPHS undirected graph generate random graphs depth-first search in a graph DFS in a graph (nonrecursive)
4.1 paths in a graph (DFS)
4.2 paths in a graph (BFS)
4.3 connected components of a graph bipartite or odd cycle (DFS) bipartite or odd cycle (BFS) cycle in a graph Eulerian cycle in a graph Eulerian path in a graph symbol graph degrees of separation directed graph generate random digraphs
4.4 depth-first search in a digraph DFS in a digraph (nonrecursive) paths in a digraph (DFS) paths in a digraph (BFS) cycle in a digraph cycle in a digraph (nonrecursive) Eulerian cycle in a digraph Eulerian path in a digraph depth-first order in a digraph
4.5 topological order in a DAG topological order (nonrecursive) transitive closure symbol digraph
4.6 strong components (Kosaraju–Sharir) strong components (Tarjan) strong components (Gabow) edge-weighted graph weighted edge MST (lazy Prim)
4.7 MST (Prim)
4.8 MST (Kruskal) MST (Boruvka) edge-weighted digraph weighted, directed edge
4.9 shortest paths (Dijkstra) undirected shortest paths (Dijkstra) all-pairs shortest paths
4.10 shortest paths in a DAG longest paths in a DAG critical path method
4.11 shortest paths (Bellman–Ford) cycle in an edge-weighted digraph arbitrage detection all-pairs shortest paths (dense) edge-weighted graph (dense)
5 STRINGS alphabet alphabet client
5.1 LSD radix sort
5.2 MSD radix sort
5.3 3-way string quicksort
5.4 multiway trie symbol table multiway trie set
5.5 ternary search trie
5.6 substring search (Knuth–Morris–Pratt)
5.7 substring search (Boyer–Moore)
5.8 substring search (Rabin–Karp)
5.9 NFA for regular expressions grep binary dump hex dump picture dump genomic code data compression (run-length coding)
5.10 data compression (Huffman)
5.11 data compression (Lempel–Ziv–Welch)
6.1 collision system particle
6.2 B-tree
6.3 suffix array (suffix sorting) suffix array (optimized) longest repeated substring keyword in context longest common substring
6.4 maxflow–mincut capacitated network capacitated edge with flow global mincut (Stoer–Wagner)4 bipartite matching (alternating path) bipartite matching (Hopcroft–Karp) weighted bipartite matching linear programming (simplex) two-person zero-sum game
9 BEYOND Gaussian elimination Gauss–Jordan elimination Fast Fourier transform complex number 2d convex hull (Graham scan) 2d farthest pair (rotating calipers) 2d closest pair Fenwich tree1 Segment tree1 PATRICIA trie symbol table2 PATRICIA trie set2 Multiway heap3 Index multiway heap3 Binomial heap3 Index binomial heap3 Fibonacci heap3 Index Fibonacci heap3 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.

1.5 read numbers and text from standard input
1.5 write numbers and text to standard output
1.5 draw geometric shapes in a window
1.5 create, play, and manipulate sound
2.2 generate random numbers
2.2 compute statistics
2.2 read and write 1D and 2D arrays
3.1 read numbers and text from files and URLs
3.1 write numbers and text to files
3.1 draw geometric shapes
3.1 interactions with Draw
3.1 process digital images read bits from standard input write bits to standard output read bits from files and URLs 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:

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 It will create a subdirectory algs4-data with all of the data files used in the textbook.


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.2.13 transaction data type
1.2.16 rational number data type
1.2.19 date data type
1.3.1 add isFull() method to stack
1.3.4 balanced parentheses
1.3.7 add peek() method to stack
1.3.10 infix-to-postfix conversion
1.3.11 evaluate a postfix expression
1.3.14 resizing array queue
1.3.37 Josephus problem
1.4.14 brute-force 4-sum
1.5.7 quick union
1.5.7 quick find
1.5.17 Erdos-Renyi simulation
2.1.1 trace of selection sort
2.1.4 trace of insertion sort
2.1.9 trace of shellsort
2.1.21 add natural order to Transaction
2.1.22 sort transactions
2.1.23 insertion sort with sentinel
2.1.24 insertion sort with half exchanges
2.2.2 mergesort trace
2.2.3 bottom-up mergesort trace
2.2.9 mergesort without static array
2.2.11 improved mergesort
2.2.19 count number of inversions
2.2.20 index sort
2.3.1 partition trace
2.3.2 quicksort trace
2.3.5 sort array with 2 distinct keys
2.3.12 3-way quicksort trace
2.3.16 best-case for quicksort
2.3.22 Bentley-McIlroy 3-way quicksort
2.4.3 ordered array priority queue
2.4.3 unordered array priority queue
2.4.15 check if an array is heap-ordered
2.4.25 find a^3 + b^3 = c^3 + d^3
2.4.33 index priority queue
2.5.8 count word frequencies
2.5.12 shortest processing time first rule
2.5.13 longest processing time first rule
2.5.14 sort by reverse domain name
2.5.16 2003 California gubernatorial election order
2.5.19 Kendall Tau distance
2.5.24 stable priority queue
2.5.25 point comparators
2.5.27 index sort
2.5.28 sort files by name
3.1.1 compute GPA
3.1.2 unordered-array symbol table
3.1.5 add size(), delete(), and keys()
3.1.16 add delete()
3.1.17 add floor()
3.1.29 test client
3.1.30 check internal invariants
3.2.6 add height() method
3.2.10 test client
3.2.13 nonrecursive BST
3.2.25 perfectly balanced BST
3.2.32 order check
3.2.33 rank/select check
4.1.3 add copy constructor
4.1.13 add distTo() method
4.1.23 histogram of Bacon numbers
4.1.26 degrees of separation with DFS
4.1.27 memory of Graph data type
4.1.36 find bridges
4.2.3 add copy constructor
4.2.21 memory of Digraph data type
4.2.23 directed Eulerian cycle
4.2.31 queue-based topologial sort
4.2.39 web crawler
4.3.9 edge-weighted graph constructor
4.3.11 memory of edge-weighted graph
4.3.17 add toString() to EdgeWeightedGraph
4.3.21 add edges() to PrimMST
4.3.22 minimum spanning forest
4.3.22 minimum spanning forest
4.3.33 MST certification
4.3.43 Boruvka's algorithm
4.4.2 add toString() method
4.4.11 memory of EdgeWeightedDigraph data type
4.4.12 topological sort in edge-weighted digraphs
4.4.12 directed cycle in edge-weighted digraphs
4.4.28 longest paths in DAGs
4.4.35 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 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.