New pages
Jump to navigation
Jump to search
(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)
- 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")
- 10:42, 15 February 2023 Srba (SLAM Algorithms SLAM Algorithms) (hist | edit) [448 bytes] Admin (talk | contribs) (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:42, 15 February 2023 FastSlam (SLAM Algorithms SLAM Algorithms) (hist | edit) [434 bytes] Admin (talk | contribs) (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:42, 15 February 2023 Maximum a Posteriori Occupancy Mapping (Occupancy Grid Mapping Occupancy Grid Mapping) (hist | edit) [252 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2004 == Reference ==")
- 10:42, 15 February 2023 HEALPix mapping Wong (Environment Mapping Texture Mapping) (hist | edit) [252 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2008 == Reference ==")
- 10:42, 15 February 2023 Mauro Steigleder (Environment Mapping Texture Mapping) (hist | edit) [243 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == - == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2005 == Reference ==")
- 10:42, 15 February 2023 Emil Praun (Environment Mapping Texture Mapping) (hist | edit) [252 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2003 == Reference ==")
- 10:42, 15 February 2023 Heidrich; W.; and H.-P. Seidel (Environment Mapping Texture Mapping) (hist | edit) [252 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 1998 == Reference ==")
- 10:42, 15 February 2023 Sphere mapping (Environment Mapping Texture Mapping) (hist | edit) [243 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == - == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 1984 == Reference ==")
- 10:42, 15 February 2023 Nate Green (Environment Mapping Texture Mapping) (hist | edit) [252 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{4})$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 1986 == Reference ==")
- 10:42, 15 February 2023 Blinn and Newell (Environment Mapping Texture Mapping) (hist | edit) [243 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == - == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 1976 == Reference ==")
- 10:42, 15 February 2023 Bresenham Algorithm (Rasterization Rasterization) (hist | edit) [460 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ Words (Derived: for each iteration (i.e. each step along the line), only need to store a constant number of variables that are then overwritten in the next iteration.) == Description == == Approximate? == Approximate Approximation Factor: n/a == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1962 == Reference == Hearn, Baker (1997) pg. 88")
- 10:42, 15 February 2023 Digital Differential Analyzer (DDA) (Rasterization Rasterization) (hist | edit) [492 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ Words (Derived: for each iteration (i.e. each step along the line), only need to store a constant number of variables that are then overwritten in the next iteration.) == Description == "Scan-conversion line algorithm" == Approximate? == Approximate Approximation Factor: n/a == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1983 == Reference == Hearn, Ba...")
- 10:42, 15 February 2023 Shani; Brafman; & Shimony; 2005 (POMDPs POMDPs) (hist | edit) [242 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2005 == Reference ==")
- 10:42, 15 February 2023 Bertsekas & Castanon; 1999; (POMDPs POMDPs) (hist | edit) [242 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 1999 == Reference ==")
- 10:42, 15 February 2023 McAllester & Singh; 1999; (POMDPs POMDPs) (hist | edit) [242 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 1999 == Reference ==")
- 10:42, 15 February 2023 Paquet; Tobin; & Chaib-draa; 2005; (POMDPs POMDPs) (hist | edit) [242 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2005 == Reference ==")
- 10:42, 15 February 2023 Barto;Bradtke; & Singhe; 1995; (POMDPs POMDPs) (hist | edit) [242 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 1995 == Reference ==")
- 10:42, 15 February 2023 Washington; 1997; (POMDPs POMDPs) (hist | edit) [242 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 1997 == Reference ==")
- 10:42, 15 February 2023 Satia & Lave; 1973; (POMDPs POMDPs) (hist | edit) [242 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 1973 == Reference ==")
- 10:42, 15 February 2023 Spaan & Vlassis; 2005 (POMDPs POMDPs) (hist | edit) [242 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2005 == Reference ==")
- 10:42, 15 February 2023 Smith & Simmons; 2005; (POMDPs POMDPs) (hist | edit) [242 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2005 == Reference ==")
- 10:41, 15 February 2023 Poupart; 2005; (POMDPs POMDPs) (hist | edit) [242 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2005 == Reference ==")
- 10:41, 15 February 2023 Braziunas & Boutilier; 2004; (POMDPs POMDPs) (hist | edit) [242 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2004 == Reference ==")
- 10:41, 15 February 2023 Pineau; Gordon; & Thrun; 2003; (POMDPs POMDPs) (hist | edit) [242 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2003 == Reference ==")