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 Brute force (backtracking search) (The Vertex Cover Problem The Vertex Cover Problem) (hist | edit) [305 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^k n^O({1})$) == Space Complexity == $O(k)$ auxiliary words (Just need to keep track of current subset being checked) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 10:53, 15 February 2023 C-LOOK (Disk Scheduling Disk Scheduling) (hist | edit) [256 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*log n)$ == Space Complexity == $O(n)$ auxiliary words (See LOOK) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1979 == Reference == -")
- 10:53, 15 February 2023 LOOK (Disk Scheduling Disk Scheduling) (hist | edit) [314 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*log n)$ == Space Complexity == $O(n)$ auxiliary words (Needs sorted array of requests and seek distance but not much else) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1979 == Reference == -")
- 10:53, 15 February 2023 C-SCAN (Disk Scheduling Disk Scheduling) (hist | edit) [256 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*log n)$ == Space Complexity == $O(n)$ auxiliary words (See SCAN) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1979 == Reference == -")
- 10:53, 15 February 2023 SCAN (Disk Scheduling Disk Scheduling) (hist | edit) [327 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*log n)$ == Space Complexity == $O(n)$ auxiliary words (https://www.geeksforgeeks.org/scan-elevator-disk-scheduling-algorithms/?ref=lbp) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1979 == Reference == -")
- 10:53, 15 February 2023 SSTF (Disk Scheduling Disk Scheduling) (hist | edit) [346 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*log n)$ with binary tree == Space Complexity == $O(n)$ auxiliary words (https://www.geeksforgeeks.org/program-for-sstf-disk-scheduling-algorithm/?ref=lbp) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1979 == Reference == -")
- 10:53, 15 February 2023 FCFS (Disk Scheduling Disk Scheduling) (hist | edit) [335 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary words (Needs to keep track of seek distance but FCFS is fairly straightforward/no extra info needed) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1979 == Reference == -")
- 10:53, 15 February 2023 Catriel Beeri Ronald Fagin John H. Howard (Multivalued Dependency Inference Problem Dependency Inference Problem) (hist | edit) [269 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({4}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1977 == Reference == https://dl.acm.org/doi/10.1145/509404.509414")
- 10:53, 15 February 2023 Räihä; Manilla (Multivalued Dependency Inference Problem Dependency Inference Problem) (hist | edit) [428 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 == 1992 == Reference == https://www.sciencedirect.com/science/article/pii/0166218X92900315")
- 10:53, 15 February 2023 Trino ( 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 == 2004 == Reference ==")
- 10:53, 15 February 2023 Naive ( 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 == 1956 == Reference ==")
- 10:53, 15 February 2023 Derek's + Maxwell ( 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 == 2001 == Reference ==")
- 10:53, 15 February 2023 Maxwell ( 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 == 2000 == Reference ==")
- 10:53, 15 February 2023 Russell et. al. ( 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 == 1989 == Reference ==")
- 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 ==")