Algorithms

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

Note：

1. based on STL Library
2. using C++14
3. Not support drawing
4. **Bug: ** const object (many member function forget to add const)
5. Welcome to point out the error, and pull better code

the code is writed and debug in CLion IDE，and not test in terminal（I will check it after finish more code）

ch1. Fundamentals

REF	PROGRAM	DESCRIPTION / JAVADOC	REF	PROGRAM	DESCRIPTION / JAVADOC
-	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 / JAVADOC	REF	PROGRAM	DESCRIPTION / JAVADOC
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.java	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 / JAVADOC	REF	PROGRAM	DESCRIPTION / JAVADOC
-	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 / JAVADOC	REF	PROGRAM	DESCRIPTION / JAVADOC
-	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