Skip to content

Latest commit

 

History

History
228 lines (125 loc) · 14.1 KB

README.md

File metadata and controls

228 lines (125 loc) · 14.1 KB
Raw

DROP Graph

DROP Graph Bellman Ford Package implements the Bellman Ford Shortest Path Family of Algorithms.

Component Packages

  • AStar DROP A+ Search Package implements A* Heuristic Shortest Path Family.

  • Asymptote DROP Graph Asymptote Package implements Big O Algorithm Asymptotic Analysis.

  • Bellman Ford DROP Graph Asymptote Package implements Big O Algorithm Asymptotic Analysis.

  • Core DROP Graph Core Package contains the Vertexes, Edges, Trees, Forests, and Graphs.

  • Decision Tree DROP Graph Decision Tree Package contains the Property Estimates for Decision Trees.

  • Heap DROP Graph Heap Package contains the Heap Based Priority Queue Implementations.

  • MST DROP Graph MST computes the Agnostic Minimum Spanning Tree Properties.

  • MST Greedy DROP Graph MST Greedy Package contains the Greedy Algorithms for MSTs and Forests.

  • Search DROP Graph Search Package implements BFS, DFS, and Vertex Ordering.

  • Selection DROP Graph Selection Package implements kth Order Statistics Selectors.

  • Shortest Path DROP Graph Shortest Path Package implements the Shortest Path Generation Algorithm Family.

  • Soft Heap DROP Soft Heap contains Soft Heap Based Approximate Priority Queue Implementation.

  • Sub-Array DROP Graph Sub-array Path Package implements the Algorithms for Sub-set Sum, k-Sum, and Maximum Sub-array Problems.

  • Tree Builder DROP Graph Tree Builder maintains the Stubs for Spanning Tree Construction.

References

  • Aziz, A., and A. Prakash (2010): Algorithms for Interviews http://users.ece.utexas.edu/~adnan/afi-samples-new.pdf

  • Bang-Jensen, J., and G. Gutin (2008): Digraphs: Theory, Algorithms, and Applications 2nd Edition Springer

  • Bader, D. A., and G. Cong (2006): Fast Shared Memory Algorithms for computing the Minimum Spanning Forests of Sparse Graphs Journal of Parallel and Distributed Computing 66 (11) 1366-1378

  • Bentley, J. (1984): Programming Pearls: Algorithm Design Techniques Communications of the ACM 27 (9) 865-873

  • Bentley, J. (1989): Programming Pearls nd Edition Addison-Wesley Reading MA

  • Bollobas, B. (1998): Modern Graph Theory Springer

  • Blum, M., R. W. Floyd, V. Pratt, R. L. Rivest, and R. E. Tarjan (1973): Time Bounds for Selection Journal of Computer and System Sciences 7 (4) 448-461

  • Bringmann, K. (2017): A near-linear Pseudo-polynomial Time Algorithm for Subset Sums Proceedings of the 28th Annual ACM SIAM Symposium on Discrete Algorithms 1073-1084

  • Brodal, G. S., G. Lagogiannis, and R. E. Tarjan (2012): Strict Fibonacci Heaps Proceedings on the 44th Symposium on the Theory of Computing; STOC 12 1177-1184

  • Brodal, G. S. (1996): Priority Queue on Parallel Machines Scandinavian Workshop on Algorithm Theory; SWAT 96 416-427

  • Brodal, G. S., and C. Okasaki (1996): Optimal Purely Functional Priority Queues Journal of Functional Programming 6 (6) 839-857

  • Brown, M. R. (1978): Implementation and Analysis of Binomial Queue Algorithms SIAM Journal on Computing 7 (3) 298-319

  • Chan, T. M. (2018): More Logarithmic Factor Speedups for 3SUM, (median+) Convolution, and some Geometric 3SUM Hard Problems Proceedings of the 29th Annual ACM SIAM Symposium on Discrete Algorithms 881-897

  • Chazelle, B. (2000): The Discrepancy Method: Randomness and Complexity https://www.cs.princeton.edu/~chazelle/pubs/book.pdf

  • Chazelle, B. (2000): The Soft Heap: An Approximate Priority Queue with Optimal Error Rate Journal of the Association for Computing Machinery 47 (6) 1012-1027

  • Chazelle, B. (2000): A Minimum Spanning Tree Algorithm with Inverse-Ackerman Type Complexity Journal of the Association for Computing Machinery 47 (6) 1028-1047

  • Coppin, B. (2004): Artificial Intelligence Illuminated Jones and Bartlett Learning

  • Cormen, T., C. E. Leiserson, R. Rivest, and C. Stein (2009): Introduction to Algorithms 3rd Edition MIT Press

  • Dechter, R., and J. Pearl (1985): Generalized Best-first Search Strategies and the Optimality of A* Journal of the ACM 32 (3) 505-536

  • de Fraysseix, H., O. de Mendez, and P. Rosenstiehl (2006): Tremaux Trees and Planarity International Journal of Foundations of Computer Science 17 (5) 1017-1030

  • Dijkstra, E. W. (1959): A Note on Two Problems in Connection with Graphs Numerische Mathematik 1 269-271

  • Eppstein, D. (1999): Spanning Trees and Spanners https://www.ics.uci.edu/~eppstein/pubs/Epp-TR-96-16.pdf

  • Eppstein, D. (2007): Blum-style Analysis of Quickselect https://11011110.github.io/blog/2007/10/09/blum-style-analysis-of.html

  • Felner, A. (2011): Position Paper: Dijkstra Algorithm versus Uniform Cost Search or a Case against Dijkstra Algorithm Proceedings of the 4th International Symposium on Combinatorial Search 47-51

  • Floyd, R. W., and R. L. Rivest (1975): Expected Time Bounds for Selection Communications of the ACM 18 (3) 165-172

  • Floyd, R. W., and R. L. Rivest (1975): The Algorithm SELECT: for finding the ith smallest of n Elements Communications of the ACM 18 (3) 173

  • Gajentaan, A., and M. H. Overmars (1995): On a Class of O(n2) Problems in Computational Geometry Computational Geometry: Theory and Applications 5 (3) 165-185

  • Grama, A., A. Gupta, G. Karypis, and V. Kumar (2003): Introduction to Parallel Computing 2nd Edition Addison Wesley

  • Gries, D. (1982): A Note on a Standard Strategy for developing Loop Invariants and Loops Science of Computer Programming 2 (3) 207-214

  • Gross, J. L., and J. Yellen (2005): Graph Theory and its Applications Springer

  • Hart, P. E., N. J. Nilsson, and B. Raphael (1968): A Formal Basis for the Heuristic Determination of the Minimum Cost Paths IEEE Transactions on Systems Sciences and Cybernetics 4 (2) 100-107

  • Hayward, R., and C. McDiarmid (1991): Average Case Analysis of Heap-building by Repeated Insertion Journal of Algorithms 12 (1) 126-153

  • Hoare, C. A. R. (1961): Algorithm 65: Find Communications of the ACM 4 (1) 321-322

  • Horowitz, E., and S. Sahni (1974): Computing Partitions with Applications to the Knapsack Problem Journal of the ACM 21 (2) 277-292

  • Kagan, E., and I. Ben-Gal (2014): A Group Testing Algorithm with Online Informational Learning IIE Transactions 46 (2) 164-184

  • Kaplan, H., and U. Zwick (2009): A simpler implementation and analysis of Chazelle Soft Heaps https://epubs.siam.org/doi/abs/10.1137/1.9781611973068.53?mobileUi=0

  • Karger, D. R., P. N. Klein, and R. E. Tarjan (1995): A Randomized Linear-Time Algorithm to find Minimum Spanning Trees Journal of the Association for Computing Machinery 42 (2) 321-328

  • Kepner, J., and J. Gilbert (2011): Graph Algorithms in the Language of Linear Algebra Society for Industrial and Applied Mathematics

  • Kleinberg, J., and E. Tardos (2022): Algorithm Design 2nd Edition Pearson

  • Koiliaris, K., and C. Xu (2016): A Faster Pseudo-polynomial Time Algorithm for Subset Sum https://arxiv.org/abs/1507.02318 arXiV

  • Kopelowitz, T., S. Pettie, and E. Porat (2014): Higher Lower Bounds from the 3SUM Conjecture https://arxiv.org/abs/1407.6756 arXiV

  • Knuth, D. (1997): The Art of Computer Programming 3rd Edition Addison-Wesley

  • Kocay, W., and D. L. Kreher (2004): Graphs, Algorithms, and Optimizations CRC Press

  • Mehlhorn, K., and P. Sanders (2008): Algorithms and Data Structures: The Basic Tool-box Springer

  • Musser, D. R. (1997): Introselect Sorting and Selection Algorithms Software: Practice and Experience 27 (8) 983-993

  • Osipov, V., P. Sanders, and J. Singler (2009): The Filter-Kruskal Minimum Spanning Tree Algorithm http://algo2.iti.kit.edu/documents/fkruskal.pdf

  • Patrascu, M. (2010): Towards Polynomial Lower Bounds for Dynamic Problems Proceedings of the 42nd ACM Symposium on Theory of Computing 603-610

  • Pettie, S., and V. Ramachandran (2002): An Optimal Minimum Spanning Tree Algorithm Journal of the ACM 49 (1) 16-34

  • Pettie, S., and V. Ramachandran (2008): Randomized Minimum Spanning Tree Algorithms using Exponentially Fewer Random Bits ACM Transactions on Algorithms 4 (1) 1-27

  • Quinn, M. J., and N. Deo (1984): Parallel Graph Algorithms ACM Computing Surveys 16 (3) 319-348

  • Reif, J. H. (1985): Depth-first Search is inherently Sequential Information Processing Letters 20 (5) 229-234

  • Russell, S., and P. Norvig (2009): Artificial Intelligence: A Modern Approach 3rd Edition Prentice Hall

  • Russell, S. J. and P. Norvig (2018): Artificial Intelligence: A Modern Approach 4th Edition Pearson

  • Sanders, P., K. Mehlhorn, M. Dietzfelbinger, and R. Dementiev (2019): Sequential and Parallel Algorithms and Data Structures; A Basic Toolbox Springer

  • Sedgewick, R. E., and K. D. Wayne (2011): Algorithms 4th Edition Addison-Wesley

  • Setia, R., A. Nedunchezhian, and S. Balachandran (2015): A New Parallel Algorithm for Minimum Spanning Tree Problem https://hipcor.fatcow.com/hipc2009/documents/HIPCSS09Papers/1569250351.pdf

  • Suchanek, M. A. (2012): Elementary yet Precise Worst-case Analysis of Floyd Heap Construction Program Fundamenta Informaticae 120 (1) 75-92

  • Sundell, H., and P. Tsigas (2005): Fast and Lock-free Concurrent Priority Queues for Multi-threaded Systems Journal of Parallel and Distributed Computing 65 (5) 609-627

  • Takaoka, T. (2002): Efficient Algorithms for the Maximum Sub-array Problem by Distance Matrix Multiplication https://www.sciencedirect.com/science/article/pii/S1571066104003135?via%3Dihub

  • Vuillemin, J. (1978): A Data Structure for Manipulating Priority Queues Communications of the ACM 21 (4) 309-315

  • Wikipedia (2019): Binomial Heap https://en.wikipedia.org/wiki/Binomial_heap

  • Wikipedia (2019): Dijkstra Algorithm https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

  • Wikipedia (2019): Floyd-Rivest Algorithm https://en.wikipedia.org/wiki/Floyd%E2%80%93Rivest_algorithm

  • Wikipedia (2019): Kruskal Algorithm https://en.wikipedia.org/wiki/Kruskal%27s_algorithm

  • Wikipedia (2019): Prim Algorithm https://en.wikipedia.org/wiki/Prim%27s_algorithm

  • Wikipedia (2019): Quickselect https://en.wikipedia.org/wiki/Quickselect

  • Wikipedia (2019): Selection Algorithm https://en.wikipedia.org/wiki/Selection_algorithm

  • Wikipedia (2020): 3Sum https://en.wikipedia.org/wiki/3SUM

  • Wikipedia (2020): A+ Search Algorithm https://en.wikipedia.org/wiki/A*_search_algorithm

  • Wikipedia (2020): Bellman-Ford Algorithm https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm

  • Wikipedia (2020): Binary Heap https://en.wikipedia.org/wiki/Binary_heap

  • Wikipedia (2020): Breadth-first Search https://en.wikipedia.org/wiki/Breadth-first_search

  • Wikipedia (2020): Depth-first Search https://en.wikipedia.org/wiki/Depth-first_search

  • Wikipedia (2020): Introselect https://en.wikipedia.org/wiki/Introselect

  • Wikipedia (2020): Maximum Sub-array Problem https://en.wikipedia.org/wiki/Maximum_subarray_problem

  • Wikipedia (2020): Median Of Medians https://en.wikipedia.org/wiki/Median_of_medians

  • Wikipedia (2020): Minimum Spanning Tree https://en.wikipedia.org/wiki/Minimum_spanning_tree

  • Wikipedia (2020): Priority Queue https://en.wikipedia.org/wiki/Priority_queue

  • Wikipedia (2020): Spanning Tree https://en.wikipedia.org/wiki/Spanning_tree

  • Wikipedia (2020): Subset Sum Problem https://en.wikipedia.org/wiki/Subset_sum_problem

DROP Specifications