User contributions for Admin

15 February 2023

• 11:1411:14, 15 February 2023 diff hist +246‎ N Dekker's algorithm (2-thread Mutual Exclusion Mutual Exclusion) ‎ Created page with "== Time Complexity == $O(n)$ == Space Complexity == communication variables? () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1963 == Reference == -" current
• 11:1411:14, 15 February 2023 diff hist +412‎ N Diffie–Hellman key exchange (Key Exchange Key Exchange) ‎ 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" current
• 11:1411:14, 15 February 2023 diff hist +452‎ N Elliptic-curve Diffie-Hellman (ECDH) (Key Exchange Key Exchange) ‎ 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" current
• 11:1411:14, 15 February 2023 diff hist +442‎ N Gabow; Tarjan (General Graph MCM Maximum Cardinality Matching) ‎ 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:1411:14, 15 February 2023 diff hist +532‎ N Klein (section 5) (Planar Bipartite Graph Perfect Matching Maximum Cardinality Matching) ‎ 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:..." current
• 11:1411:14, 15 February 2023 diff hist +365‎ N Mucha, Sankowski (general) (General Graph MCM Maximum Cardinality Matching) ‎ 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" current
• 11:1411:14, 15 February 2023 diff hist +426‎ N Chandran and Hochbaum (Bipartite Graph MCM Maximum Cardinality Matching) ‎ 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:1411:14, 15 February 2023 diff hist +446‎ N Blum (General Graph MCM Maximum Cardinality Matching) ‎ 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:1411:14, 15 February 2023 diff hist +443‎ N Madry's algorithm (Bipartite Graph MCM Maximum Cardinality Matching) ‎ 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" current
• 11:1411:14, 15 February 2023 diff hist +547‎ N Mucha; Sankowski (planar) (Bipartite Graph MCM Maximum Cardinality Matching) ‎ 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:1411:14, 15 February 2023 diff hist +432‎ N Hopcroft–Karp algorithm (Bipartite Graph MCM Maximum Cardinality Matching) ‎ 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:1411:14, 15 February 2023 diff hist +466‎ N Ford–Fulkerson algorithm (Bipartite Graph MCM Maximum Cardinality Matching) ‎ 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:1411:14, 15 February 2023 diff hist +303‎ N Sort merge join ( Joins) ‎ 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:1411:14, 15 February 2023 diff hist +288‎ N Hash join ( Joins) ‎ 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:1411:14, 15 February 2023 diff hist +302‎ N Nested loop join ( Joins) ‎ 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:1411:14, 15 February 2023 diff hist +369‎ N Basic Local Alignment Search Tool (BLAST) (Edit Sequence, constant-size alphabet Sequence Alignment) ‎ 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" current
• 11:1411:14, 15 February 2023 diff hist +369‎ N Gapped BLAST (Edit Sequence, constant-size alphabet Sequence Alignment) ‎ 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" current
• 11:1411:14, 15 February 2023 diff hist +440‎ N Apostolico–Giancarlo Algorithm (Single String Search String Search) ‎ 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" current
• 11:1411:14, 15 February 2023 diff hist +396‎ N BOM (Backward Oracle Matching) (Single String Search String Search) ‎ 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" current
• 11:1411:14, 15 February 2023 diff hist +386‎ N Boyer-Moore-Horspool (BMH) (Single String Search String Search) ‎ 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" current
• 11:1411:14, 15 February 2023 diff hist +388‎ N Raita Algorithm (Single String Search String Search) ‎ 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" current
• 11:1411:14, 15 February 2023 diff hist +410‎ N Aho–Corasick (AC) Algorithm (Multiple String Search String Search) ‎ Created page with "== Time Complexity == $O(n + m + z)$ == Space Complexity == $O(km)$ words (Derived: Number of states of the automaton that is created) == Description == Automaton-based, finite automaton that tracks the partial prefix match == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1975 == Reference == https://cr.yp.to/bib/1975/aho.pdf" current
• 11:1411:14, 15 February 2023 diff hist +347‎ N Backward Non-Deterministic DAWG Matching (BNDM) (Single String Search String Search) ‎ Created page with "== Time Complexity == $O(n+m)$ == Space Complexity == $O(sm)$ words (https://link.springer.com/chapter/10.1007/BFb0030778) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1998 == Reference == https://link.springer.com/chapter/10.1007/BFb0030778" current
• 11:1411:14, 15 February 2023 diff hist +434‎ N Commentz-Walter Algorithm (Multiple String Search String Search) ‎ Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(km)$ words (Derived: Number of states of the automaton that is created) == Description == Automaton-based, constructs a converse state machine from the given patterns == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1979 == Reference == https://link.springer.com/chapter/10.1007/3-540-09510-1_10" current
• 11:1411:14, 15 February 2023 diff hist +389‎ N Fast Hybrid Algorithm (Single String Search String Search) ‎ Created page with "== Time Complexity == $O(n+m)$+ $O(m+s)$ == Space Complexity == $O(m)$ words (Derived: Uses three tables, each of size $O(m)$) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2017 == Reference == https://thesai.org/Downloads/Volume8No6/Paper_15-Fast_Hybrid_String_Matching_Algorithm.pdf" current
• 11:1411:14, 15 February 2023 diff hist +327‎ N Quick-Skip Searching (Single String Search String Search) ‎ Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(m)$ words (Derived: Uses two tables, both of size $O(m)$) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2012 == Reference == http://www.ijcte.org/papers/462-G1278.pdf" current
• 11:1411:14, 15 February 2023 diff hist +275‎ N String-Matching with Finite Automata (Single String Search String Search) ‎ Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(m)$ words (Derived: $O(m)$ states in the DFA) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == -" current
• 11:1411:14, 15 February 2023 diff hist +364‎ N Two-way String-Matching Algorithm (Single String Search String Search) ‎ Created page with "== Time Complexity == $O(n + m)$ == Space Complexity == $O({1})$ words (http://monge.univ-mlv.fr/~mac/Articles-PDF/CP-1991-jacm.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1991 == Reference == http://monge.univ-mlv.fr/~mac/Articles-PDF/CP-1991-jacm.pdf" current
• 11:1411:14, 15 February 2023 diff hist +403‎ N General number field sieve (Second Category Integer Factoring Integer Factoring) ‎ Created page with "== Time Complexity == $O(exp(({1}+o({1})$)({64}n/{9})^{({1}/{3})}(log n)^{({2}/{3})}) heuristically? == Space Complexity == $O(n^{2/3})$ bits (http://www.ams.org/notices/199612/pomerance.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1996 == Reference == http://www.ams.org/notices/199612/pomerance.pdf" current
• 11:1411:14, 15 February 2023 diff hist +374‎ N Shor's algorithm Quantum Implementation (Second Category Integer Factoring Integer Factoring) ‎ Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ qubits (https://quantum-computing.ibm.com/composer/docs/iqx/guide/shors-algorithm) == Description == Quantum algorithm == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Quantum == Year == 1994 == Reference == https://ieeexplore.ieee.org/document/365700/" current
• 11:1411:14, 15 February 2023 diff hist +419‎ N Special number field sieve (First Category Integer Factoring Integer Factoring) ‎ Created page with "== Time Complexity == $O(exp(({1}+o({1})$)({32}n/{9})^{({1}/{3})}(log n)^{({2}/{3})}) heuristically? == Space Complexity == $O(n^{2/3})$ bits (http://www.ams.org/notices/199612/pomerance.pdf) == Description == For integers of the form $r^e \pm s$, for r and s relatively small == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1940 == Reference ==" current
• 11:1411:14, 15 February 2023 diff hist +466‎ N Bader & Cong Parallel Implementation (Undirected, General MST Minimum Spanning Tree (MST)) ‎ Created page with "== Time Complexity == $O(E log(V)$/p) == Space Complexity == $O(V)$ total words (Initializes and uses a constant number of arrays of size O(V) (and does work similar to work done in Boruvka/Prim algorithm)) == Description == Parallel algorithm == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == PRAM/SMPs? == Year == 2006 == Reference == https://www.sciencedirect.com/science/article/pii/S0743731506001262"
• 11:1411:14, 15 February 2023 diff hist +293‎ N Incremental convex hull algorithm; Michael Kallay ( Convex Hull) ‎ Created page with "== Time Complexity == $O(n log n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1984 == Reference == https://www.sciencedirect.com/science/article/pii/002001908490084X"
• 11:1411:14, 15 February 2023 diff hist +279‎ N Alon and Kahale (3-Graph Coloring Graph Coloring) ‎ Created page with "== Time Complexity == $O({1.24}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1997 == Reference == http://www.cs.tau.ac.il/~nogaa/PDFS/spectcolpr1.pdf" current
• 11:1411:14, 15 February 2023 diff hist +273‎ N Hirsch (3-Graph Coloring Graph Coloring) ‎ Created page with "== Time Complexity == $O({1.239}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1998 == Reference == https://dl.acm.org/doi/10.5555/314613.314838" current
• 11:1411:14, 15 February 2023 diff hist +300‎ N Johnson (3-Graph Coloring Graph Coloring) ‎ Created page with "== Time Complexity == $O({1.4422}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1988 == Reference == https://www.sciencedirect.com/science/article/abs/pii/0020019088900658" current
• 11:1411:14, 15 February 2023 diff hist +260‎ N Schöning (3-Graph Coloring Graph Coloring) ‎ Created page with "== Time Complexity == $O({1.333}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == Yes, == Model of Computation == == Year == 1999 == Reference == https://ieeexplore.ieee.org/document/814612" current
• 11:1411:14, 15 February 2023 diff hist +296‎ N Robson (3-Graph Coloring Graph Coloring) ‎ Created page with "== Time Complexity == $O({1.2108}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1986 == Reference == https://www.sciencedirect.com/science/article/pii/0196677486900325" current
• 11:1411:14, 15 February 2023 diff hist +328‎ N Wu et al. (LCS Longest Common Subsequence) ‎ Created page with "== Time Complexity == $O(n(m-r)$) == Space Complexity == $O(m^{2})$? words (Derived: Same as the above two) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1990 == Reference == https://publications.mpi-cbg.de/Wu_1990_6334.pdf" current
• 11:1411:14, 15 February 2023 diff hist +326‎ N Ahuja et al. ( Maximum Flow) ‎ Created page with "== Time Complexity == $O(VELog(V(LogU)$^{0.5} / E)) == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1987 == Reference == http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.86.5093&rep=rep1&type=pdf" current
• 11:1411:14, 15 February 2023 diff hist +393‎ N Miller and Myers (LCS Longest Common Subsequence) ‎ Created page with "== Time Complexity == $O(n(m-r)$) == Space Complexity == $O(m^{2})$ words (Derived: Uses an upper triangular matrix $M$ that is size $(m + 1) \times (m + 1)$) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1985 == Reference == https://onlinelibrary.wiley.com/doi/abs/10.1002/spe.4380151102" current
• 11:1411:14, 15 February 2023 diff hist +375‎ N Nakatsu et al. (LCS Longest Common Subsequence) ‎ Created page with "== Time Complexity == $O(n(m-r)$) == Space Complexity == $O(m^{2})$ 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 == 1982 == Reference == https://link.springer.com/article/10.1007/BF00264437" current
• 11:1411:14, 15 February 2023 diff hist +7‎ Rick (LCS Longest Common Subsequence) ‎No edit summary Tag: Manual revert
• 11:1411:14, 15 February 2023 diff hist +1‎ Harvey; Hoeven; Lecerf ( Multiplication) ‎No edit summary Tag: Manual revert
• 11:1411:14, 15 February 2023 diff hist +10‎ Covanov and Thomé ( Multiplication) ‎No edit summary Tag: Manual revert
• 11:1411:14, 15 February 2023 diff hist −1‎ Harvey; Hoeven; Lecerf ( Multiplication) ‎No edit summary Tags: Manual revert Reverted
• 11:1311:13, 15 February 2023 diff hist −97‎ Beigel & Eppstein (3-Graph Coloring Graph Coloring) ‎No edit summary Tags: Manual revert Reverted
• 11:1311:13, 15 February 2023 diff hist +97‎ Beigel & Eppstein (3-Graph Coloring Graph Coloring) ‎No edit summary Tags: Manual revert Reverted
• 11:1311:13, 15 February 2023 diff hist +4‎ Goldberg & Rao (Integer Maximum Flow Maximum Flow) ‎No edit summary Tag: Manual revert
• 11:1311:13, 15 February 2023 diff hist −4‎ Goldberg & Rao (Integer Maximum Flow Maximum Flow) ‎No edit summary Tags: Manual revert Reverted