New pages

(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)

• 11:16, 15 February 2023 ‎Gaussian Elimination (Exact Laplacian Solver SDD Systems Solvers) (hist | edit) ‎[373 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$ words (Derived: Storing the inverse of the Laplacian) == Description == Use Gaussian elimination to compute the inverse of the Laplacian to solve for x == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == -150 == Reference == -")
• 11:15, 15 February 2023 ‎9-point FFT (2-Dimensional Poisson Problem Poisson Problem) (hist | edit) ‎[317 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} logn)$ == Space Complexity == $O(n^{2})$? 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 ==")
• 11:15, 15 February 2023 ‎5-point cyclic reduction (2-Dimensional Poisson Problem Poisson Problem) (hist | edit) ‎[340 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} logn)$ == Space Complexity == $O(n^{2})$? words (Generally uses a constant number of n^2*n^2 matrices where O(n^2) entries are nonempty) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1970 == Reference ==")
• 11:15, 15 February 2023 ‎9-point ADI iteration + smooth guess (2-Dimensional Poisson Problem Poisson Problem) (hist | edit) ‎[340 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} logn)$ == Space Complexity == $O(n^{2})$? words (Generally uses a constant number of n^2*n^2 matrices where O(n^2) entries are nonempty) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1969 == Reference ==")
• 11:15, 15 February 2023 ‎5-point FFT (2-Dimensional Poisson Problem Poisson Problem) (hist | edit) ‎[317 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} logn)$ == Space Complexity == $O(n^{2})$? 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 ==")
• 11:15, 15 February 2023 ‎9-point ADI iteration (2-Dimensional Poisson Problem Poisson Problem) (hist | edit) ‎[340 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} logn)$ == Space Complexity == $O(n^{2})$? words (Generally uses a constant number of n^2*n^2 matrices where O(n^2) entries are nonempty) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1965 == Reference ==")
• 11:15, 15 February 2023 ‎9-point Tensor product (2-Dimensional Poisson Problem Poisson Problem) (hist | edit) ‎[382 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$? words (Generally uses a constant number of n^2*n^2 matrices where O(n^2) 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")
• 11:15, 15 February 2023 ‎9-point SOR iteration (2-Dimensional Poisson Problem Poisson Problem) (hist | edit) ‎[322 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$? words (Need one auxiliary O(n^2)-sized vector to store guess, and the scalar sigma) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1956 == Reference ==")
• 11:15, 15 February 2023 ‎5-point ADI iteration (2-Dimensional Poisson Problem Poisson Problem) (hist | edit) ‎[344 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} log^{2}n)$ == Space Complexity == $O(n^{2})$? words (Generally uses a constant number of n^2*n^2 matrices where O(n^2) entries are nonempty) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1955 == Reference ==")
• 11:15, 15 February 2023 ‎5-point SOR iteration (2-Dimensional Poisson Problem Poisson Problem) (hist | edit) ‎[329 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3} logn)$ == Space Complexity == $O(n^{2})$? words (Need one auxiliary O(n^2)-sized vector to store guess, and the scalar sigma) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1954 == Reference ==")
• 11:15, 15 February 2023 ‎5-point Gauss Seidel iteration (2-Dimensional Poisson Problem Poisson Problem) (hist | edit) ‎[340 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{4} logn)$ == Space Complexity == $O(n^{2})$? words (Generally uses a constant number of n^2*n^2 matrices where O(n^2) entries are nonempty) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1945 == Reference ==")
• 11:15, 15 February 2023 ‎5-point Gauss elimination (2-Dimensional Poisson Problem Poisson Problem) (hist | edit) ‎[305 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{4})$ == Space Complexity == $O(n^{4})$ words (See Gauss-Jordan elimination, but matrix is of size n^2*n^2) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1945 == Reference ==")
• 11:15, 15 February 2023 ‎5-point star Cramer's rule (2-Dimensional Poisson Problem Poisson Problem) (hist | edit) ‎[463 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O({4}^{(n^{2})})$ == Space Complexity == $O({4}^{(n^{2})})$ for sure, $O(n^{2})$ 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^2) levels overall) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1945 == Reference ==")
• 11:15, 15 February 2023 ‎TSPLIB (Minimum TSP The Traveling-Salesman Problem) (hist | edit) ‎[304 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^V logE)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1991 == Reference == https://pubsonline.informs.org/doi/abs/10.1287/ijoc.3.4.376")
• 11:15, 15 February 2023 ‎Lawler; E. L. (Minimum TSP The Traveling-Salesman Problem) (hist | edit) ‎[306 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O({1.674}^V E^{2})$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1985 == Reference == https://onlinelibrary.wiley.com/doi/10.1002/net.3230180309")
• 11:15, 15 February 2023 ‎Christofides algorithm (Approximate TSP The Traveling-Salesman Problem) (hist | edit) ‎[458 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{3})$ == Space Complexity == $O(V^{2})$??? words (Depends on best space complexity for O(V^3) min-weight matching (the rest of the algorithm requires O(V) auxiliary space)) == Description == == Approximate? == Approximate Approximation Factor: 1.5 == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == https://apps.dtic.mil/dtic/tr/fulltext/u2/a025602.pdf")
• 11:15, 15 February 2023 ‎Held–Karp algorithm (Minimum TSP The Traveling-Salesman Problem) (hist | edit) ‎[368 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{2} {2}^V)$ == Space Complexity == $O(V*{2}^V)$ words (Need to store all C(S, l) for all subsets $S \subseteq V$ and all vertices l) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1962 == Reference == https://www.jstor.org/stable/2098806")
• 11:15, 15 February 2023 ‎Kazuhisa Makino, Takeaki Uno; Section 5 (Enumerating Maximal Cliques, arbitrary graph Clique Problems) (hist | edit) ‎[441 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{\omega})$ per clique where omega is the exponent on matrix multiplication == Space Complexity == $O(n^{2})$ auxiliary words (https://link.springer.com/chapter/10.1007/978-3-540-27810-8_23) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2004 == Reference == https://link.springer.com/chapter/10.1007/978-3-540-27810-8_23")
• 11:15, 15 February 2023 ‎Shuji Tsukiyama, Mikio Ide, Hiromu Ariyoshi, and Isao Shirakawa (Enumerating Maximal Cliques, arbitrary graph Clique Problems) (hist | edit) ‎[473 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(nm)$ per clique == Space Complexity == $O(m)$ auxiliary words (See original reference, but also note that we'd have to construct and store the complementary graph (as this is originally an algo for MISs)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1977 == Reference == https://www.proquest.com/docview/918487776?pq-origsite=gscholar&fromopenv...")
• 11:15, 15 February 2023 ‎M. Chrobak and D. Eppstein (Enumerating Maximal Cliques, arbitrary graph Clique Problems) (hist | edit) ‎[432 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n d^{2} {2}^d)$ == Space Complexity == $O(n)$ auxiliary? words (Keeps track of degeneracy ordering along with vertex and subset being tested (here the subset size is bounded by O(d)=O(n))) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1989 == Reference == https://www.ics.uci.edu/~eppstein/pubs/ChrEpp-TCS-91.pdf")
• 11:15, 15 February 2023 ‎Chiba and Nishizeki (Enumerating Maximal Cliques, arbitrary graph Clique Problems) (hist | edit) ‎[412 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(a(G)*m)$ per clique == Space Complexity == $O(m)$ auxiliary words (https://pdfs.semanticscholar.org/0d19/245a27bc65a87a8014d5b8a66fb514c8ff0b.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1985 == Reference == https://pdfs.semanticscholar.org/0d19/245a27bc65a87a8014d5b8a66fb514c8ff0b.pdf")
• 11:15, 15 February 2023 ‎David Eppstein, Maarten Löffler, Darren Strash (Enumerating Maximal Cliques, arbitrary graph Clique Problems) (hist | edit) ‎[368 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(dn {3}^{(d/{3})})$ == Space Complexity == $O(n^{2})$ auxiliary? words (See Bron-Kerbosch, but also keeps track of O(n)-sized degeneracy ordering) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2010 == Reference == https://arxiv.org/pdf/1006.5440.pdf")
• 11:15, 15 February 2023 ‎Segundo; Artieda; Strash Parallel (Enumerating Maximal Cliques, arbitrary graph Clique Problems) (hist | edit) ‎[473 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O({3}^{(n/{3})})$ total work? (previously this cell said $O(n^{4})$) == Space Complexity == $O(n^{2})$ auxiliary?? words (Keep track of an O(n)-sized recursive stack with O(n)-sized lists as elements? (this algo builds off of Bron-Kerbosch)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2011 == Reference == https://arxiv.org/pdf/1801.00202.pdf")
• 11:15, 15 February 2023 ‎Tomita; Tanaka & Takahashi (Enumerating Maximal Cliques, arbitrary graph Clique Problems) (hist | edit) ‎[374 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O({3}^{(n/{3})$}) == Space Complexity == $O(n^{2})$ auxiliary? words (See Bron-Kerbosch (seems like a similar approach?)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference == https://snap.stanford.edu/class/cs224w-readings/tomita06cliques.pdf")
• 11:15, 15 February 2023 ‎Akkoyunlu; E. A. (Enumerating Maximal Cliques, arbitrary graph Clique Problems) (hist | edit) ‎[390 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O({3}^{(n/{3})$}) == Space Complexity == $O(n^{2})$ auxiliary?? words (See Bron-Kerbosch (seems like a similar approach?)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1973 == Reference == http://www.dcs.gla.ac.uk/~pat/jchoco/clique/enumeration/papers/SMJ000001%5B1%5D.pdf")
• 11:15, 15 February 2023 ‎Bron–Kerbosch algorithm (Enumerating Maximal Cliques, arbitrary graph Clique Problems) (hist | edit) ‎[379 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O({3}^{(n/{3})})$ == Space Complexity == $O(n^{2})$ auxiliary? words (Keep track of an O(n)-sized recursive stack with O(n)-sized lists as elements?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1973 == Reference == https://dl.acm.org/doi/10.1145/362342.362367")
• 11:15, 15 February 2023 ‎Finch (Inexact GED Graph Edit Distance Computation) (hist | edit) ‎[531 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{2} E)$ == Space Complexity == $O(V^{2})$? words (Seems to store/update a constant number of values per pair of nodes (one from each graph)) == Description == energy-based == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1998 == Reference == https://direct.mit.edu/neco/article-pdf/10/7/1873/813998/089976698300017188.pdf?casa_token=nCYv9xO_Cc4AAAAA:EHiG4v8QmQju6u9...")
• 11:15, 15 February 2023 ‎Tao D; Tang X; Li X et al ( Graph Edit Distance Computation) (hist | edit) ‎[281 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{2})$ == Space Complexity == () == Description == EDH == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2006 == Reference == https://eprints.bbk.ac.uk/id/eprint/443/1/Binder1.pdf")
• 11:15, 15 February 2023 ‎Wang Y-K; Fan K-C; Horng J-T ( Graph Edit Distance Computation) (hist | edit) ‎[288 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(V E^{2} loglogE)$ == Space Complexity == () == Description == Genetics-based == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1997 == Reference == https://doi.org/10.1109/3477.604100")
• 11:15, 15 February 2023 ‎Neuhaus, Riesen, Bunke (Inexact GED Graph Edit Distance Computation) (hist | edit) ‎[363 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{2})$ == Space Complexity == $O(wV)$ words (Derived: number of nodes under consideration at once) == Description == A*-Beamsearch == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference == https://link.springer.com/chapter/10.1007/11815921_17")
• 11:15, 15 February 2023 ‎Alberto Sanfeliu and King-Sun Fu ( Graph Edit Distance Computation) (hist | edit) ‎[272 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{3} E^{2})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1983 == Reference == https://doi.org/10.1109/TSMC.1983.6313167")
• 11:15, 15 February 2023 ‎K Riesen (Inexact GED Graph Edit Distance Computation) (hist | edit) ‎[337 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{2})$ == Space Complexity == $O(V)$ words (Space complexity of A*) == Description == A* with bipartite heuristic == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2013 == Reference == https://doi.org/10.1007/978-3-642-38221-5_15")
• 11:15, 15 February 2023 ‎L Chang (Inexact GED Graph Edit Distance Computation) (hist | edit) ‎[400 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(V E^{2} logV)$ == Space Complexity == $O(V)$ words (Theorem 5.1, and the bound on T_{\leq \delta ...} is V\log V https://doi.org/10.48550/arXiv.1709.06810) == Description == AStar+ == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2017 == Reference == https://doi.org/10.48550/arXiv.1709.06810")
• 11:15, 15 February 2023 ‎Y Bai (Inexact GED Graph Edit Distance Computation) (hist | edit) ‎[417 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{2})$ == Space Complexity == $O(V^{2})$ words (Derived: Auxiliary matrices for the neural network of size VxV) == Description == SimGNN == Approximate? == Approximate Approximation Factor: none stated == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2018 == Reference == https://asset-pdf.scinapse.io/prod/2886034153/2886034153.pdf")
• 11:15, 15 February 2023 ‎X Chen (Exact GED Graph Edit Distance Computation) (hist | edit) ‎[362 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(VS)$ == Space Complexity == $O(wV^{2})$ words (Theorem 5, https://doi.org/10.1016/j.knosys.2018.10.002) == Description == Beam Stack Search == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2019 == Reference == https://doi.org/10.1016/j.knosys.2018.10.002")
• 11:15, 15 February 2023 ‎Stephen Alstrup, Cyril Gavoille, Haim Kaplan & Theis Rauhe (Lowest Common Ancestor with Static Trees Lowest Common Ancestor) (hist | edit) ‎[362 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n+m)$ == Space Complexity == $O(n)$ words ((see original reference, noting that a word is O(log n) bits)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2004 == Reference == https://link.springer.com/article/10.1007/s00224-004-1155-5")
• 11:15, 15 February 2023 ‎Berkman; Vishkin (Lowest Common Ancestor with Static Trees Lowest Common Ancestor) (hist | edit) ‎[333 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n+m)$ ? == Space Complexity == $O(n)$ words (space bounded by pre-processing time) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1993 == Reference == https://apps.dtic.mil/dtic/tr/fulltext/u2/a227803.pdf")
• 11:15, 15 February 2023 ‎Schieber; Vishkin (Lowest Common Ancestor with Static Trees Lowest Common Ancestor) (hist | edit) ‎[372 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n+m)$ == Space Complexity == $O(n)$ words (https://www.proquest.com/docview/919780720?pq-origsite=gscholar&fromopenview=true) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1988 == Reference == https://epubs.siam.org/doi/abs/10.1137/0217079?journalCode=smjcat")
• 11:15, 15 February 2023 ‎Tarjan's off-line lowest common ancestors algorithm (Off-Line Lowest Common Ancestor Lowest Common Ancestor) (hist | edit) ‎[510 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n+m)$ == Space Complexity == $O(n)$ words (https://www.cs.bgu.ac.il/~segal/PAPERS2/tarj.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1984 == Reference == https://www.semanticscholar.org/paper/Fast-Algorithms-for-Finding-Nearest-Common-Harel-Tarjan/8867d059dda279b1aed4a0301e4e46f9daf65174")
• 11:15, 15 February 2023 ‎Revuz's algorithm (Acyclic DFA Minimization DFA Minimization) (hist | edit) ‎[381 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ words (https://www.labri.fr/perso/zeitoun/research/pdf/Almeida-Zeitoun-IPL2008.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1992 == Reference == https://www.sciencedirect.com/science/article/pii/0304397592901423")
• 11:15, 15 February 2023 ‎Almeida & Zeitoun (Cyclic Nontrivial SCCs DFA Minimization DFA Minimization) (hist | edit) ‎[390 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ words (https://www.labri.fr/perso/zeitoun/research/pdf/Almeida-Zeitoun-IPL2008.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2008 == Reference == https://www.labri.fr/perso/zeitoun/research/pdf/Almeida-Zeitoun-IPL2008.pdf")
• 11:15, 15 February 2023 ‎Brzozowski's algorithm (DFA Minimization DFA Minimization) (hist | edit) ‎[526 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O({2}^n)$ words (http://www.cs.ru.nl/bachelors-theses/2017/Erin_van_der_Veen___4431200___The_Practical_Performance_of_Automata_Minimization_Algorithms.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1963 == Reference == https://www.semanticscholar.org/paper/Canonical-regular-expressions-and-minimal-state-for-...")
• 11:15, 15 February 2023 ‎Moore's algorithm (DFA Minimization DFA Minimization) (hist | edit) ‎[371 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} k)$ == Space Complexity == $O(n)$ words (Derived: Auxiliary data structure that keeps track of a 'block' binary variable for each state) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1956 == Reference == https://doi.org/10.2307/2964500")
• 11:15, 15 February 2023 ‎Hopcroft's algorithm (DFA Minimization DFA Minimization) (hist | edit) ‎[374 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(kn \log n)$ == Space Complexity == $O(kn)$ words (https://link.springer.com/content/pdf/10.1007/3-540-54430-5_107.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1971 == Reference == https://www.cs.cmu.edu/~./sutner/CDM/papers/Hopcroft71.pdf")
• 11:15, 15 February 2023 ‎Dekel; Nassimi & Sahni Parallel Implementation (Topological Sorting Topological Sorting) (hist | edit) ‎[652 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O( log² V)$ == Space Complexity == $O(V^{2})$?? words (Their n*n*n cube setup seems to only require each processor to keep track of one entry A(i, j), B(i, j) and propagates the results across the structure, only requiring O(1) auxiliary space per processor. Comparison sorting can be done easily with O(1) auxiliary space per processor.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Comp...")
• 11:15, 15 February 2023 ‎Tarjan's DFS based algorithm (Topological Sorting Topological Sorting) (hist | edit) ‎[353 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(V+E)$ == Space Complexity == $O(V)$ auxiliary? words (maintain O(V)-sized recursion stack, along with O(V) marks) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == https://link.springer.com/article/10.1007/BF00268499")
• 11:15, 15 February 2023 ‎Kahn's algorithm (Topological Sorting Topological Sorting) (hist | edit) ‎[332 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(V+E)$ == Space Complexity == $O(V)$ auxiliary words (maintain stack of nodes with no incoming edges) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1962 == Reference == https://dl.acm.org/doi/10.1145/368996.369025")
• 11:15, 15 February 2023 ‎Chan's algorithm Parallel Implementation ( Variance Calculations) (hist | edit) ‎[402 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(log n)$ == Space Complexity == $O({1})$ per processor words (Each processor maintains O(1) information related to count, mean, M2) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == EREW(??) PRAM == Year == 1979 == Reference == http://i.stanford.edu/pub/cstr/reports/cs/tr/79/773/CS-TR-79-773.pdf")
• 11:15, 15 February 2023 ‎Welford's Online algorithm ( Variance Calculations) (hist | edit) ‎[420 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary words (Maintains O(1) information (count, mean, M2) that is constantly updated as values are read) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1962 == Reference == http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.302.7503&rep=rep1&type=pdf")
• 11:15, 15 February 2023 ‎Weighted incremental algorithm ( Variance Calculations) (hist | edit) ‎[460 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary words (Maintains O(1) information (sum of weights, sum of squared weights, weighted sum of values, weighted sum of values squared) that is constantly updated as values are read) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1979 == Reference == https://dl.acm.org/doi/10.1145/359146.359153")

(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)