java algorithms and data structure

http://algs4.cs.princeton.edu/code/

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
–	GlobalMincut.java	global mincut (Stoer–Wagner)4
–	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:

• Mac OS X (automatic). The Mac OS X installer downloads algs4.jar to the /Users/username/algs4 folder; adds it to the DrJava classpath; and provides the wrapper scripts javac-algs4 and java-algs4, which classpath in algs4.jar, for use in the Terminal.
• Windows (automatic). The Windows installer downloads algs4.jar to the C:\Users\username\algs4 folder; adds it the DrJava classpath; and provides the wrapper scripts javac-algs4 and java-algs4, which classpath in algs4.jar, for use from the Command Prompt.
• Windows Command Prompt (manual). Download algs4.jar to a folder, say C:\Users\username\algs4. Next, add algs4.jar to the CLASSPATH environment variable.
  • Windows 7: Start -> Computer -> System Properties -> Advanced system settings -> Environment Variables -> User variables -> CLASSPATH.
    Vista: Start -> My Computer -> Properties -> Advanced -> Environment Variables -> User variables -> CLASSPATH.
    Windows XP: Start -> Control Panel -> System -> Advanced -> Environment Variables -> User variables -> CLASSPATH.
  • Prepend the following to the beginning of the CLASSPATH variable:

    C:\Users\username\algs4\algs4.jar;

    The semicolons separate entries in the CLASSPATH.
  • Click OK three times.
  If you don't see a variable named CLASSPATH, click New and in the popup window enter CLASSPATH for the variable name. Then, perform the instructions above.
• Windows Command Prompt (heavy handed). Download algs4.jar and put it in the directory %SystemRoot%\Sun\Java\lib\ext\.
• Mac OS X Terminal (manual). Download algs4.jar to a folder, say ~/algs4. Depending on your shell, add the following line or lines to the file specified:
  • Bourne-again shell (bash). Add the following line to the file ~/.bash_profile (if it exists); otherwise add it to the file ~/.bash_login (if it exists); otherwise, add it to the file ~/.profile (if it doesn't exist, create it first):

    export CLASSPATH=$CLASSPATH:~/algs4/algs4.jar

    The colons separate entries in the CLASSPATH.
  • C shell (csh). Add the following line to the file ~/.cshrc (if it doesn't exist, create it first):

    if ( !($?CLASSPATH) ) then setenv CLASSPATH .:~/algs4/algs4.jar else setenv CLASSPATH .:~/algs4/algs4.jar:${CLASSPATH} endif
  • Bourne shell (sh). Add the following line to the file ~/.profile (if it doesn't exist, create it first):

    export CLASSPATH=$CLASSPATH:~/algs4/algs4.jar
  • T shell (tcsh). Add the following line to the file ~/.tcshrc (if it exists); otherwise add it to the file ~/.cshrc (if it doesn't exist, create it first):

    if ( !($?CLASSPATH) ) then setenv CLASSPATH .:~/algs4/algs4.jar else setenv CLASSPATH .:~/algs4/algs4.jar:${CLASSPATH} endif
• Mac OS X (heavy handed). Download algs4.jar and put it in the folder /Users/username/Library/Java/Extensions/.
• Linux Command Line (manual). Follow the same instructions as for Mac OS X Terminal.
• Linux (heavy handed). Download algs4.jar and put it in the directory /usr/java/packages/lib/ext/.
• DrJava (manual). Download algs4.jar to a folder and algs4.jar to the classpath via Preferences -> Resources -> Extra Classpath -> Add.
• Eclipse (manual). Download algs4.jar to a folder and add algs4.jar to the classpath variable to the build path of a project via Project -> Properties -> Java Build Path -> Libaries -> Add External JARs.

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.

Last modified on August 26, 2016.

Copyright © 2000–2016 Robert Sedgewick and Kevin Wayne. All rights reserved.