User contributions for Admin
Jump to navigation
Jump to search
15 February 2023
- 10:5210:52, 15 February 2023 diff hist +403 N String Graph with Ferragina–Manzini Index (Simpson, Durbin) (De Novo Genome Assembly De Novo Genome Assembly) Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$? words (Requires computing O(n) overlaps for graph; data structures are otherwise linear in space usage) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2010 == Reference == https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2881401/pdf/btq217.pdf" current
- 10:5210:52, 15 February 2023 diff hist +383 N De Bruijn Graph (Idury, Waterman) (De Novo Genome Assembly De Novo Genome Assembly) Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$? words (Requires computing O(n) overlaps for graph; data structures are otherwise linear in space usage) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1994 == Reference == https://www.ncbi.nlm.nih.gov/pubmed/7497130" current
- 10:5210:52, 15 February 2023 diff hist +383 N String Graph (Myers) (De Novo Genome Assembly De Novo Genome Assembly) Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$? words (Requires computing O(n) overlaps for graph; data structures are otherwise linear in space usage) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1994 == Reference == https://www.ncbi.nlm.nih.gov/pubmed/7497129"
- 10:5210:52, 15 February 2023 diff hist +394 N Katajainen and M. Koppinen ( Delaunay Triangulation) Created page with "== Time Complexity == $O(n log log n)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1987 == Reference == https://www.semanticscholar.org/paper/Constructing-Delaunay-triangulations-by-merging-in-Katajainen-Koppinen/b13059c096f37407ea680fec0e61e000f6407292"
- 10:5210:52, 15 February 2023 diff hist +374 N Dwyer (higher dimensions) (General Delaunay Triangulation (d-dimensions) Delaunay Triangulation) Created page with "== Time Complexity == $O(n log log n)$ == Space Complexity == $O(n)$? words (Keep track of O(1) information per triangle related to triangulation??) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1987 == Reference == https://link.springer.com/article/10.1007/BF02574694"
- 10:5210:52, 15 February 2023 diff hist +374 N Drysdale; Su (2-Dimensional Delaunay Triangulation Delaunay Triangulation) Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$? words (See other incremental algorithms) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1996 == Reference == https://web.archive.org/web/20120308043808/http://www.cs.berkeley.edu/~jrs/meshpapers/SuDrysdale.pdf" current
- 10:5210:52, 15 February 2023 diff hist +342 N Fortune (2-Dimensional Delaunay Triangulation Delaunay Triangulation) Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words (See incremental/flipping algorithm space complexities) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1992 == Reference == https://dl.acm.org/doi/10.1145/142675.142695" current
- 10:5210:52, 15 February 2023 diff hist +407 N S-hull (Sinclair) (2-Dimensional Delaunay Triangulation Delaunay Triangulation) Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (Keep track of triangles in current triangulation, based on which points have been added so far and which triangles to remove) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 2010 == Reference == http://www.s-hull.org/paper/s_hull.pdf"
- 10:5210:52, 15 February 2023 diff hist +410 N Dwyer (2-Dimensional Delaunay Triangulation Delaunay Triangulation) Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$? words (Space recursion is S(n)=max(2S(n/2), O(n)) as triangulations from recursive calls are modified in the merge step) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1987 == Reference == https://link.springer.com/article/10.1007/BF01840356"
- 10:5210:52, 15 February 2023 diff hist +424 N Bowyer–Watson algorithm (2-Dimensional Delaunay Triangulation Delaunay Triangulation) Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (Keep track of triangles in current triangulation, based on which points have been added so far and which triangles to remove) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1981 == Reference == https://academic.oup.com/comjnl/article/24/2/167/338200"
- 10:5210:52, 15 February 2023 diff hist +499 N Belloch (2-Dimensional Delaunay Triangulation Delaunay Triangulation) Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (Keep track of triangles in current triangulation, based on which points have been added so far and which triangles to remove (see other incremental algos)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 2006 == Reference == https://web.archive.org/web/20180425231851/https://www.cs.cmu.edu/~ygu1/pape..."
- 10:5210:52, 15 February 2023 diff hist +407 N Guibas; Stofli (2-Dimensional Delaunay Triangulation Delaunay Triangulation) Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (Space recursion is S(n)=max(2S(n/2), O(n)) as triangulations from recursive calls are modified in the merge step) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1985 == Reference == http://www.geom.uiuc.edu/~samuelp/del_project.html"
- 10:5210:52, 15 February 2023 diff hist +427 N De Berg; Cheong (2-Dimensional Delaunay Triangulation Delaunay Triangulation) Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (Keep track of triangles in current triangulation, based on which points have been added so far) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 2008 == Reference == https://web.archive.org/web/20091028054315/http://www.cs.uu.nl/geobook/interpolation.pdf"
- 10:5210:52, 15 February 2023 diff hist +341 N Flipping algorithm (2-Dimensional Delaunay Triangulation Delaunay Triangulation) Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words (Keep track of edges in current triangulation) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1999 == Reference == https://link.springer.com/article/10.1007/PL00009464" current
- 10:5210:52, 15 February 2023 diff hist +346 N Naive algorithm (2-Dimensional Delaunay Triangulation Delaunay Triangulation) Created page with "== Time Complexity == $O(n^{4})$? (previously $O(n^{2})$) == Space Complexity == $O(n)$ words (Keep track of triangles in triangulation, and current triangle being tested) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1934 == Reference == -" current
- 10:5210:52, 15 February 2023 diff hist +315 N 9-point FFT (3-Dimensional Poisson Problem Poisson Problem) Created page with "== Time Complexity == $O(n^{3} logn)$ == Space Complexity == $O(n^{3})$? words (FFT generally requires aux. space equal to dimension of vector?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1978 == Reference =="
- 10:5210:52, 15 February 2023 diff hist +338 N 5-point cyclic reduction (3-Dimensional Poisson Problem Poisson Problem) Created page with "== Time Complexity == $O(n^{3} logn)$ == Space Complexity == $O(n^{3})$? words (Generally uses a constant number of n^3*n^3 matrices where O(n^3) entries are nonempty) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1970 == Reference =="
- 10:5210:52, 15 February 2023 diff hist +338 N 9-point ADI iteration + smooth guess (3-Dimensional Poisson Problem Poisson Problem) Created page with "== Time Complexity == $O(n^{3} logn)$ == Space Complexity == $O(n^{3})$? words (Generally uses a constant number of n^3*n^3 matrices where O(n^3) entries are nonempty) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1969 == Reference =="
- 10:5210:52, 15 February 2023 diff hist +315 N 5-point FFT (3-Dimensional Poisson Problem Poisson Problem) Created page with "== Time Complexity == $O(n^{3} logn)$ == Space Complexity == $O(n^{3})$? words (FFT generally requires aux. space equal to dimension of vector?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1965 == Reference =="
- 10:5210:52, 15 February 2023 diff hist +338 N 9-point ADI iteration (3-Dimensional Poisson Problem Poisson Problem) Created page with "== Time Complexity == $O(n^{3} logn)$ == Space Complexity == $O(n^{3})$? words (Generally uses a constant number of n^3*n^3 matrices where O(n^3) entries are nonempty) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1965 == Reference =="
- 10:5210:52, 15 February 2023 diff hist +382 N 9-point Tensor product (3-Dimensional Poisson Problem Poisson Problem) Created page with "== Time Complexity == $O(n^{4})$ == Space Complexity == $O(n^{3})$? words (Generally uses a constant number of n^3*n^3 matrices where O(n^3) entries are nonempty) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1964 == Reference == https://epubs.siam.org/doi/pdf/10.1137/0113067" current
- 10:5210:52, 15 February 2023 diff hist +327 N 5-point SOR iteration (3-Dimensional Poisson Problem Poisson Problem) Created page with "== Time Complexity == $O(n^{4} logn)$ == Space Complexity == $O(n^{3})$? words (Need one auxiliary O(n^3)-sized vector to store guess, and the scalar sigma) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1954 == Reference =="
- 10:5210:52, 15 February 2023 diff hist +322 N 9-point SOR iteration (3-Dimensional Poisson Problem Poisson Problem) Created page with "== Time Complexity == $O(n^{4})$ == Space Complexity == $O(n^{3})$? words (Need one auxiliary O(n^3)-sized vector to store guess, and the scalar sigma) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1956 == Reference ==" current
- 10:5210:52, 15 February 2023 diff hist +342 N 5-point ADI iteration (3-Dimensional Poisson Problem Poisson Problem) Created page with "== Time Complexity == $O(n^{3} log^{2}n)$ == Space Complexity == $O(n^{3})$? words (Generally uses a constant number of n^3*n^3 matrices where O(n^3) entries are nonempty) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1955 == Reference =="
- 10:5210:52, 15 February 2023 diff hist +338 N 5-point Gauss Seidel iteration (3-Dimensional Poisson Problem Poisson Problem) Created page with "== Time Complexity == $O(n^{5} logn)$ == Space Complexity == $O(n^{3})$? words (Generally uses a constant number of n^3*n^3 matrices where O(n^3) entries are nonempty) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1945 == Reference =="
- 10:5210:52, 15 February 2023 diff hist +305 N 5-point Gauss elimination (3-Dimensional Poisson Problem Poisson Problem) Created page with "== Time Complexity == $O(n^{7})$ == Space Complexity == $O(n^{6})$ words (See Gauss-Jordan elimination, but matrix is of size n^3*n^3) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1945 == Reference ==" current
- 10:5210:52, 15 February 2023 diff hist +463 N 5-point star Cramer's rule (3-Dimensional Poisson Problem Poisson Problem) Created page with "== Time Complexity == $O({5}^{(n^{3})$}) == Space Complexity == $O({5}^{(n^{3})})$ for sure, $O(n^{3})$ possibly??? (if super conservative) words (For expansion by minors, each "level" of expansion requires computing and storing O(1) smaller determinants, and there are O(n^3) levels overall) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1945 == Reference ==" current
- 10:5010:50, 15 February 2023 diff hist −12 Czumaj (Approximate MCOP Matrix Chain Multiplication) No edit summary Tags: Manual revert Reverted
- 10:4210:42, 15 February 2023 diff hist +377 N Chin and Poon (LCS Longest Common Subsequence) Created page with "== Time Complexity == $O(sn + \min\{sp, rm\})$ == Space Complexity == $O(p + n)$ words (https://link.springer.com/content/pdf/10.1007/3-540-58338-6_63.pdf, Fig. 3) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1991 == Reference == https://dl.acm.org/citation.cfm?id=105592"
- 10:4210:42, 15 February 2023 diff hist +374 N Apostolico and Guerra (Algorithm 2) (LCS Longest Common Subsequence) Created page with "== Time Complexity == $O(rm + sn + n \log s)$ == Space Complexity == $O(p + sn)$ words (https://link.springer.com/content/pdf/10.1007/BF01840365.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1987 == Reference == https://link.springer.com/article/10.1007/BF01840365" current
- 10:4210:42, 15 February 2023 diff hist +389 N Hsu and Du (Scheme 1) (LCS Longest Common Subsequence) Created page with "== Time Complexity == $O(rm \log(n/m)$ + rm) == Space Complexity == $O(rm)$ words (https://www.sciencedirect.com/science/article/pii/0022000084900254) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1984 == Reference == https://www.sciencedirect.com/science/article/pii/0022000084900254" current
- 10:4210:42, 15 February 2023 diff hist +357 N Hirschberg (LCS Longest Common Subsequence) Created page with "== Time Complexity == $O(rn + n \log n)$ == Space Complexity == $O(n + p)$ words (https://link.springer.com/content/pdf/10.1007/BF01840365.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1977 == Reference == https://dl.acm.org/citation.cfm?id=322044" current
- 10:4210:42, 15 February 2023 diff hist −7 Rick (LCS Longest Common Subsequence) No edit summary Tag: Reverted
- 10:4210:42, 15 February 2023 diff hist +390 N Rick (LCS Longest Common Subsequence) Created page with "== Time Complexity == $O(sn + \min\{r(n - r )$, rm\}) == Space Complexity == $O(sn + p)$ words (https://link.springer.com/chapter/10.1007%2F3-540-60044-2_53) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1995 == Reference == https://link.springer.com/chapter/10.1007%2F3-540-60044-2_53"
- 10:4210:42, 15 February 2023 diff hist +386 N Kuo and Cross (LCS Longest Common Subsequence) Created page with "== Time Complexity == $O(p + n(r+\log n)$) == Space Complexity == $O(p + n)$ words (https://dl.acm.org/doi/10.1145/74697.74702, Same space complexity as Hunt and Szymanski.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1989 == Reference == https://dl.acm.org/citation.cfm?id=74702" current
- 10:4210:42, 15 February 2023 diff hist +372 N Apostolico and Guerra (HS1 Algorithm) (LCS Longest Common Subsequence) Created page with "== Time Complexity == $O(m \log n +p \log({2}mn/p)$) == Space Complexity == $O(p + n)$ words (https://link.springer.com/article/10.1007/BF01840365) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1987 == Reference == https://link.springer.com/article/10.1007/BF01840365" current
- 10:4210:42, 15 February 2023 diff hist +389 N Hsu and Du (Scheme 2) (LCS Longest Common Subsequence) Created page with "== Time Complexity == $O(rm \log(n/r)$ + rm) == Space Complexity == $O(rm)$ words (https://www.sciencedirect.com/science/article/pii/0022000084900254) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1984 == Reference == https://www.sciencedirect.com/science/article/pii/0022000084900254" current
- 10:4210:42, 15 February 2023 diff hist +397 N Czumaj (Matrix Chain Scheduling Problem Matrix Chain Multiplication) Created page with "== Time Complexity == $O(log^{3} n)$ == Space Complexity == $O(n^{2})$? words (Derived: uses two arrays ($D$ and $c$) both of size $O(n^2)$) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == CREW PRAM == Year == 1993 == Reference == https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.54.9426&rep=rep1&type=pdf" current
- 10:4210:42, 15 February 2023 diff hist +354 N Prakesh Ramanan (Approximate MCOP Matrix Chain Multiplication) Created page with "== Time Complexity == $O(log^{4} n)$ == Space Complexity == $O(n)$? words (Derived: $n$ subtrees and each one has a $O(1)$ size trunk) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == CREW PRAM == Year == 1996 == Reference == https://epubs.siam.org/doi/abs/10.1137/0225039" current
- 10:4210:42, 15 February 2023 diff hist +426 N Heejo Lee; Jong Kim; Sungje Hong; and Sunggu Lee (Approximate MCSP Matrix Chain Multiplication) Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$? words (Derived: two $n \times n$ size tables ($S$ and $W$)) == Description == == Approximate? == Approximate Approximation Factor: "near optimal" == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1997 == Reference == http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.56.222&rep=rep1&type=pdf" current
- 10:4210:42, 15 February 2023 diff hist +496 N Spaghetti Sort Parallel Implementation (Non-Comparison Sorting Sorting) Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary? per processor? words (Assuming getting the spaghetti rods doesn't take up any auxiliary space, the only auxiliary space in this algorithm involves the table and the hands, each using O(1) space) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == ??? == Year == 1984 == Reference == https://link.springer.com/chapter/10.1007..." current
- 10:4210:42, 15 February 2023 diff hist +385 N Odd Even Sort Parallel Implementation (Comparison Sorting Sorting) Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O({1})$ words (in-situ) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1972 == Reference == https://www.semanticscholar.org/paper/Parallel-Neighbor-Sort-(or-the-Glory-of-the-Habermann/bc7b6efb99aae6225239425747fd0169a51f30ce" current
- 10:4210:42, 15 February 2023 diff hist +367 N Probabilistic Convolution Tree (Change-Making Problem Change-Making Problem) Created page with "== Time Complexity == $O(n log n)$ == Space Complexity == $O(n log n)$ words (https://pubmed.ncbi.nlm.nih.gov/24626234/) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2014 == Reference == https://www.ncbi.nlm.nih.gov/pubmed/24626234"
- 10:4210:42, 15 February 2023 diff hist +439 N Srba (SLAM Algorithms SLAM Algorithms) Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$? words? (Seems to store a constant number of O(n)*O(n)-sized matrices and O(n)*O(n)-sized tables (see section II, part C)) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2002 == Reference == http://ingmec.ual.es/~jlblanco/papers/blanco2013rba.pdf"
- 10:4210:42, 15 February 2023 diff hist +424 N FastSlam (SLAM Algorithms SLAM Algorithms) Created page with "== Time Complexity == $O(m*log n)$ per iteration == Space Complexity == $O(mn)$? words? (Stores and updates a balanced binary tree of n elements/dimensions per particle) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2003 == Reference == http://robots.stanford.edu/papers/montemerlo.fastslam-tr.pdf"
- 10:4210:42, 15 February 2023 diff hist +252 N Maximum a Posteriori Occupancy Mapping (Occupancy Grid Mapping Occupancy Grid Mapping) Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2004 == Reference ==" current
- 10:4210:42, 15 February 2023 diff hist +252 N HEALPix mapping Wong (Environment Mapping Texture Mapping) Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2008 == Reference ==" current
- 10:4210:42, 15 February 2023 diff hist +243 N Mauro Steigleder (Environment Mapping Texture Mapping) Created page with "== Time Complexity == - == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2005 == Reference ==" current
- 10:4210:42, 15 February 2023 diff hist +252 N Emil Praun (Environment Mapping Texture Mapping) Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2003 == Reference ==" current
- 10:4210:42, 15 February 2023 diff hist +252 N Heidrich; W.; and H.-P. Seidel (Environment Mapping Texture Mapping) Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 1998 == Reference ==" current