Algorithms

Algorithms, 4th edition textbook code (using c++)

official java code: Algorithms, 4th Edition

Note：

1. based on STL Library
2. using C++17
3. Not support drawing
4. Welcome to point out the error, and pull better code

TODO

• check ch1
• check ch2
• check ch3
• check ch4
• check ch5
• add ch6

Tutorial: run demo code

terminal

# for example 
cd ch1
g++ 1_BinarySearch/main.cpp -o binary
./binary

IDE(clion)

You sholud Edit the Configurations：（Due to the relative file path）

Working directory: youroot/algs4cplusplus/ch1

ch1. Fundamentals

REF	PROGRAM	DESCRIPTION / C++DOC	REF	PROGRAM	DESCRIPTION / C++DOC
-	BinarySearch.h	binary search	-	RandomSeq.cpp	random numbers in a given range
-	Average.cpp	average of a sequence of numbers	-	Cat.cpp	concatenate files
-	Knuth.h	Knuth shuffle	-	Counter.h	counter
-	StaticSETofInts.h	set of integers	-	Whitelist.cpp	whitelist client
-	Vector.h	Euclidean vector	-	Date.h	date
-	Transaction.h	transaction	-	Point2D.h	point
-	RectHV.h	axis-aligned rectangle	-	Interval1D.h	1d interval
-	Interval2D.h	2d interval	-	Accumulator.h	running average and stddev
1.1	ResizingArrayStack.h	LIFO stack (resizing array)	1.2	LinkedStack.h	LIFO stack (linked list)
-	Stack.h	LIFO stack	-	ResizingArrayQueue.h	FIFO queue (resizing array)
1.3	LinkedQueue.h	FIFO queue (linked list)	-	Queue.h	FIFO queue
-	ResizingArrayBag.h	multiset (resizing array)	1.4	LinkedBag.h	multiset (linked list)
-	Bag.h	multiset	-	Stopwatch.h	timer (wall time)
-	StopwatchCPU.h	timer (CPU time)	-	LinearRegression.h	simple linear regression
-	ThreeSum.h	brute-force three sum	-	ThreeSumFast.h	faster three sum
-	DoublingTest.h	doubling test	-	DoublingRatio.cpp	doubling ratio
-	QuickFindUF.h	quick find	-	QuickUnionUF.h	quick union
1.5	WeightedQuickUnionUF.h	weighted quick union	-	UF.h	union-by-rank with path halving

ch2. Sorting

REF	PROGRAM	DESCRIPTION / C++DOC	REF	PROGRAM	DESCRIPTION /C++DOC
2.1	Insertion.h	insertion sort	-	InsertionX.h	insertion sort (optimized)
-	BinaryInsertion.h	binary insertion sort	2.2	Selection.h	selection sort
2.3	Shell.java	shellsort	2.4	Merge.java	top-down mergesort
-	MergeBU.h	bottom-up mergesort	-	MergeX.h	optimized mergesort
-	Inversions.h	number of inversions	2.5	Quick.h	quicksort
-	Quick3way.h	quicksort with 3-way partitioning	-	QuickX.h	optimized 2-way quicksort
-	QuickBentleyMcIlroy.h	optimized 3-way quicksort	-	TopM.cpp	priority queue client
2.6	MaxPQ.h	max heap priority queue	-	MinPQ.h	min heap priority queue
-	IndexMinPQ.h	index min heap priority queue	-	IndexMaxPQ.h	index max heap priority queue
-	Multiway.h	multiway merge	2.7	Heap.h	heapsort

ch3. Searching

REF	PROGRAM	DESCRIPTION / C++DOC	REF	PROGRAM	DESCRIPTION /C++DOC
-	FrequencyCounter.cpp	frequency counter	3.1	SequentialSearchST.h	sequential search
3.2	BinarySearchST.h	binary search	3.3	BST.h	binary search tree
3.4	RedBlackBST.h	red-black tree	3.5	SeparateChainingHashST.h	separate chaining hash table
3.6	LinearProbingHashST.h	linear probing hash table	-	ST.h	ordered symbol table
-	SET.h	ordered set	-	DeDup.cpp	remove duplicates
-	WhiteFilter.cpp	whitelist filter	-	BlackFilter.cpp	blacklist filter
-	LookupCSV.cpp	dictionary lookup	-	LookupIndex.cpp	index and inverted index
-	FileIndex.cpp	file indexing	-	SparseVector.h	sparse vector

ch4. Graphs

REF	PROGRAM	DESCRIPTION / C++DOC	REF	PROGRAM	DESCRIPTION / C++DOC
-	Graph.h	undirected graph	-	GraphGenerator.java	generate random graphs
-	DepthFirstSearch.h	depth-first search in a graph	-	NonrecursiveDFS.h	DFS in a graph (nonrecursive)
4.1	DepthFirstPaths.h	paths in a graph (DFS)	4.2	BreadthFirstPaths.h	paths in a graph (BFS)
4.3	CC.h	connected components of a graph	-	Bipartite.h	bipartite or odd cycle (DFS)
-	BipartiteX.h	bipartite or odd cycle (BFS)	-	Cycle.h	cycle in a graph
-	EulerianCycle.h	Eulerian cycle in a graph	-	EulerianPath.h	Eulerian path in a graph
-	SymbolGraph.h	symbol graph	-	DegreesOfSeparation.cpp	degrees of separation
-	Digraph.h	directed graph	-	DigraphGenerator.h	generate random digraphs
4.4	DirectedDFS.h	depth-first search in a digraph	-	NonrecursiveDirectedDFS.h	DFS in a digraph (nonrecursive)
-	DepthFirstDirectedPaths.h	paths in a digraph (DFS)	-	BreadthFirstDirectedPaths.h	paths in a digraph (BFS)
-	DirectedCycle.h	cycle in a digraph	-	DirectedCycleX.h	cycle in a digraph (nonrecursive)
-	DirectedEulerianCycle.h	Eulerian cycle in a digraph	-	DirectedEulerianPath.h	Eulerian path in a digraph
-	DepthFirstOrder.h	depth-first order in a digraph	4.5	Topological.h	topological order in a DAG
-	TopologicalX.h	topological order (nonrecursive)	-	TransitiveClosure.h	transitive closure
-	SymbolDigraph.h	symbol digraph	4.6	KosarajuSharirSCC.h	strong components (Kosaraju–Sharir)
-	TarjanSCC.h	strong components (Tarjan)	-	GabowSCC.h	strong components (Gabow)
-	EdgeWeightedGraph.h	edge-weighted graph	-	Edge.h	weighted edge
-	LazyPrimMST.h	MST (lazy Prim)	4.7	PrimMST.h	MST (Prim)
4.8	KruskalMST.h	MST (Kruskal)	-	BoruvkaMST.h	MST (Boruvka)
-	EdgeWeightedDigraph.h	edge-weighted digraph	-	DirectedEdge.h	weighted, directed edge
4.9	DijkstraSP.h	shortest paths (Dijkstra)	-	DijkstraUndirectedSP.h	undirected shortest paths (Dijkstra)
-	DijkstraAllPairsSP.h	all-pairs shortest paths	4.10	AcyclicSP.h	shortest paths in a DAG
-	AcyclicLP.h	longest paths in a DAG	-	CPM.cpp	critical path method
4.11	BellmanFordSP.h	shortest paths (Bellman–Ford)	-	EdgeWeightedDirectedCycle.h	cycle in an edge-weighted digraph
-	Arbitrage.cpp	arbitrage detection	-	FloydWarshall.h	all-pairs shortest paths (dense)
-	AdjMatrixEdgeWeightedDigraph.h	edge-weighted graph (dense)

ch5. Strings

REF	PROGRAM	DESCRIPTION / C++DOC	REF	PROGRAM	DESCRIPTION / C++DOC
-	Alphabet.java	alphabet	-	Count.java	alphabet client
5.1	LSD.h	LSD radix sort	5.2	MSD.h	MSD radix sort
-	InplaceMSD.h	In-place MSD radix sort1	5.3	Quick3string.h	3-way string quicksort
-	AmericanFlag.h	American flag sort1	-	AmericanFlagX.h	non-recursive American flag sort1
5.4	TrieST.h	multiway trie symbol table	-	TrieSET.h	multiway trie set
5.5	TST.h	ternary search trie	5.6	KMP.h	substring search (Knuth–Morris–Pratt)
5.7	BoyerMoore.h	substring search (Boyer–Moore)	5.8	RabinKarp.h	substring search (Rabin–Karp)
5.9	NFA.h	NFA for regular expressions	-	GREP.cpp	grep
-	BinaryDump.cpp	binary dump