User contributions for Admin

15 February 2023

• 10:3810:38, 15 February 2023 diff hist +277‎ N Fringe (Informed Search Informed Search) ‎ Created page with "== Time Complexity == $O(b^d)$ == Space Complexity == $O(b^d)$ words (Stores all generated nodes in memory) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2005 == Reference ==" current
• 10:3810:38, 15 February 2023 diff hist +365‎ N Field D* (Informed Search Informed Search) ‎ Created page with "== Time Complexity == $O(b^d)$ == Space Complexity == $O(b^d)$ words (Stores all generated nodes in memory) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference == https://www.ri.cmu.edu/pub_files/pub4/ferguson_david_2006_3/ferguson_david_2006_3.pdf" current
• 10:3810:38, 15 February 2023 diff hist +344‎ N D* (Informed Search Informed Search) ‎ Created page with "== Time Complexity == $O(b^d)$ == Space Complexity == $O(b^d)$ words (Stores all generated nodes in memory) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1994 == Reference == https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.15.3683" current
• 10:3810:38, 15 February 2023 diff hist +354‎ N Block A* (Informed Search Informed Search) ‎ Created page with "== Time Complexity == $O(b^d)$ == Space Complexity == $O(b^d)$ words (Stores all generated nodes in memory) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2011 == Reference == https://webdocs.cs.ualberta.ca/~holte/Publications/aaai11PeterYapFinal.pdf" current
• 10:3810:38, 15 February 2023 diff hist +220‎ N Incremental Heuristic Search ( Informed Search) ‎ Created page with "== Time Complexity == $O(b^d)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1968 == Reference ==" current
• 10:3810:38, 15 February 2023 diff hist +329‎ N Greedy Best-First Search (Informed Search Informed Search) ‎ Created page with "== Time Complexity == $O(b^d)$ == Space Complexity == $O(b^d)$ words (https://en.wikipedia.org/wiki/Breadth-first_search: Stores all generated nodes in memory) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1959 == Reference ==" current
• 10:3810:38, 15 February 2023 diff hist +598‎ N Press, Teukolsky, Flannery (Square Matrix LU Decomposition LU Decomposition) ‎ Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $\tilde{O}(n)$ words (Derived: The only auxiliary structure used is a list called "vv" that has one entry per row of the input matrix to store some sort of scaling metric) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2007 == Reference == https://books.google.com/books?hl=en&lr=&id=1aAOdzK3FegC&oi=fnd&pg=PA1&dq=T..."
• 10:3810:38, 15 February 2023 diff hist +235‎ N David ( LU Decomposition) ‎ Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference ==" current
• 10:3810:38, 15 February 2023 diff hist +528‎ N Randomized LU Decomposition (Rectangular Matrix LU Decomposition LU Decomposition) ‎ Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $\tilde{O}(nl + ml)$ words (Derived: Two intermediate auxiliary matrices of sizes $n \times l$ and $m \times l$ for the input matrix of size $m \times n$) == Description == == Approximate? == Approximate Approximation Factor: See Theorem 4.3 in original paper for error bound == Randomized? == Yes, Monte Carlo == Model of Computation == Word RAM == Year == 2016 == Reference == https://www.sc..." current
• 10:3810:38, 15 February 2023 diff hist +235‎ N Closed formula ( LU Decomposition) ‎ Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1975 == Reference ==" current
• 10:3810:38, 15 February 2023 diff hist +382‎ N Shanks's square forms factorization (SQUFOF) (Second Category Integer Factoring Integer Factoring) ‎ Created page with "== Time Complexity == $O({2}^{(n/{4})$}) == Space Complexity == $O(n)$? bits (Constant number of O(n)-bit integers) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 2007 == Reference == https://www.ams.org/journals/mcom/2008-77-261/S0025-5718-07-02010-8/S0025-5718-07-02010-8.pdf"
• 10:3810:38, 15 February 2023 diff hist +424‎ N Rational sieve (Second Category Integer Factoring Integer Factoring) ‎ Created page with "== Time Complexity == $O(e^{sqrt(({2}+o({1})$)n*logn)}) == Space Complexity == $O(n+(B/logB)$^{2})? bits (Same general approach as Dixon's algorithm) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1993 == Reference == https://www.ams.org/journals/mcom/1993-61-203/S0025-5718-1993-1182953-4/S0025-5718-1993-1182953-4.pdf" current
• 10:3810:38, 15 February 2023 diff hist +429‎ N Quadratic sieve (Second Category Integer Factoring Integer Factoring) ‎ Created page with "== Time Complexity == - == Space Complexity == $O(n+(B/logB)$^{2})? bits (Same general approach as Dixon's algorithm) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1981 == Reference == https://www.semanticscholar.org/paper/Analysis-and-comparison-of-some-integer-factoring-Pomerance/134b7b065a73d4ca00bb16c7b8bebbde951b0ba0" current
• 10:3810:38, 15 February 2023 diff hist +413‎ N Continued fraction factorization (CFRAC) (Second Category Integer Factoring Integer Factoring) ‎ Created page with "== Time Complexity == $O(e^{\sqrt({2}n*logn)})$ == Space Complexity == $O(n+(B/logB)$^{2})? bits (Same as above? assuming there is a bound parameter implemented) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1931 == Reference == https://www.ams.org/journals/bull/1931-37-10/S0002-9904-1931-05271-X/home.html" current
• 10:3810:38, 15 February 2023 diff hist +643‎ N Dixon's algorithm (Second Category Integer Factoring Integer Factoring) ‎ Created page with "== Time Complexity == $O(e^{({2} \sqrt({2}) \sqrt(n*logn))}){4} == Space Complexity == $O(n+(B/logB)$^{2})? bits (There are pi(B) = O(B/log B) primes in the factor base; need pi(B)+1=O(B/log B) relations involving an integer (which doesn't need to be kept track of) and a pi(B)-bit string of exponents. Also need O(n) bits to perform other computations. Rest is irrelevant asymptotically) == Description == == Approximate? == Exact == Randomized? == No, deter..." current
• 10:3810:38, 15 February 2023 diff hist +320‎ N Euler's factorization method (First Category Integer Factoring Integer Factoring) ‎ Created page with "== Time Complexity == $O({2}^{(n/{2})})$ == Space Complexity == $O(n)$ auxiliary bits (constant number of values which require at most O(n) bits) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1940 == Reference == -"
• 10:3810:38, 15 February 2023 diff hist +360‎ N Fermat's factorization method (First Category Integer Factoring Integer Factoring) ‎ Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O(n)$ auxiliary bits (constant number of values which require at most O(n) bits) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1894 == Reference == https://archive.org/details/oeuvresdefermat02ferm"
• 10:3810:38, 15 February 2023 diff hist +394‎ N Lenstra elliptic curve factorization (First Category Integer Factoring Integer Factoring) ‎ Created page with "== Time Complexity == $O(e^{(\sqrt(({1}+o({1}))n*log n))})$ == Space Complexity == $O(n)$ auxiliary? bits (constant number of values which are expressed in mod N) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1987 == Reference == https://www.jstor.org/stable/1971363?origin=crossref&seq=1"
• 10:3810:38, 15 February 2023 diff hist +364‎ N Williams' p + 1 algorithm (First Category Integer Factoring Integer Factoring) ‎ Created page with "== Time Complexity == $O({2}^ (n))$ == Space Complexity == $O(n)$ auxiliary? bits (constant number of values which are expressed in mod N) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1982 == Reference == https://www.jstor.org/stable/2007633?origin=crossref"
• 10:3810:38, 15 February 2023 diff hist +553‎ N Pollard's p − 1 algorithm (First Category Integer Factoring Integer Factoring) ‎ Created page with "== Time Complexity == $O(B*log B*log^{2}(n)$)? == Space Complexity == $O(n+B)$ auxiliary bits (the number M requires O((log B)*pi(B)) = O(B) bits, and the other numbers require O(n) bits) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1974 == Reference == https://www.cambridge.org/core/journals/mathematical-proceedings-of-the-cambridge-philosophical-society/article/th..."
• 10:3810:38, 15 February 2023 diff hist +373‎ N Pollard's rho algorithm (First Category Integer Factoring Integer Factoring) ‎ Created page with "== Time Complexity == - == Space Complexity == $O(n)$ auxiliary bits (keep track of g (the polynomial; O(1) space), x, y, and d (all O(n) space)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1975 == Reference == https://link.springer.com/article/10.1007%2FBF01933667"
• 10:3810:38, 15 February 2023 diff hist +372‎ N Wheel factorization (First Category Integer Factoring Integer Factoring) ‎ Created page with "== Time Complexity == $O({2}^{n/2})$ == Space Complexity == $O(n)$ auxiliary bits (need to keep track of what number you're currently checking, along with o(n) bits for the wheel (assuming it's small)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1940 == Reference =="
• 10:3810:38, 15 February 2023 diff hist +318‎ N Trial division (First Category Integer Factoring Integer Factoring) ‎ Created page with "== Time Complexity == $O({2}^{n/2})$ == Space Complexity == $O(n)$ auxiliary bits (need to keep track of what number you're currently checking) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1202 == Reference == -"
• 10:3810:38, 15 February 2023 diff hist +427‎ N Chan (APSP on Dense Directed Graphs with Arbitrary Weights; APSP on Dense Undirected Graphs with Arbitrary Weights All-Pairs Shortest Paths (APSP)) ‎ Created page with "== Time Complexity == $O(V^{3} \log^{3} \log V / \log^{2} V)$ == Space Complexity == $O(V^{2})$ words (Derived: Dividing $A$ and $B$ into $V \times q$ and $q \times V$ matrices, in total using $O(V^2)$ space ) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2009 == Reference == http://tmc.web.engr.illinois.edu/moreapsp.pdf"
• 10:3810:38, 15 February 2023 diff hist +354‎ N Chan (Geometrically Weighted) (APSP on Geometrically Weighted Graphs All-Pairs Shortest Paths (APSP)) ‎ Created page with "== Time Complexity == $O(V^{2.{84}4})$ == Space Complexity == $O(l V^{2})$ words (Derived: Compute and store $2l$ $V \times V$ matrices) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2009 == Reference == http://tmc.web.engr.illinois.edu/moreapsp.pdf"
• 10:3810:38, 15 February 2023 diff hist +407‎ N Thorup (APSP on Dense Undirected Graphs with Positive Integer Weights; APSP on Sparse Undirected Graphs with Positive Integer Weights All-Pairs Shortest Paths (APSP)) ‎ Created page with "== Time Complexity == $O(EV)$ == Space Complexity == $O(EV)$ words (https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22.7128&rep=rep1&type=pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1999 == Reference == http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22.7128&rep=rep1&type=pdf"
• 10:3810:38, 15 February 2023 diff hist +295‎ N Pettie & Ramachandran (APSP on Dense Undirected Graphs with Arbitrary Weights; APSP on Sparse Undirected Graphs with Arbitrary Weights All-Pairs Shortest Paths (APSP)) ‎ Created page with "== Time Complexity == $O(EV \log \alpha(E,V))$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Pointer Machine == Year == 2002 == Reference == https://dl.acm.org/citation.cfm?id=545417"
• 10:3810:38, 15 February 2023 diff hist +492‎ N Williams (APSP on Dense Directed Graphs with Arbitrary Weights All-Pairs Shortest Paths (APSP)) ‎ Created page with "== Time Complexity == $O(V^{3} /{2}^{(\log V)^{0.5}})$ == Space Complexity == $O(V^{2})$ words (Derived: discussed with Ryan, uses an auxiliary $V \times V$ matrix, and the space required for the matrix multiplication of $V \times d$ and $d \times V$ matrices is also $O(V^2)$) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2014 == Reference == https://dl.acm.org/citati..."
• 10:3810:38, 15 February 2023 diff hist +390‎ N Seidel's algorithm (APSP on Dense Undirected Unweighted Graphs; APSP on Sparse Undirected Unweighted Graphs All-Pairs Shortest Paths (APSP)) ‎ Created page with "== Time Complexity == $O (V^{2.{37}3} \log V)$ == Space Complexity == $O(V^{2})$ words (Derived: Uses four auxiliary $V \times V$ matrices) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1995 == Reference == https://www.sciencedirect.com/science/article/pii/S0022000085710781?via%3Dihub"
• 10:3710:37, 15 February 2023 diff hist +357‎ N Floyd–Warshall algorithm (APSP All-Pairs Shortest Paths (APSP)) ‎ Created page with "== Time Complexity == $O(V^{3})$ == Space Complexity == $O(V^{2})$ words (Derived: Uses a $V \times V$ matrix to store and calculate distances) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1962 == Reference == https://dl.acm.org/citation.cfm?id=368168"
• 10:3710:37, 15 February 2023 diff hist +368‎ N Shimbel Algorithm (APSP on Dense Directed Graphs with Arbitrary Weights All-Pairs Shortest Paths (APSP)) ‎ Created page with "== Time Complexity == $O(V^{4})$ == Space Complexity == $O(V^{2})$ words (Derived: Uses a $V \times V$ matrix to store and calculate distances) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1953 == Reference == https://link.springer.com/article/10.1007/BF02476438"
• 10:3710:37, 15 February 2023 diff hist +397‎ N Thorup's algorithm (Nonnegative Integer Weights Shortest Path (Directed Graphs)) ‎ Created page with "== Time Complexity == $O(E + V min(log log V, log log L))$ == Space Complexity == $O(V)$? ("linear-space queue") words (https://dl.acm.org/doi/10.1016/j.jcss.2004.04.003) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 2004 == Reference == https://dl.acm.org/doi/10.1016/j.jcss.2004.04.003" current
• 10:3710:37, 15 February 2023 diff hist +354‎ N Gabow Ahuja Algorithm (Nonnegative Integer Weights Shortest Path (Directed Graphs)) ‎ Created page with "== Time Complexity == $O(E + V*((log(L))^{0.5}) )$ == Space Complexity == $O(m + log C)$ words (https://dl.acm.org/doi/10.1145/77600.77615) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1990 == Reference == https://dl.acm.org/doi/10.1145/77600.77615"
• 10:3710:37, 15 February 2023 diff hist +342‎ N Gabow's algorithm (Nonnegative Weights Shortest Path (Directed Graphs)) ‎ Created page with "== Time Complexity == $O(E logL/log({2}+(E/V)))$ == Space Complexity == $O(V+E)$? words ((keeping track of new graphs?)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1983 == Reference == https://ieeexplore.ieee.org/document/4568085"
• 10:3710:37, 15 February 2023 diff hist +406‎ N Dijkstra's algorithm with Fibonacci heap (Johnson 1981; Karlsson & Poblete 1983) (Nonnegative Integer Weights Shortest Path (Directed Graphs)) ‎ Created page with "== Time Complexity == $O(E log log L)$ == Space Complexity == $O(V+L)$ words (https://www.sciencedirect.com/science/article/pii/0166218X8390104X?via%3Dihub) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1981 == Reference == https://www.sciencedirect.com/science/article/pii/0166218X8390104X?via%3Dihub"
• 10:3710:37, 15 February 2023 diff hist +418‎ N Dijkstra's algorithm with Fibonacci heap (Fredman & Tarjan 1984; Fredman & Tarjan 1987) (Nonnegative Weights Shortest Path (Directed Graphs)) ‎ Created page with "== Time Complexity == $O(E + V log V)$ == Space Complexity == $O(V)$ auxiliary words (keeping track of distances/previous node in path, along with heap) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1984 == Reference == https://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/fibonacci%20heaps.pdf"
• 10:3710:37, 15 February 2023 diff hist +373‎ N Dijkstra's algorithm with binary heap (Johnson 1977) (Nonnegative Weights Shortest Path (Directed Graphs)) ‎ Created page with "== Time Complexity == $O((E + V) log V)$ == Space Complexity == $O(V)$ auxiliary words (keeping track of distances/previous node in path, along with heap) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1977 == Reference == https://dl.acm.org/citation.cfm?id=321993"
• 10:3710:37, 15 February 2023 diff hist +389‎ N Dijkstra's algorithm with list (Whiting & Hillier 1960) (Nonnegative Weights Shortest Path (Directed Graphs)) ‎ Created page with "== Time Complexity == $O( V² )$ == Space Complexity == $O(V)$ auxiliary words (keeping track of distances/previous node in path, along with list) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1960 == Reference == https://www.jstor.org/stable/3007178?seq=1#page_scan_tab_contents"
• 10:3710:37, 15 February 2023 diff hist +326‎ N Bellman–Ford algorithm (Dantzig 1960) (Nonnegative Weights Shortest Path (Directed Graphs)) ‎ Created page with "== Time Complexity == $O( V² logV)$ == Space Complexity == $O(E)$ (total) words (can be easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1960 == Reference == https://www.jstor.org/stable/pdf/2627005.pdf"
• 10:3710:37, 15 February 2023 diff hist +381‎ N Bellman–Ford algorithm (Shimbel 1955; Bellman 1958; Moore 1959) (general weights Shortest Path (Directed Graphs)) ‎ Created page with "== Time Complexity == $O(VE)$ == Space Complexity == $O(V)$ auxiliary words (keeping track of distances) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1959 == Reference == https://www.ams.org/journals/qam/1958-16-01/S0033-569X-1958-0102435-2/S0033-569X-1958-0102435-2.pdf"
• 10:3710:37, 15 February 2023 diff hist +370‎ N Bellman–Ford algorithm (Ford 1956) (general weights Shortest Path (Directed Graphs)) ‎ Created page with "== Time Complexity == $O( V² EL)$ == Space Complexity == $O(E)$ words (number of equations in LP; each equation has a constant number of variables) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1956 == Reference == https://apps.dtic.mil/sti/pdfs/AD0422842.pdf"
• 10:3710:37, 15 February 2023 diff hist +432‎ N Dyer (2-dimensional array representation Closest Pair Problem) ‎ Created page with "== Time Complexity == $O(n)$ using $O(n^{2})$ processors == Space Complexity == $O(n^{2})$ words (https://www.sciencedirect.com/science/article/pii/0020019080900356) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == log-space pyramid cellular automaton == Year == 1980 == Reference == https://www.sciencedirect.com/science/article/pii/0020019080900356" current
• 10:3710:37, 15 February 2023 diff hist +324‎ N Shamos; Hoey (2-dimensional space, Euclidean metric Closest Pair Problem) ‎ Created page with "== Time Complexity == $O(n logn)$ == Space Complexity == $O(n)$ words (Voronoi diagrams require O(n) space) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1975 == Reference == https://ieeexplore.ieee.org/document/4567872"
• 10:3710:37, 15 February 2023 diff hist +377‎ N Hinrichs; Nievergelt; Schorn (2-dimensional space, l m (or l infty) norm Closest Pair Problem) ‎ Created page with "== Time Complexity == $O(n logn)$ == Space Complexity == $O(n)$ words (https://www.sciencedirect.com/science/article/pii/0020019088901500) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1988 == Reference == https://www.sciencedirect.com/science/article/pii/0020019088901500"
• 10:3710:37, 15 February 2023 diff hist +372‎ N Bentley; Shamos (k-dimensional space, l m (or l infty) norm Closest Pair Problem) ‎ Created page with "== Time Complexity == $O(kn logn)$ == Space Complexity == $O(kn)$? words (keep track of all sorted lists in each dimension; re-use space from recursive calls) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1976 == Reference == https://dl.acm.org/citation.cfm?id=803652"
• 10:3710:37, 15 February 2023 diff hist +372‎ N Bentley (k-dimensional space, l m (or l infty) norm Closest Pair Problem) ‎ Created page with "== Time Complexity == $O(kn logn)$ == Space Complexity == $O(kn)$? words (keep track of all sorted lists in each dimension; re-use space from recursive calls) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1980 == Reference == https://dl.acm.org/citation.cfm?id=358850"
• 10:3710:37, 15 February 2023 diff hist +309‎ N Rabin' Algorithm (k-dimensional space, l m (or l infty) norm Closest Pair Problem) ‎ Created page with "== Time Complexity == $O({3}^k*n^{2})$ == Space Complexity == $O(n)$ words (can be easily derived) == Description == == Approximate? == Exact == Randomized? == Yes, Las Vegas == Model of Computation == Real RAM == Year == 1976 == Reference == https://dl.acm.org/citation.cfm?id=540196" current
• 10:3710:37, 15 February 2023 diff hist +377‎ N F. Preparata and M. Shamos (k-dimensional space, l m (or l infty) norm Closest Pair Problem) ‎ Created page with "== Time Complexity == $O(kn logn)$ == Space Complexity == $O(kn)$? words (keep track of all sorted lists in each dimension; re-use space from recursive calls) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1986 == Reference == https://www.springer.com/gp/book/9780387961316"
• 10:3710:37, 15 February 2023 diff hist +385‎ N Fortune and Hopcroft (k-dimensional space, l m (or l infty) norm Closest Pair Problem) ‎ Created page with "== Time Complexity == $O(kn loglogn+n*{3}^k)$ == Space Complexity == $O(n)$ words (can be easily derived? (can re-use space from recursive calls)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1979 == Reference == https://www.sciencedirect.com/science/article/pii/0020019079900851"
• 10:3710:37, 15 February 2023 diff hist +369‎ N Thorup (reverse-delete) (Undirected, General MST Minimum Spanning Tree (MST)) ‎ Created page with "== Time Complexity == $O(E LogV (loglogV)^{3})$ == Space Complexity == $O(E)$ auxiliary? words (can be easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2000 == Reference == https://www.cs.princeton.edu/courses/archive/spr10/cos423/handouts/NearOpt.pdf"