Java Algorithms and Clients

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.

Algorithms and clients in the textbook. The list below includes a few more than 100 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 1d interval 2d interval
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 polynomial 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 optimized 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  
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 cycle in a graph tinyG.txt  mediumG.txt  largeG.txt 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 paths in a digraph (DFS) tinyDG.txt  mediumDG.txt cycle in a digraph tinyDG.txt  tinyDAG.txt depth-first order in a digraph tinyDG.txt  tinyDAG.txt  
4.5 topological order in a DAG jobs.txt paths in a digraph (BFS) tinyDG.txt  mediumDG.txt 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 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 Knuth-Morris-Pratt substring search
5.7 Boyer-Moore substring search
5.8 Rabin-Karp substring search
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 run-length coding 4runs.bin  q32x48.bin  q64x96.bin  
5.10 Huffman coding tinytinyTale.txt  medTale.txt  tale.txt  
5.11 Lempel-Ziv-Welch coding abraLZW.txt  ababLZW.txt  
6.1 collision system brownian.txt  diffusion.txt particle
6.2 B-tree
6.3 suffix array abra.txt suffix array abra.txt longest repeated substring tinyTale.txt  mobydick.txt keyword in context tale.txt longest common substring tale.txt  mobydick.txt  
6.4 max flow / min cut tinyFN.txt capacitated network capacitated edge with flow bipartite matching weighted bipartite matching simplex method
9 BEYOND DATA Gaussian elimination Fast Fourier transform complex number 2d convex hull rs1423.txt  kw1260.txt 2d farthest pair rs1423.txt  kw1260.txt 2d closest pair rs1423.txt  kw1260.txt  

Standard input and output libraries.

We use these standard input and output libraries from Introduction to Programming: An Interdisciplinary Approach. You can download them all together as stdlib.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 process digital images
3.2 measure running time 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 stdlib.jar and algs4.jar and add them to the classpath. Do not unjar them. 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.

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. Our libraries stdlib.jar and algs4.jar are 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. If I use a named package to structure my code, the compiler can no longer access the libraries in stdlib.jar or algs4.jar. Why not?

A. The libraries in stdlib.jar and algs4.jar are in the "default" package. In Java, you can't access classes in the default package from a named package. If you need to use our libraries with a named package, you can use these package versions: stdlib-package.jar and algs4-package.jar.

Warning: if you are taking Princeton COS 226 or Coursera, Algorithms, Part I or II, you must use the default package verison of our libraries to facilitate grading.

Q. Why is there Javadoc for only some of the classes in algs4.jar?

A. We documented the most important classes in the library and we hope to slowly do more. To help us along, we welcome crowdsourcing efforts—just send us the Javadoc'd verison of a class (being sure to maintain a consistent style, e.g., please don't use tabs!) and we'll update.

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.