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

1 FUNDAMENTALS DATA binary search tinyW.txt  tinyT.txt  largeW.txt  largeT.txt random numbers in a given range average of a sequence of numbers concatenate files in1.txt  in2.txt Knuth shuffle cards.txt counter set of integers whitelist client tinyW.txt  tinyT.txt  largeW.txt  largeT.txt Euclidean vector date transaction point axis-aligned rectangle 1d interval 2d interval running average and stddev
1.1 LIFO stack (resizing array) tobe.txt  
1.2 LIFO stack (linked list) tobe.txt LIFO stack tobe.txt FIFO queue (resizing array) tobe.txt  
1.3 FIFO queue (linked list) tobe.txt FIFO queue tobe.txt multiset (resizing array)
1.4 multiset (linked list) multiset timer (wall time) timer (CPU time) simple linear regression brute-force three sum 1Kints.txt  2Kints.txt  4Kints.txt  8Kints.txt faster three sum 1Kints.txt  2Kints.txt  4Kints.txt  8Kints.txt doubling test doubling ratio quick find tinyUF.txt  mediumUF.txt  largeUF.txt quick union tinyUF.txt  mediumUF.txt  largeUF.txt  
1.5 weighted quick union tinyUF.txt  mediumUF.txt  largeUF.txt union-by-rank with path halving tinyUF.txt  mediumUF.txt  largeUF.txt  
2.1 insertion sort tiny.txt  words3.txt insertion sort (optimized) tiny.txt  words3.txt binary insertion sort tiny.txt  words3.txt  
2.2 selection sort
2.3 shellsort
2.4 top-down mergesort bottom-up mergesort optimized mergesort
2.5 quicksort quicksort with 3-way partitioning optimized quicksort priority queue client tinyBatch.txt  
2.6 max heap priority queue tinyPQ.txt min heap priority queue tinyPQ.txt index min heap priority queue index max heap priority queue multiway merge m1.txt  m2.txt  m3.txt  
2.7 heapsort tiny.txt  words3.txt  
3 SEARCHING DATA frequency counter tinyTale.txt  tale.txt  leipzig1M.txt  
3.1 sequential search tinyST.txt  
3.2 binary search tinyST.txt  
3.3 binary search tree tinyST.txt  
3.4 red-black tree tinyST.txt  
3.5 separate chaining hash table
3.6 linear probing hash table ordered symbol table ordered set remove duplicates tinyTale.txt whitelist filter list.txt  tinyTale.txt blacklist filter list.txt  tinyTale.txt dictionary lookup ip.csv  DJIA.csv  amino.csv  UPC.csv index and inverted index aminoI.csv  movies.txt file indexing ex1.txt  ex2.txt  ex3.txt  ex4.txt sparse vector
4 GRAPHS DATA undirected graph tinyG.txt  mediumG.txt generate random graphs depth-first search in a graph tinyG.txt  mediumG.txt DFS in a graph (nonrecursive) tinyG.txt  mediumG.txt  
4.1 paths in a graph (DFS) tinyCG.txt  mediumG.txt  largeG.txt  
4.2 paths in a graph (BFS) tinyCG.txt  mediumG.txt  largeG.txt  
4.3 connected components of a graph tinyG.txt  mediumG.txt  largeG.txt bipartite or odd cycle (DFS) bipartite or odd cycle (BFS) cycle in a graph tinyG.txt  mediumG.txt  largeG.txt Eulerian cycle in a graph Eulerian path in a graph symbol graph routes.txt  movies.txt degrees of separation routes.txt  movies.txt directed graph tinyDG.txt generate random digraphs
4.4 depth-first search in a digraph tinyDG.txt DFS in a digraph (nonrecursive) tinyDG.txt paths in a digraph (DFS) tinyDG.txt  mediumDG.txt paths in a digraph (BFS) tinyDG.txt  mediumDG.txt cycle in a digraph tinyDG.txt  tinyDAG.txt cycle in a digraph (nonrecursive) Eulerian cycle in a digraph Eulerian path in a digraph depth-first order in a digraph tinyDG.txt  tinyDAG.txt  
4.5 topological order in a DAG jobs.txt topological order (nonrecursive) transitive closure tinyDG.txt symbol digraph
4.6 strong components (Kosaraju–Sharir) tinyDG.txt  mediumDG.txt  largeDG.txt strong components (Tarjan) tinyDG.txt  mediumDG.txt  largeDG.txt strong components (Gabow) tinyDG.txt  mediumDG.txt  largeDG.txt edge-weighted graph weighted edge MST (lazy Prim) tinyEWG.txt  mediumEWG.txt  largeEWG.txt  
4.7 MST (Prim) tinyEWG.txt  mediumEWG.txt  largeEWG.txt  
4.8 MST (Kruskal) tinyEWG.txt  mediumEWG.txt  largeEWG.txt MST (Boruvka) tinyEWG.txt  mediumEWG.txt  largeEWG.txt edge-weighted digraph tinyEWD.txt weighted, directed edge
4.9 shortest paths (Dijkstra) tinyEWD.txt  mediumEWD.txt  largeEWD.txt undirected shortest paths (Dijkstra) tinyEWG.txt  mediumEWG.txt  largeEWG.txt all-pairs shortest paths tinyEWD.txt  mediumEWD.txt  
4.10 shortest paths in a DAG tinyEWDAG.txt longest paths in a DAG tinyEWDAG.txt critical path method jobsPC.txt  
4.11 shortest paths (Bellman–Ford) tinyEWDn.txt  tinyEWDnc.txt cycle in an edge-weighted digraph arbitrage detection rates.txt all-pairs shortest paths (dense) tinyEWD.txt  mediumEWD.txt edge-weighted graph (dense) tinyEWD.txt  
5 STRINGS DATA alphabet alphabet client abra.txt  pi.txt  
5.1 LSD radix sort words3.txt  
5.2 MSD radix sort shells.txt  
5.3 3-way string quicksort shells.txt  
5.4 multiway trie symbol table shellsST.txt multiway trie set shellsST.txt  
5.5 ternary search trie shellsST.txt  
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 abra.txt hex dump abra.txt picture dump abra.txt genomic code genomeTiny.txt  genomeVirus.txt data compression (run-length coding) 4runs.bin  q32x48.bin  q64x96.bin  
5.10 data compression (Huffman) tinytinyTale.txt  medTale.txt  tale.txt  
5.11 data compression (Lempel–Ziv–Welch) abraLZW.txt  ababLZW.txt  
6.1 collision system brownian.txt  diffusion.txt particle
6.2 B-tree
6.3 suffix array (suffix sorting) abra.txt suffix array (optimized) abra.txt longest repeated substring tinyTale.txt  mobydick.txt keyword in context tale.txt longest common substring tale.txt  mobydick.txt  
6.4 maxflow–mincut tinyFN.txt capacitated network capacitated edge with flow bipartite matching (alternating path) bipartite matching (Hopcroft–Karp) weighted bipartite matching linear programming (simplex) two-person zero-sum game
9 BEYOND DATA Gaussian elimination Gauss–Jordan elimination Fast Fourier transform complex number 2d convex hull (Graham scan) rs1423.txt  kw1260.txt 2d farthest pair (rotating calipers) rs1423.txt  kw1260.txt 2d closest pair rs1423.txt  kw1260.txt 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
1 contributed by Ricardo Pacheco
2 contributed by John Hentosh
3 contributed by Tristan Claverie

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:

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.

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