algorithms

Personal implementation of some algorithms in "Introduction to Algorithms", third edition

Contents

Ch.	Name	Algorithm	Page
2	InsertSort	Insersion Sort	18
	MergeSort	Merge	31
		Merge Sort	34
4	FindMaximumSubarray	Find Max Crossing Subarray	71
		Find Maximum Subarray	72
		Square Matrix Multiply	75
		Square Matrix Multiply Recursive	77
		Square Matrix Multiply Strassen	82
5	HireAssistant	Hire Assistant	115
		Randomized Hire Assistant	124
	RandomPermute	Permute By Sorting	125
		Randomize In Place	126
	OnLineMaximum	On Line Maximum	140
6	MaxHeap	Max Heapify	154
		Build Max Heap	157
		Heap Sort	160
		Heap Maximum	163
		Heap Extract Max	163
		Heap Increase Key	164
		Max Heap Insert	164
		Build Max Heap prime	167
7	Quicksort	Quicksort	171
		Partition	171
		Randomized Partition	179
		Randomized Quicksort	179
8	CountingSort	Counting Sort	195
	RadixSort	Radix Sort	198
	BucketSort	Bucket Sort	201
9	Minimum	Minimum	214
		Maximum	214
		Min Max	214
	RandomizedSelect	Randomized Select	216
		Randomized Select Iter	219
	Select	Select	220
10	Stack	StackEmpty	233
		Push	233
		Pop	233
	Queue	Enqueue	235
		Dequeue	235
	LinkedList	List Search	237
		List Insert	238
		List Delete	238
		List Delete prime	238
		List Search prime	239
		List Insert prime	239
	StorageManage	Allocate Object	244
		Free Object	244
11	DirectAddress	Direct Address Search	254
		Direct Address Insert	254
		Direct Address Delete	254
	ChainedHash	Chained Hash Insert	258
		Chained Hash Search	258
		Chained Hash Delete	258
	Hash	Division Hash	263
		Multiplication Hash	263
		Universal Hash	263
	OpenAddress	Hash Insert	270
		Hash Search	271
12	BinaryTree	Inorder Tree Walk	288
		Preorder Tree Walk	289
		Postorder Tree Walk	289
	BinarySearchTree	Tree Search	290
		Iterative Tree Search	291
		Tree Minimum	291
		Tree Maximum	291
		Tree Successor	292
		Tree Predecessor	293
		Tree Insert	294
		Transplant	296
		Tree Delete	298
13	RedBlackTree	Left Rotate	313
		Right Rotate	313
		RB Insert	315
		RB Insert Fixup	316
		RB Transplant	323
		RB Delete	324
		RB Delete Fixup	326
14	OrderStatisticTree	OS Select	341
		OS Rank	342
	IntervalTree	Interval Search	351
15	CutRod	Cut Rod	363
		Momorized Cut Rod	365
		Momorized Cut Rod Aux	366
		Bottom Up Cut Rod	366
		Extended Bottom Up Cut Rod	369
		Print Cut Rod Solution	369
	MatrixChainOrder	Matrix Multiply	371
		Matrix Chain Order	375
		Print Optimal Parens	377
		Recursive Matrix Chain	385
		Memorized Matrix Chain	388
		Lookup Chain	388
	LCSLength	LCS Length	394
		Print LCS	395
	OptimalBST	Optimal BST	402
16	ActivitySelector	Recursive Activity Selector	419
		Greedy Activity Selector	421
	Huffman	Huffman	431
	Greedy	Greedy	440
	TaskSchedule	Task Schedule	446
17	Stack	Multi Pop	453
	BinaryCounter	Increment	454
	DynamicTable	Table Insert	464
18	BTree	B Tree Search	491
		B Tree Create	492
		B Tree Split Child	494
		B Tree Insert	495
		B Tree Insert Nonfull	495
		B Tree Delete	502
19	FibHeap	Make Fib Heap	510
		Fib Heap Insert	510
		Fib Heap Minimum	511
		Fib Heap Union	512
		Fib Heap Extract Min	513
		Consolidate	516
		Fib Heap Link	516
		Fib Heap Decrease Key	519
		Cut	519
		Cascading Cut	519
		Fib Heap Delete	522
20	ProtovEB	Proto vEB Member	541
		Proto vEB Minimum	542
		Proto vEB Maximum	542
		Proto vEB Successor	543
		Proto vEB Predecessor	543
		Proto vEB Insert	544
		Proto vEB Delete	544
	vEB	vEB Tree Minimum	550
		vEB Tree Maximum	550
		vEB Tree Member	550
		vEB Tree Successor	551
		vEB Tree Predecessor	552
		vEB Empty Tree Insert	553
		vEB Tree Insert	553
		vEB Tree Delete	554
21	DisjointSet	Connected Components	563
		Same Component	563
		Make Set	571
		Union	571
		Link	571
		Find Set	571
22	BFS	BFS	595
		Print Path	601
	DFS	DFS	604
		DFS Visit	604
	TopologicalSort	Topological Sort	613
	SCC	Strongly Connected Components	617
23	MST	MST Kruskal	631
		MST Prim	634
24	BellmanFord	Initialize Single Source	648
		Relax	649
		Bellman Ford	651
	DagShortestPaths	Dag Shortest Paths	655
	Dijkstra	Dijkstra	658
25	FloydWarshall	Print All Pairs Shortest Path	685
	AllPairsShortestPaths	Extend Shortest Paths	688
		Slow All Pairs Shortest Paths	689
		Faster All Pairs Shortest Paths	691
	FloydWarshall	Floyd Warshall	695
	TransitiveClosure	Transitive Closure	698
	Johnson	Johnson	704
26	FordFulkerson	Ford Fulkerson	724
	MaximumBipartiteMatching	Maximum Bipartite Matching	733
	RelabelToFront	Push	739
		Relabel	740
		Initialize Preflow	740
		Discharge	751
		Relabel To Front	755
27	Fib	Fib	775
		P Fib	776
	MatVec	Mat Vec	785
		Mat Vec Main Loop	785
	RaceExample	Race Example	788
	MatVec	Mat Vec Wrong	790
	PSquareMatrixMultiply	P Square Matrix Multiply	793
		P Matrix Multiply Recursive	794
		P Matrix Multiply Strassen	794
	PMergeSort	Merge Sort prime	797
		Binary Search	799
		P Merge	800
		P Merge Sort	803
28	LUPSolve	LUP Solve	817
		LU Decomposition	821
		LUP Decomposition	824
	MatrixInverse	Matrix Inverse	828
	LeastSquareApprox	Least Square Approx	837
29	Simplex	Pivot	869
		Simplex	871
		Initialize Simplex	887
30	RecursiveFFT	Recursive FFT	911
		Inverse FFT	913
		Polynomial Multiply	914
	IterativeFFT	Iterative FFT	917
		Bit Reversal Copy	918
31	Euclid	Euclid	935
		Extended Euclid	937
	ModLinEquationSolver	Modular Linear Equation Solver	949
	ModularExponentiation	Modular Exponentiation	957
	Pseudoprime	Pseudoprime	967
	MillerRabin	Witness	969
		Miller Rabin	970
	PollardRho	Pollard Rho	977
32	NaiveStringMatcher	Naive String Matcher	988
	RabinKarpMatcher	Rabin Karp Matcher	993
	FiniteAutomatonMatcher	Finite Automaton Matcher	999
		Compute Transition Function	1001
	KMPMatcher	KMP Matcher	1005
		Compute Prefix Function	1006
33	SegmentsIntersect	Segments Intersect	1018
		Direction	1018
		On Segment	1018
	AnySegmentsIntersect	Insert	1024
		Delete	1024
		Above	1024
		Below	1024
		Any Segments Intersect	1025
	GrahamScan	Graham Scan	1031
	JarvisMarch	Jarvis March	1038
	ClosestPairPoints	Closest Pair Points	1043
35	ApproxVertexCover	Approx Vertex Cover	1109
	ApproxTSPTour	Approx TSP Tour	1112
	GreedySetCover	Greedy Set Cover	1119
	ApproxMinWeightVC	Approx Min Weight VC	1126
	SubsetSum	Exact Subset Sum	1129
		Trim	1130
		Approx Subset Sum	1131

Directory Structure

• include/<Name>.hpp: header file that contains the actual algorithm
• src/<Name>Main.hpp: C++ program that runs the algorithm on some data
• src/<Name>Test.hpp: C++ program that runs test on the algorithm
• bin/<Name>(Main|Test): Executable of src/<Name>(Main|Test).hpp
• bin/<Name>(Main|Test).d: Dependencies of src/<Name>(Main|Test).hpp

Supplementary Files

• Graph.hpp, GraphMain.cpp, GraphTest.cpp: Graph-related classes
• graph_utils.hpp: utility functions for graphs
• output_integers.hpp: print a vector
• print_ptr.hpp: print a pointer
• print_tree.hpp: print a tree using ASCII art (inspired by UBC CS221)
• random_integers.hpp: generate a random integer or vector of integers
• utils.hpp: utility functions for cpp files

Supplementary Programs

• include_check.py: identifies unnecessary includes
• dot.sh: generate a graphviz graph from stdin

Example

$ ls include/Fib.hpp src/FibMain.cpp src/FibTest.cpp
include/Fib.hpp  src/FibMain.cpp  src/FibTest.cpp
$ make bin/FibMain > /dev/null
$ bin/FibMain
n       a       b       a == b
10      55      55      true
$ bin/FibMain 19
n       a       b       a == b
19      4181    4181    true
$ make bin/FibTest > /dev/null
$ bin/FibTest
0       0       0       0
1       1       1       1
2       1       1       1
3       2       2       2
4       3       3       3
5       5       5       5
6       8       8       8
7       13      13      13
8       21      21      21
9       34      34      34
10      55      55      55
11      89      89      89
12      144     144     144
13      233     233     233
14      377     377     377
15      610     610     610
16      987     987     987
17      1597    1597    1597
18      2584    2584    2584
19      4181    4181    4181
20      6765    6765    6765
$ echo $?
0
$

Continuous Integration

.github/workflows/build.yml defines the continuous integration workflow of this project. All the targets are built and tested. The CI succeeds if all tests pass.

Difference from the "algorithm" project

• Separated header files from main functions.
• Added tests to all algorithms.
• Fixed some bugs in algorithms.
• Added continuous integration (CI) using Github Actions.
• Switched to using std::mt19937 to generate random numbers.
• Removed dependencies on non-original work (printtree.hpp).
• Resolved memory leaks.