New pages
Jump to navigation
Jump to search
(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)
- 11:15, 15 February 2023 Faugère F5 algorithm (Gröbner Bases Gröbner Bases) (hist | edit) [482 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(C(n+D_reg, D_reg)$^{\omega}) where omega is the exponent on matrix multiplication == Space Complexity == $O(C(n+D_{reg}, D_{reg})$^{2})? words (Seems to keep track of a square matrix (for monomials) of size $O(C(n+D_{reg}, D_{reg})^2$)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2002 == Reference == https://dl.acm.org/doi/10.1145/780506.780516")
- 11:15, 15 February 2023 Faugère F4 algorithm (Gröbner Bases Gröbner Bases) (hist | edit) [500 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(C(n+D_reg, D_reg)$^{\omega}) where omega is the exponent on matrix multiplication == Space Complexity == $O(C(n+D_{reg}, D_{reg})$^{2})? words (Seems to keep track of a square matrix (for monomials) of size $O(C(n+D_{reg}, D_{reg})^2$)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1999 == Reference == https://linkinghub.elsevier.com/retrieve/...")
- 11:15, 15 February 2023 Buchberger's algorithm (Gröbner Bases Gröbner Bases) (hist | edit) [401 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == d^{({2}^{(n+o({1})})}) == Space Complexity == d^{({2}^{(n+o({1}))})}?? words (Output may contain that many elements. However, this bound seems very crude/loose) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == https://dl.acm.org/doi/10.1145/1088216.1088219")
- 11:15, 15 February 2023 Dual subgradients and the drift-plus-penalty method (Stochastic optimization Convex Optimization (Non-linear)) (hist | edit) [324 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(Vmn)$???? words (involves minimizing an expression with up to O(Vmn) terms per iteration?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1993 == Reference ==")
- 11:15, 15 February 2023 Subgradient method (General, Constrained optimization Convex Optimization (Non-linear)) (hist | edit) [376 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} )$ == Space Complexity == $O(n+L)$? words (keep track of current guess x^{(k)}, and needs to compute subgradient g^{(k)}) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1981 == Reference == https://www.springer.com/gp/book/9783642821202")
- 11:15, 15 February 2023 Ellipsoid method (General, Constrained optimization Convex Optimization (Non-linear)) (hist | edit) [383 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} logn)$ == Space Complexity == $O(nmL)$ words (see orginal paper (noting that O(alpha*log(H*alpha)) = O(L))) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1971 == Reference == https://www.sciencedirect.com/science/article/abs/pii/0041555380900610")
- 11:15, 15 February 2023 Wolfe; Lemaréchal; Kiwiel (General, Constrained optimization Convex Optimization (Non-linear)) (hist | edit) [413 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{4})$ == Space Complexity == $O(n+L)$?? words (keeps track of current guess x^{(k)}, and computes bundle G^{(k)}, direction d^{(k)}, and scalar t^{(k)}?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1964 == Reference == https://link.springer.com/content/pdf/10.1007/BFb0120703.pdf")
- 11:15, 15 February 2023 Gomory's cutting method (ILP;MILPs Convex Optimization (Non-linear)) (hist | edit) [431 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n*poly(n, m)$)? (previously $O(n^{3})$) == Space Complexity == $O(nm+m^{2})$ words (See simplex algorithm, but also O(m) variables and constraints are introduced) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1953 == Reference == https://www.cs.uleth.ca/~benkoczi/OR/read/cutting-stock-LP.pdf")
- 11:15, 15 February 2023 Sattolo's algorithm (Cyclic Permutations Generating Random Permutations) (hist | edit) [321 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ words (Essentially in-situ) == Description == == Approximate? == Exact == Randomized? == Yes, ?? == Model of Computation == Word RAM == Year == 1986 == Reference == https://www.sciencedirect.com/science/article/abs/pii/0020019086900736")
- 11:15, 15 February 2023 Durstenfeld's Algorithm 235 (General Permutations Generating Random Permutations) (hist | edit) [295 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ words (Essentially in-situ) == Description == == Approximate? == Exact == Randomized? == Yes, ?? == Model of Computation == Word RAM == Year == 1964 == Reference == https://dl.acm.org/doi/10.1145/364520.364540")
- 11:15, 15 February 2023 Fisher–Yates/Knuth shuffle (General Permutations Generating Random Permutations) (hist | edit) [411 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words (Need to keep track of which elements have been struck out already) == Description == == Approximate? == Exact == Randomized? == Yes, ?? == Model of Computation == Word RAM == Year == 1938 == Reference == https://www.worldcat.org/title/statistical-tables-for-biological-agricultural-and-medical-research/oclc/14222135")
- 11:15, 15 February 2023 Gosper's algorithm ( Cycle Detection) (hist | edit) [408 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O((\lambda + \mu)$ log(\lambda + \mu) t_f) == Space Complexity == \Theta(log(\mu + \lambda)) (https://en.wikipedia.org/wiki/Cycle_detection#Gosper's_algorithm) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1978 == Reference == https://www.inwap.com/pdp10/hbaker/hakmem/flows.html#item132")
- 11:15, 15 February 2023 Brent's algorithm ( Cycle Detection) (hist | edit) [336 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O((\lambda + \mu)$ t_f) == Space Complexity == $O({1})$ Pointer algo (Algorithmic Cryptanalysis) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1973 == Reference == https://maths-people.anu.edu.au/~brent/pd/rpb005.pdf")
- 11:15, 15 February 2023 Floyd's tortoise and hare algorithm ( Cycle Detection) (hist | edit) [338 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O((\lambda + \mu)$ t_f) == Space Complexity == $O({1})$ Pointer algo (Algorithmic Cryptanalysis) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1967 == Reference == http://pds7.egloos.com/pds/200801/07/29/p636-floyd.pdf")
- 11:15, 15 February 2023 Naive Implementation (Exact Laplacian Solver SDD Systems Solvers) (hist | edit) [473 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n!)$ == Space Complexity == $O(n^{2})$ Word RAM (Derived: The Leibniz formula for the determinant of the Laplacian can be computed with constant space. The adjugate matrix of the Laplacian takes $n^2$ space.) == Description == Explicitly calculating the inverse of the Laplacian to solve for x == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == -")
- 11:15, 15 February 2023 Daitch; Spielman (Inexact Laplacian Solver SDD Systems Solvers) (hist | edit) [498 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{5/4} (log^{2} (n)$ loglogn)^{3/4} log({1}/ϵ)) == Space Complexity == $O(n)$ words (Derived: Uses an auxiliary sparse Cholesky decomposition which has $O(n)$ non-zero entries) == Description == Support Theory (Trusses and Stiffness Matrices) == Approximate? == Approximate Approximation Factor: \epsilon == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2007 == Reference == https://arxiv....")
- 11:15, 15 February 2023 Lee; Peng; Spielman (Inexact Laplacian Solver SDD Systems Solvers) (hist | edit) [513 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ words (Derived: Uses an auxiliary sparse Cholesky decomposition which has $O(n)$ non-zero entries) == Description == Recursive algorithm with sparse Cholesky factorization of Laplacian == Approximate? == Approximate Approximation Factor: The sparse Cholesky decomposition is a 2-approximation == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2015 == Reference...")
- 11:15, 15 February 2023 Kelner; Orecchia; Sidford; Zhu (Inexact Laplacian Solver SDD Systems Solvers) (hist | edit) [431 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(m log^{2} (n)$ loglogn) == Space Complexity == $O(n)$ words (Derived: Uses a spanning tree of the graph that the Laplacian is for) == Description == Low-stretch spanning tree == Approximate? == Approximate Approximation Factor: \epsilon == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2013 == Reference == https://arxiv.org/pdf/1301.6628.pdf")
- 11:15, 15 February 2023 Briggs; Henson; McCormick ( SDD Systems Solvers) (hist | edit) [321 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{1.{2}5} loglogn)$ == Space Complexity == () == Description == Multigrid == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2000 == Reference == http://www.math.ust.hk/~mamu/courses/531/tutorial_with_corrections.pdf")
- 11:15, 15 February 2023 Blelloch; Koutis; Miller; Tangwongsan (Inexact Laplacian Solver SDD Systems Solvers) (hist | edit) [434 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n logn)$ == Space Complexity == m + $O(n/log n)$ words (https://www.cs.cmu.edu/afs/cs.cmu.edu/Web/People/jkoutis/papers/SC10-paper.pdf) == Description == Combinatorial multigrid == Approximate? == Approximate Approximation Factor: ? == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2010 == Reference == https://ieeexplore.ieee.org/document/5644892")
- 11:15, 15 February 2023 Koutis; Miller and Peng (Inexact Laplacian Solver SDD Systems Solvers) (hist | edit) [444 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $\tilde{O}(m log n)$ == Space Complexity == $O(n)$ words (Derived: Uses an auxiliary chain of graphs, which can be kept track of with a single spanning tree) == Description == Incremental sparsifier == Approximate? == Approximate Approximation Factor: \epsilon == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2010 == Reference == https://arxiv.org/abs/1102.4842")
- 11:15, 15 February 2023 Boman; Chen; Hendrickson; Toledo (Inexact Laplacian Solver SDD Systems Solvers) (hist | edit) [452 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n log({1}/ϵ)$ ) == Space Complexity == $O(n)$ words (Derived: The preconditioners used have $O(n)$ non-zero entries) == Description == Maximum-weight-basis (MWB) preconditioners == Approximate? == Approximate Approximation Factor: \epsilon == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2004 == Reference == https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.343")
- 11:15, 15 February 2023 Boman; Hendrickson (Inexact Laplacian Solver SDD Systems Solvers) (hist | edit) [332 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $\tilde{O}(mn^{({1}/{2})})$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: \epsilon == Randomized? == No, deterministic == Model of Computation == == Year == 2003 == Reference == https://epubs.siam.org/doi/10.1137/S0895479801390637")
- 11:15, 15 February 2023 Bern; Gilbert; Hendrickson (Inexact Laplacian Solver SDD Systems Solvers) (hist | edit) [304 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n loglogn)$ == Space Complexity == () == Description == Support Graph Preconditioning == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2006 == Reference == https://dl.acm.org/citation.cfm?id=1117896")
- 11:15, 15 February 2023 Spielman, Teng (Inexact Laplacian Solver SDD Systems Solvers) (hist | edit) [556 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(m log^c n)$ == Space Complexity == $O(n)$ words (Derived: Uses spanning trees and sparse Cholesky factorization which both take $O(n)$ space) == Description == Spectral Sparsification == Approximate? == Approximate Approximation Factor: \epsilon == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2004 == Reference == https://dl.acm.org/doi/pdf/10.1145/1007352.1007372?casa_token=k60CrC_UJp0AA...")
- 11:15, 15 February 2023 Chan-Singhal-Liu ( Mutual Exclusion) (hist | edit) [422 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(logn)$ == Space Complexity == $O({1})$ per process, $O(n)$ total? communication variables? (Each process seems to keep track of a constant number of variables (see algorithm descriiption)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1990 == Reference == https://ieeexplore.ieee.org/document/113817")
- 11:15, 15 February 2023 Peterson's algorithm ( Mutual Exclusion) (hist | edit) [378 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ total communication variables? (see original paper ("requires $2n-1$ shared variables of size $n$")) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1981 == Reference == https://zoo.cs.yale.edu/classes/cs323/doc/Peterson.pdf")
- 11:15, 15 February 2023 Vaidya (Inexact Laplacian Solver SDD Systems Solvers) (hist | edit) [366 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn^{({3}/{4})$}) == Space Complexity == $O(n)$ words (Derived: Uses a spanning tree (size $O(n)$)) == Description == Using maximum-weight spanning trees == Approximate? == Approximate Approximation Factor: \epsilon == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1990 == Reference ==")
- 11:15, 15 February 2023 Naimi-Trehel's algorithm ( Mutual Exclusion) (hist | edit) [442 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(logn)$ == Space Complexity == $O({1})$ per process, $O(n)$ total? communication variables? (Each process keeps track of a constant number of variables (see algorithm descriiption)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1996 == Reference == https://www.sciencedirect.com/science/article/abs/pii/S0743731596900416")
- 11:14, 15 February 2023 Dekker's algorithm (2-thread Mutual Exclusion Mutual Exclusion) (hist | edit) [246 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == communication variables? () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1963 == Reference == -")
- 11:14, 15 February 2023 Elliptic-curve Diffie-Hellman (ECDH) (Key Exchange Key Exchange) (hist | edit) [452 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mult(n)$*n^{2})? where mult(n) is running time on n-bit multiplication == Space Complexity == $O(n)$ bits (Each party only keeps track of a constant number of n-bit integers) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 2006 == Reference == https://csrc.nist.gov/publications/detail/sp/800-56a/revised/archive/2007-03-14")
- 11:14, 15 February 2023 Diffie–Hellman key exchange (Key Exchange Key Exchange) (hist | edit) [412 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mult(n)$*n) where mult(n) is running time on n-bit multiplication == Space Complexity == $O(n)$ bits (Each party only keeps track of a constant number of n-bit integers) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1978 == Reference == https://ieeexplore.ieee.org/document/1055638")
- 11:14, 15 February 2023 Klein (section 5) (Planar Bipartite Graph Perfect Matching Maximum Cardinality Matching) (hist | edit) [532 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{({4}/{3})$} logV) == Space Complexity == $O(V^{({4}/{3})$})? words (Considers and operates on a graph partition (which still takes up $O(E)=O(V)$ space), and computes shortest-path distances within each graph partition, the total of which requires $O(V^{(4/3)})$ space) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1997 == Reference == http:...")
- 11:14, 15 February 2023 Mucha, Sankowski (general) (General Graph MCM Maximum Cardinality Matching) (hist | edit) [365 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{2.{37}6})$ == Space Complexity == $O(V^{2})$?? words (Algorithm uses/manipulates constant number of matrices and graphs?) == Description == == Approximate? == Exact == Randomized? == Yes, Monte Carlo == Model of Computation == Word RAM == Year == 2004 == Reference == https://ieeexplore.ieee.org/document/1366244")
- 11:14, 15 February 2023 Gabow; Tarjan (General Graph MCM Maximum Cardinality Matching) (hist | edit) [432 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O((V^{0.5})$E) == Space Complexity == $O(E)$ auxiliary? words (https://web.eecs.umich.edu/~pettie/matching/Gabow-Tarjan-scaling-general-graph-matching.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1991 == Reference == https://web.eecs.umich.edu/~pettie/matching/Gabow-Tarjan-scaling-general-graph-matching.pdf")
- 11:14, 15 February 2023 Chandran and Hochbaum (Bipartite Graph MCM Maximum Cardinality Matching) (hist | edit) [416 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(min(V*k, E)$+sqrt(k)*min(k^{2}, E)) == Space Complexity == $O(E)$ auxiliary?? words (Designs a flow network and runs pseudoflow algorithms on graph; space can be reused if too many residual graphs are created) == Description == == Approximate? == Exact == Randomized? == Yes, == Model of Computation == Word RAM == Year == 2011 == Reference == https://arxiv.org/abs/1105.1569")
- 11:14, 15 February 2023 Blum (General Graph MCM Maximum Cardinality Matching) (hist | edit) [436 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O((V^{0.5})$E) == Space Complexity == $O(E)$ auxiliary?? words (Each phase, creates a separate directed graph and solves a reachability problem on it. Can reuse space across phases) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1990 == Reference == https://web.eecs.umich.edu/~pettie/matching/Blum-matching-ICALP90.pdf")
- 11:14, 15 February 2023 Madry's algorithm (Bipartite Graph MCM Maximum Cardinality Matching) (hist | edit) [443 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(E^{10/7}*polylog(V)$) == Space Complexity == $O(E + V)$ words (Derived: Uses an augmented graph (copy of the original graph plus an additional node with edges between it and all other nodes)) == Description == Based on electric flows == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2013 == Reference == https://arxiv.org/abs/1307.2205")
- 11:14, 15 February 2023 Hopcroft–Karp algorithm (Bipartite Graph MCM Maximum Cardinality Matching) (hist | edit) [422 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O((V^{0.5})$E) == Space Complexity == $O(V)$ auxiliary words (maximal set of vertex-disjoint shortest augmenting paths uses O(V) space to store, taking symmetric difference also uses O(V) space) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1973 == Reference == https://epubs.siam.org/doi/10.1137/0202019")
- 11:14, 15 February 2023 Mucha; Sankowski (planar) (Bipartite Graph MCM Maximum Cardinality Matching) (hist | edit) [550 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{(\omega/{2})$}) where omega is the exponent on matrix multiplication == Space Complexity == $O(VlogV)$??? words (Paper mentions matrices with O(VlogV) nonempty entries; unclear if there are any other space-consuming objects (on first passthrough) as planar graphs only require O(V) space) == Description == == Approximate? == Exact == Randomized? == Yes, Monte Carlo == Model of Computation == Word RAM == Year == 2006 == Re...")
- 11:14, 15 February 2023 Ford–Fulkerson algorithm (Bipartite Graph MCM Maximum Cardinality Matching) (hist | edit) [456 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(VE)$ == Space Complexity == $O(E)$ auxiliary words (creating new graph and using it as input to the Ford-Fulkerson algorithm) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1956 == Reference == https://www.cambridge.org/core/journals/canadian-journal-of-mathematics/article/maximal-flow-through-a-network/5D6E55D3B06C4F7B1043BC1D82D40764")
- 11:14, 15 February 2023 Hash join ( Joins) (hist | edit) [285 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n+m)$ == Space Complexity == $O(n+m)$? words (Need a hash table of at least that size) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM(?) == Year == 1960 == Reference == -")
- 11:14, 15 February 2023 Sort merge join ( Joins) (hist | edit) [300 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn + mlogm)$ == Space Complexity == $O(n+m)$? words (Need sorted lists of indices of input tables) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM(?) == Year == 1960 == Reference == -")
- 11:14, 15 February 2023 Nested loop join ( Joins) (hist | edit) [299 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nm)$ == Space Complexity == $O({1})$ words (Just need to keep track of which rows are being checked) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM(?) == Year == 1960 == Reference == -")
- 11:14, 15 February 2023 Basic Local Alignment Search Tool (BLAST) (Edit Sequence, constant-size alphabet Sequence Alignment) (hist | edit) [369 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(mn)$? words (Uses at most a constant number of O(m)*O(n) arrays, whose contents are of size O(1)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1990 == Reference == https://www.ncbi.nlm.nih.gov/pubmed/2231712")
- 11:14, 15 February 2023 Gapped BLAST (Edit Sequence, constant-size alphabet Sequence Alignment) (hist | edit) [369 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(mn)$? words (Uses at most a constant number of O(m)*O(n) arrays, whose contents are of size O(1)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1997 == Reference == https://www.ncbi.nlm.nih.gov/pubmed/9254694")
- 11:14, 15 February 2023 Apostolico–Giancarlo Algorithm (Single String Search String Search) (hist | edit) [440 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(m + s)$ + $O(n)$ == Space Complexity == $O(m)$ words (https://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1456&context=cstech&sei-redir=1) == Description == Variant of BM == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1986 == Reference == https://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1456&context=cstech&sei-redir=1")
- 11:14, 15 February 2023 Boyer-Moore-Horspool (BMH) (Single String Search String Search) (hist | edit) [386 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn + s)$ == Space Complexity == $O(s)$ words (Derived: Uses a bad-character shift table of size $O(s)$) == Description == Bad-character heuristic == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1980 == Reference == https://onlinelibrary.wiley.com/doi/abs/10.1002/spe.4380100608")
- 11:14, 15 February 2023 BOM (Backward Oracle Matching) (Single String Search String Search) (hist | edit) [396 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(m)$ + $O(mn)$ == Space Complexity == $O(m)$ words (https://link.springer.com/content/pdf/10.1007/3-540-47849-3_18.pdf) == Description == Automaton-based oracle == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1999 == Reference == https://link.springer.com/chapter/10.1007/3-540-47849-3_18")
- 11:14, 15 February 2023 Raita Algorithm (Single String Search String Search) (hist | edit) [388 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn + s)$ == Space Complexity == $O(s)$ words (Derived: Uses a bad-character shift table of size $O(s)$) == Description == Slight variation of BMH == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1991 == Reference == https://www.cin.ufpe.br/~paguso/courses/if767/bib/Raita_1992.pdf")