User contributions for Admin
Jump to navigation
Jump to search
15 February 2023
- 10:3510:35, 15 February 2023 diff hist +252 N The SUSAN corner detector ( Corner Detection) Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 1997 == Reference ==" current
- 10:3510:35, 15 February 2023 diff hist +325 N L. Kitchen and A. Rosenfeld (Grey-scale Corner Detection) Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 1982 == Reference == https://www.sciencedirect.com/science/article/abs/pii/0167865582900204" current
- 10:3410:34, 15 February 2023 diff hist +299 N Harris and Stephens algorithm ( Corner Detection) Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 1988 == Reference == http://www.bmva.org/bmvc/1988/avc-88-023.pdf" current
- 10:3410:34, 15 February 2023 diff hist +412 N Barvinok (Geometric Maximum TSP The Traveling-Salesman Problem) Created page with "== Time Complexity == $O(V^{2} loglogE)$ == Space Complexity == $O(V)$? memory cells (Derived: One memory cell per tunnel-city pair, with one tunnel total) == Description == Tunneling == Approximate? == Approximate Approximation Factor: ? == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 2003 == Reference == https://dl.acm.org/doi/10.1145/876638.876640"
- 10:3410:34, 15 February 2023 diff hist +377 N Dantzig-Fulkerson-Johnson (DFJ) formulation (Minimum TSP The Traveling-Salesman Problem) Created page with "== Time Complexity == $O({1.674}^V E^{2})$ == Space Complexity == $O({2}^V)$ words (http://web.ist.utl.pt/~ist11038/CD_Casquilho/TSP1992EJOR_Laporte.pdf) == Description == ILP formulation == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1954 == Reference == https://doi.org/10.1287/opre.2.4.393" current
- 10:3410:34, 15 February 2023 diff hist +426 N Miller-Tucker-Zemlin (MTZ) formulation (Minimum TSP The Traveling-Salesman Problem) Created page with "== Time Complexity == $exp(V)$ == Space Complexity == $O(V^{4})$ words (Derived: V^2 + 2V constraints on V^2 variables, most integer programs use space of O(nm) where n=#vars and m=#constraints) == Description == ILP formulation == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1960 == Reference == https://dl.acm.org/doi/10.1145/321043.321046" current
- 10:3410:34, 15 February 2023 diff hist +407 N Micali and Vazirani ( Maximum Cardinality Matching) Created page with "== Time Complexity == $O(V^{0.5} E)$ == Space Complexity == $O(V)$ not mentioned (https://link.springer.com/content/pdf/10.1007/PL00009186.pdf) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == Restricted Randomness (RR) == Year == 1980 == Reference == https://dl.acm.org/doi/10.1109/SFCS.1980.12"
- 10:3410:34, 15 February 2023 diff hist +321 N Brélaz (DSatur) (3-Graph Coloring Graph Coloring) Created page with "== Time Complexity == $O(V^{2})$ == Space Complexity == $O(V + E)$ words (Derived using adjacency lists) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1979 == Reference == https://dl.acm.org/doi/10.1145/359094.359101"
- 10:3410:34, 15 February 2023 diff hist +341 N Karger, Blum ( Graph Coloring) Created page with "== Time Complexity == $O(poly(V))$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: $\tilde{O}(n^{3/14})$ == Randomized? == No, deterministic == Model of Computation == == Year == 1997 == Reference == http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.4204" current
- 10:3410:34, 15 February 2023 diff hist +428 N Schonhage's algorithm (Matrix Multiplication Matrix Product) Created page with "== Time Complexity == $O(n^{({3}*log52/log110)}) ~ O(n^{2.{521}8})$ == Space Complexity == $O(n^{2})$ words (Derived: Same idea as Strassen's, plus three additional nxn matrices) == Description == == Approximate? == Approximate Approximation Factor: ? == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1980 == Reference == https://epubs.siam.org/doi/abs/10.1137/0210032"
- 10:3410:34, 15 February 2023 diff hist +414 N Bini's algorithm (Matrix Multiplication Matrix Product) Created page with "== Time Complexity == $O(n^{2.{779}9})$ == Space Complexity == $O(n^{2})$ words (Derived: Same idea as Strassen's, plus three additional nxn matrices) == Description == == Approximate? == Approximate Approximation Factor: $O(n logn)$ error == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1979 == Reference == https://doi.org/10.1016/0020-0190(79)90113-3" current
- 10:3410:34, 15 February 2023 diff hist +433 N Chin (Approximate MCOP Matrix Chain Multiplication) Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ words (Derived: There are a few auxiliary variables, only one of which is variable length. That is a list of length $O(n)$.) == Description == == Approximate? == Approximate Approximation Factor: 1.2485 == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1978 == Reference == https://dl.acm.org/citation.cfm?id=359556" current
- 10:3410:34, 15 February 2023 diff hist +502 N Chandra (Approximate MCOP Matrix Chain Multiplication) Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$? words (Derived: cannot find pdf of original paper or any description of the actual algorithm, but likely the same space as Chin's algorithm) == Description == == Approximate? == Approximate Approximation Factor: 2 == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1975 == Reference == https://www.worldcat.org/title/computing-matrix-chain-products-in-near-..." current
- 10:3410:34, 15 February 2023 diff hist +12 Czumaj (Approximate MCOP Matrix Chain Multiplication) No edit summary Tag: Reverted
- 10:3410:34, 15 February 2023 diff hist +511 N Czumaj (Approximate MCOP Matrix Chain Multiplication) Created page with "== Time Complexity == $O(\log n)$ == Space Complexity == $O(n)$ words? (Derived: solving the optimal triangulation problem of a convex polygon where there are $n+1$ vertices and $n+1$, so total $O(n)$ auxiliary space) == Description == == Approximate? == Approximate Approximation Factor: 1.1547 == Randomized? == No, deterministic == Model of Computation == CREW PRAM == Year == 1996 == Reference == https://citeseerx.ist.psu.edu/viewdoc/download?d..."
- 10:3410:34, 15 February 2023 diff hist +300 N Dynamic Programming (Change-Making Problem Change-Making Problem) Created page with "== Time Complexity == $O(Sn)$ == Space Complexity == $O(Sn)$ words (Easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1953 == Reference == https://dl.acm.org/doi/10.1145/321864.321874" current
- 10:3410:34, 15 February 2023 diff hist +258 N Brute Force (Change-Making Problem Change-Making Problem) Created page with "== Time Complexity == $O(S^n)$ == Space Complexity == $O(n)$ words (Easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == NA" current
- 10:3410:34, 15 February 2023 diff hist +255 N Dynamic Programming (Rod-Cutting Problem Rod-Cutting Problem) Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words (easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1953 == Reference ==" current
- 10:3410:34, 15 February 2023 diff hist +257 N Brute Force (Rod-Cutting Problem Rod-Cutting Problem) Created page with "== Time Complexity == $O(n*{2}^n)$ == Space Complexity == $O(n)$ words (easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==" current
- 10:3410:34, 15 February 2023 diff hist +390 N PMS (Motif Search Motif Search) Created page with "== Time Complexity == $O(nm^{2} \sigma)$ == Space Complexity == $O(m^{2} n)$ words (https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2966288/pdf/1471-2105-11-S8-S1.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2007 == Reference == https://ieeexplore.ieee.org/abstract/document/4359890" current
- 10:3410:34, 15 February 2023 diff hist +389 N Risotto (Motif Search Motif Search) Created page with "== Time Complexity == $O(mn^{2} \sigma)$ == Space Complexity == $O(mn^{2})$ words (https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2966288/pdf/1471-2105-11-S8-S1.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference == https://link.springer.com/chapter/10.1007/11682462_69" current
- 10:3410:34, 15 February 2023 diff hist +392 N Census (Motif Search Motif Search) Created page with "== Time Complexity == $O(k nm \sigma)$ == Space Complexity == $O(mnk)$ words (https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2966288/pdf/1471-2105-11-S8-S1.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2003 == Reference == https://link.springer.com/chapter/10.1007/978-3-540-45078-8_5" current
- 10:3410:34, 15 February 2023 diff hist +372 N Mitra (Motif Search Motif Search) Created page with "== Time Complexity == $O(k nm \sigma)$ == Space Complexity == $O(mnk)$ words (https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2966288/pdf/1471-2105-11-S8-S1.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2002 == Reference == https://pubmed.ncbi.nlm.nih.gov/12169566/" current
- 10:3410:34, 15 February 2023 diff hist +390 N Speller (Motif Search Motif Search) Created page with "== Time Complexity == $O(mn^{2} \sigma)$ == Space Complexity == $O(mn^{2}/w)$ words (https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2966288/pdf/1471-2105-11-S8-S1.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1998 == Reference == https://link.springer.com/chapter/10.1007/BFb0054337" current
- 10:3410:34, 15 February 2023 diff hist +388 N Perumalla and Deo (1D Maximum Subarray Maximum Subarray Problem) Created page with "== Time Complexity == $O(log n)$ == Space Complexity == $O(n)$ auxiliary words (constant number of arrays as outlined in algorithm) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == EREW PRAM == Year == 1995 == Reference == https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.24.1291&rep=rep1&type=pdf"
- 10:3410:34, 15 February 2023 diff hist +301 N Kadane's Algorithm (1D Maximum Subarray Maximum Subarray Problem) Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary words (keep track of current tail sum and best sum) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1982 == Reference == -" current
- 10:3410:34, 15 February 2023 diff hist +296 N Shamos (1D Maximum Subarray Maximum Subarray Problem) Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(log n)$ auxiliary words (keep track of recursive maximums) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1978 == Reference == -"
- 10:3410:34, 15 February 2023 diff hist +383 N Faster Brute Force (via x(L:U) = x(L:U-1)+x(U)) (1D Maximum Subarray Maximum Subarray Problem) Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O({1})$ auxiliary words (keep track of which subarray is being computed, along with current maximum) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1977 == Reference == https://dl.acm.org/doi/pdf/10.1145/358234.381162"
- 10:3410:34, 15 February 2023 diff hist +285 N Grenander (1D Maximum Subarray Maximum Subarray Problem) Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words (storing precomputed cumulative sums) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1977 == Reference == -" current
- 10:3410:34, 15 February 2023 diff hist +336 N Brute Force (1D Maximum Subarray Maximum Subarray Problem) Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O({1})$ auxiliary words (keep track of which subarray is being computed, along with current maximum) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1977 == Reference == -"
- 10:3410:34, 15 February 2023 diff hist +382 N Bringman (Subset Sum The Subset-Sum Problem) Created page with "== Time Complexity == $\tilde{O}(nt^{1+\epsilon})$ == Space Complexity == \tilde{O}(nt^\epsilon) (https://arxiv.org/abs/1610.04712) == Description == == Approximate? == Approximate Approximation Factor: (n+t)^{-\Omega(1)} error == Randomized? == Yes, Monte Carlo == Model of Computation == == Year == 2017 == Reference == https://arxiv.org/abs/1610.04712"
- 10:3410:34, 15 February 2023 diff hist +355 N Koiliaris and Xu (Subset Sum The Subset-Sum Problem) Created page with "== Time Complexity == $\tilde{O}(min{\sqrt{n'}t, t^{5/4}, σ})$ == Space Complexity == $O(t)$ (https://dl.acm.org/doi/pdf/10.1145/3329863, Table 1) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2019 == Reference == https://dl.acm.org/doi/pdf/10.1145/3329863"
- 10:3410:34, 15 February 2023 diff hist +356 N Psinger (Subset Sum The Subset-Sum Problem) Created page with "== Time Complexity == $O(n max(S))$ == Space Complexity == $O(t)$ (https://dl.acm.org/doi/pdf/10.1145/3329863, Table 1) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1999 == Reference == https://www.sciencedirect.com/science/article/abs/pii/S0196677499910349"
- 10:3410:34, 15 February 2023 diff hist +338 N Bellman dynamic programming algorithm (Subset Sum The Subset-Sum Problem) Created page with "== Time Complexity == $O(n t)$ == Space Complexity == $O(t)$ (https://dl.acm.org/doi/pdf/10.1145/3329863, Table 1) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1956 == Reference == https://onlinelibrary.wiley.com/doi/10.1002/nav.3800030107"
- 10:3410:34, 15 February 2023 diff hist +339 N Horowitz and Sahni (Subset Sum The Subset-Sum Problem) Created page with "== Time Complexity == $O({2}^{(n/{2})})$ == Space Complexity == $O({2}^{(n/{2})$}) (https://dl.acm.org/doi/10.1145/321812.321823) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1974 == Reference == https://dl.acm.org/doi/10.1145/321812.321823"
- 10:3410:34, 15 February 2023 diff hist +404 N R-tree (Nearest Neighbor Search (NNS) Nearest Neighbor Search) Created page with "== Time Complexity == R-Tree construction: $O(n log n)$ NNS: $O(n)$ == Space Complexity == $O(log n)$ (https://www.sciencedirect.com/science/article/pii/S1877050915019675, Table 2) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1984 == Reference == http://www-db.deis.unibo.it/courses/SI-LS/papers/Gut84.pdf"
- 10:3410:34, 15 February 2023 diff hist +364 N K-d Tree (Nearest Neighbor Search (NNS) Nearest Neighbor Search) Created page with "== Time Complexity == k-d Tree construction: $O(n log n)$ NNS: $O(n)$ == Space Complexity == $O(n)$ (https://dl.acm.org/doi/pdf/10.1145/355744.355745) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1975 == Reference == https://dl.acm.org/doi/pdf/10.1145/355744.355745"
- 10:3410:34, 15 February 2023 diff hist +313 N Linear search (Nearest Neighbor Search (NNS) Nearest Neighbor Search) Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ (Derived: Only ever storing the current shortest distance and the corresponding node) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1940 == Reference == -"
- 10:3410:34, 15 February 2023 diff hist +363 N Zhao-Saalfeld ( Line Simplification) Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ (Derived: There is an auxiliary sleeve set that is $O(n)$ size worst-case) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1997 == Reference == http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.494.7321"
- 10:3410:34, 15 February 2023 diff hist +394 N Lang simplification ( Line Simplification) Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ (Derived: The only auxiliary space used is the current search line and the distance from a point in the search interval to the search line, which is all $O(1)$ space) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1969 == Reference == -"
- 10:3410:34, 15 February 2023 diff hist +469 N Opheim simplification ( Line Simplification) Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ (Derived: The only auxiliary space used is the current search ray and the current best, the distances from the next point to the ray and to the ray's origin, candidate point to stay in the simplified line) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1981 == Reference == http://dx.doi.org/10.2312/eg.19811012"
- 10:3410:34, 15 February 2023 diff hist +341 N Reumann–Witkam ( Line Simplification) Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ (Derived: The only auxiliary space used is the current search line and the distance from the next point to the line.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1974 == Reference =="
- 10:3410:34, 15 February 2023 diff hist +325 N Visvalingam–Whyatt ( Line Simplification) Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ (Derived: Storing each points effective area) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1993 == Reference == https://hull-repository.worktribe.com/output/459275"
- 10:3310:33, 15 February 2023 diff hist +383 N Ramer–Douglas–Peucker algorithm ( Line Simplification) Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$? (Derived: Recursive algorithm that has a worst-case recursion tree depth of O(n)?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1972 == Reference == https://www.sciencedirect.com/science/article/abs/pii/S0146664X72800170"
- 10:3310:33, 15 February 2023 diff hist +299 N Long Multiplication ( Multiplication) Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ auxiliary bits (Easily derived (needed for intermediate results)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1940 == Reference =="
- 10:3310:33, 15 February 2023 diff hist +443 N Toom-3 ( Multiplication) Created page with "== Time Complexity == $O(n^{1.{4}6})$ == Space Complexity == $O(n)$ auxiliary bits (Re-use space across recursive subcalls (to obtain the recursion S(n) = S(n/3)+O(n))) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1969 == Reference == https://www.ams.org/journals/tran/1969-142-00/S0002-9947-1969-0249212-8/S0002-9947-1969-0249212-8.pdf"
- 10:3310:33, 15 February 2023 diff hist +433 N Karatsuba Algorithm ( Multiplication) Created page with "== Time Complexity == $O(n^{1.{5}8})$ == Space Complexity == $O(n)$ auxiliary bits (Re-use space across recursive subcalls (to obtain the recursion S(n) = S(n/2)+O(n))) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1962 == Reference == http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=dan&paperid=26729&option_lang=eng"
- 10:3310:33, 15 February 2023 diff hist +368 N Rabin–Scott powerset construction ( NFA to DFA conversion) Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O({1})$ (Derived: besides the O(2^n) output nodes and the O(n) input nodes, there's nothing to store) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1959 == Reference == https://ieeexplore.ieee.org/document/5392601" current
- 10:3310:33, 15 February 2023 diff hist +378 N Fast clipping (Rectangular Window Line Clipping) Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary words (Easily derived (O(1) per segment, space can be re-used)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1987 == Reference == https://www.sciencedirect.com/science/article/pii/0097849387900616"
- 10:3310:33, 15 February 2023 diff hist +354 N Nicholl–Lee–Nicholl (Rectangular Window Line Clipping) Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary words (Easily derived (O(1) per segment, space can be re-used)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1987 == Reference == https://dl.acm.org/doi/10.1145/37401.37432"