Skip to content
This repository has been archived by the owner on Nov 29, 2020. It is now read-only.
/ algorithm Public archive

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

License

Notifications You must be signed in to change notification settings

lxylxy123456/algorithm

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

algorithm

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

!!! Deprecated !!!

This project is deprecated. It has known bug unfixed and will no longer be maintained. Please use https://github.com/lxylxy123456/algorithms instead.

Contents

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

Supplementary Files

  • utils.h: Utils
  • Graph.cpp: Graph classes

Supplementary Programs

  • include_check.py: identifies unnecessary includes
  • vEB_check.py: compare results of ProtovEB.cpp and vEB.cpp
  • dot.sh: generate a graphviz graph from stdin

About

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

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages