New pages
Jump to navigation
Jump to search
(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)
- 10:53, 15 February 2023 Liu (Decisional BCNF BCNF Decomposition) (hist | edit) [327 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(kn^{2})$ == Space Complexity == $O(n)$ words (Derived: Creates an auxiliary database) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1992 == Reference == https://doi.org/10.1016/0950-5849(92)90028-N")
- 10:53, 15 February 2023 Derek's Algorithm ( 4NF Decomposition) (hist | edit) [222 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1983 == Reference ==")
- 10:53, 15 February 2023 Xu; Renio ( 4NF Decomposition) (hist | edit) [222 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1972 == Reference ==")
- 10:53, 15 February 2023 Tradu; Mirc ( 4NF Decomposition) (hist | edit) [222 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1967 == Reference ==")
- 10:53, 15 February 2023 Schlimmer (Functional Dependency Inference Problem Dependency Inference Problem) (hist | edit) [368 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n {2}^n p)$ == Space Complexity == $O({2}^n)$ words ((original source, but without user-supplied bound) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1993 == Reference == https://www.aaai.org/Papers/Workshops/1993/WS-93-02/WS93-02-017.pdf")
- 10:53, 15 February 2023 Brute force algorithm (Functional Dependency Inference Problem Dependency Inference Problem) (hist | edit) [429 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} {2}^n p log p)$ == Space Complexity == $O(n2^n)$? words (bound on size of output (2^n domains, O(n) possible attributes per domain); can probably be improved) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1967 == Reference == https://www.sciencedirect.com/science/article/pii/0166218X92900315")
- 10:52, 15 February 2023 Naive algorithm (Subset Sum The Subset-Sum Problem) (hist | edit) [289 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n * n)$ == Space Complexity == $O(n)$ auxiliary words (https://dl.acm.org/doi/10.1145/321812.321823) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 10:52, 15 February 2023 Random Split Exponential algorithm (Subset Sum The Subset-Sum Problem) (hist | edit) [309 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^{(n/{2})} * n)$ == Space Complexity == $O({2}^{(n/{2})})$ words (https://dl.acm.org/doi/10.1145/321812.321823) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 10:52, 15 February 2023 Hybrid Algorithm (De Novo Genome Assembly De Novo Genome Assembly) (hist | edit) [235 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1999 == Reference ==")
- 10:52, 15 February 2023 De Bruijn Graph (Idury, Waterman) (De Novo Genome Assembly De Novo Genome Assembly) (hist | edit) [383 bytes] Admin (talk | contribs) (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")
- 10:52, 15 February 2023 String Graph (Myers) (De Novo Genome Assembly De Novo Genome Assembly) (hist | edit) [386 bytes] Admin (talk | contribs) (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:52, 15 February 2023 String Graph with Ferragina–Manzini Index (Simpson, Durbin) (De Novo Genome Assembly De Novo Genome Assembly) (hist | edit) [403 bytes] Admin (talk | contribs) (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")
- 10:52, 15 February 2023 Katajainen and M. Koppinen ( Delaunay Triangulation) (hist | edit) [343 bytes] Admin (talk | contribs) (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:52, 15 February 2023 Dwyer (higher dimensions) (General Delaunay Triangulation (d-dimensions) Delaunay Triangulation) (hist | edit) [376 bytes] Admin (talk | contribs) (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:52, 15 February 2023 Drysdale; Su (2-Dimensional Delaunay Triangulation Delaunay Triangulation) (hist | edit) [374 bytes] Admin (talk | contribs) (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")
- 10:52, 15 February 2023 Fortune (2-Dimensional Delaunay Triangulation Delaunay Triangulation) (hist | edit) [342 bytes] Admin (talk | contribs) (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")
- 10:52, 15 February 2023 Dwyer (2-Dimensional Delaunay Triangulation Delaunay Triangulation) (hist | edit) [413 bytes] Admin (talk | contribs) (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:52, 15 February 2023 S-hull (Sinclair) (2-Dimensional Delaunay Triangulation Delaunay Triangulation) (hist | edit) [410 bytes] Admin (talk | contribs) (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:52, 15 February 2023 Guibas; Stofli (2-Dimensional Delaunay Triangulation Delaunay Triangulation) (hist | edit) [410 bytes] Admin (talk | contribs) (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:52, 15 February 2023 Bowyer–Watson algorithm (2-Dimensional Delaunay Triangulation Delaunay Triangulation) (hist | edit) [427 bytes] Admin (talk | contribs) (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:52, 15 February 2023 Belloch (2-Dimensional Delaunay Triangulation Delaunay Triangulation) (hist | edit) [502 bytes] Admin (talk | contribs) (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:52, 15 February 2023 De Berg; Cheong (2-Dimensional Delaunay Triangulation Delaunay Triangulation) (hist | edit) [430 bytes] Admin (talk | contribs) (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:52, 15 February 2023 Flipping algorithm (2-Dimensional Delaunay Triangulation Delaunay Triangulation) (hist | edit) [341 bytes] Admin (talk | contribs) (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")
- 10:52, 15 February 2023 Naive algorithm (2-Dimensional Delaunay Triangulation Delaunay Triangulation) (hist | edit) [346 bytes] Admin (talk | contribs) (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 == -")
- 10:52, 15 February 2023 9-point FFT (3-Dimensional Poisson Problem Poisson Problem) (hist | edit) [317 bytes] Admin (talk | contribs) (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:52, 15 February 2023 5-point cyclic reduction (3-Dimensional Poisson Problem Poisson Problem) (hist | edit) [340 bytes] Admin (talk | contribs) (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:52, 15 February 2023 9-point ADI iteration + smooth guess (3-Dimensional Poisson Problem Poisson Problem) (hist | edit) [340 bytes] Admin (talk | contribs) (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:52, 15 February 2023 5-point FFT (3-Dimensional Poisson Problem Poisson Problem) (hist | edit) [317 bytes] Admin (talk | contribs) (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:52, 15 February 2023 9-point ADI iteration (3-Dimensional Poisson Problem Poisson Problem) (hist | edit) [340 bytes] Admin (talk | contribs) (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:52, 15 February 2023 9-point Tensor product (3-Dimensional Poisson Problem Poisson Problem) (hist | edit) [382 bytes] Admin (talk | contribs) (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")
- 10:52, 15 February 2023 5-point SOR iteration (3-Dimensional Poisson Problem Poisson Problem) (hist | edit) [329 bytes] Admin (talk | contribs) (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:52, 15 February 2023 9-point SOR iteration (3-Dimensional Poisson Problem Poisson Problem) (hist | edit) [322 bytes] Admin (talk | contribs) (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 ==")
- 10:52, 15 February 2023 5-point ADI iteration (3-Dimensional Poisson Problem Poisson Problem) (hist | edit) [344 bytes] Admin (talk | contribs) (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:52, 15 February 2023 5-point Gauss Seidel iteration (3-Dimensional Poisson Problem Poisson Problem) (hist | edit) [340 bytes] Admin (talk | contribs) (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:52, 15 February 2023 5-point Gauss elimination (3-Dimensional Poisson Problem Poisson Problem) (hist | edit) [305 bytes] Admin (talk | contribs) (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 ==")
- 10:52, 15 February 2023 5-point star Cramer's rule (3-Dimensional Poisson Problem Poisson Problem) (hist | edit) [463 bytes] Admin (talk | contribs) (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 ==")
- 10:42, 15 February 2023 Chin and Poon (LCS Longest Common Subsequence) (hist | edit) [384 bytes] Admin (talk | contribs) (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:42, 15 February 2023 Apostolico and Guerra (Algorithm 2) (LCS Longest Common Subsequence) (hist | edit) [374 bytes] Admin (talk | contribs) (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")
- 10:42, 15 February 2023 Hsu and Du (Scheme 1) (LCS Longest Common Subsequence) (hist | edit) [389 bytes] Admin (talk | contribs) (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")
- 10:42, 15 February 2023 Hirschberg (LCS Longest Common Subsequence) (hist | edit) [357 bytes] Admin (talk | contribs) (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")
- 10:42, 15 February 2023 Rick (LCS Longest Common Subsequence) (hist | edit) [379 bytes] Admin (talk | contribs) (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:42, 15 February 2023 Kuo and Cross (LCS Longest Common Subsequence) (hist | edit) [386 bytes] Admin (talk | contribs) (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")
- 10:42, 15 February 2023 Apostolico and Guerra (HS1 Algorithm) (LCS Longest Common Subsequence) (hist | edit) [372 bytes] Admin (talk | contribs) (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")
- 10:42, 15 February 2023 Hsu and Du (Scheme 2) (LCS Longest Common Subsequence) (hist | edit) [389 bytes] Admin (talk | contribs) (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")
- 10:42, 15 February 2023 Czumaj (Matrix Chain Scheduling Problem Matrix Chain Multiplication) (hist | edit) [397 bytes] Admin (talk | contribs) (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")
- 10:42, 15 February 2023 Prakesh Ramanan (Approximate MCOP Matrix Chain Multiplication) (hist | edit) [354 bytes] Admin (talk | contribs) (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")
- 10:42, 15 February 2023 Heejo Lee; Jong Kim; Sungje Hong; and Sunggu Lee (Approximate MCSP Matrix Chain Multiplication) (hist | edit) [426 bytes] Admin (talk | contribs) (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")
- 10:42, 15 February 2023 Spaghetti Sort Parallel Implementation (Non-Comparison Sorting Sorting) (hist | edit) [496 bytes] Admin (talk | contribs) (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...")
- 10:42, 15 February 2023 Odd Even Sort Parallel Implementation (Comparison Sorting Sorting) (hist | edit) [385 bytes] Admin (talk | contribs) (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")
- 10:42, 15 February 2023 Probabilistic Convolution Tree (Change-Making Problem Change-Making Problem) (hist | edit) [368 bytes] Admin (talk | contribs) (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")