New pages
Jump to navigation
Jump to search
(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)
- 11:17, 15 February 2023 Rabin Karp (The Frequent Words Problem The Frequent Words Problem) (hist | edit) [312 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(max(n, sigma^k)$) auxiliary? words (Keep track of counts on at most n-k+1 or sigma^k words) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1987 == Reference ==")
- 11:17, 15 February 2023 Naive solution (The Frequent Words Problem The Frequent Words Problem) (hist | edit) [311 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(max(n, sigma^k)$) auxiliary words (Keep track of counts on at most n-k+1 or sigma^k words) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 11:17, 15 February 2023 Hanoi graph (Tower of Hanoi Tower of Hanoi) (hist | edit) [317 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == bits () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2008 == Reference == https://books.google.com/books/about/Topics_in_Graph_Theory.html?id=pSv3XotPCQgC")
- 11:17, 15 February 2023 Gray-code based (Tower of Hanoi Tower of Hanoi) (hist | edit) [298 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O(n)$ auxiliary bits (Need to keep track of an n-bit counter for Gray codes) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == NA")
- 11:17, 15 February 2023 Non-recursion based (Tower of Hanoi Tower of Hanoi) (hist | edit) [293 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O(n)$ auxiliary bits (Only need to keep track of current configuration) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == NA")
- 11:17, 15 February 2023 Recursion based (Tower of Hanoi Tower of Hanoi) (hist | edit) [378 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O(n*log n)$ auxiliary bits (Need to keep track of an O(n)-sized recursive stack, each entry requiring O(log n) space (i.e. which tower size to manipulate)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == NA")
- 11:17, 15 February 2023 Iteration based (Tower of Hanoi Tower of Hanoi) (hist | edit) [293 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O(n)$ auxiliary bits (Only need to keep track of current configuration) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1883 == Reference == NA")
- 11:17, 15 February 2023 Rivin, Zabih (Counting Solutions n-Queens Problem) (hist | edit) [362 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({8}^n*poly(n)$) == Space Complexity == $O({8}^n*n^{2})$ words (http://www.cs.cornell.edu/~rdz/Papers/RZ-IPL92.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1992 == Reference == http://www.cs.cornell.edu/~rdz/Papers/RZ-IPL92.pdf")
- 11:17, 15 February 2023 Naive solution ( Frequent Words with Mismatches Problem) (hist | edit) [456 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*f_{bin}(sigma-{1}, k, d)$) where f_{bin}(x, y, z) = sum_{i=0}^z C(y, i)*x^i == Space Complexity == $O(max(n*f_{bin}(sigma-{1}, k, d)$, sigma^k)) auxiliary where f_{bin}(x, y, z) = sum_{i=0}^z C(y, i)*x^i words (Keep track of counts on at most that many words) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 11:17, 15 February 2023 Naive Solution (Median String Problem with Unbounded Alphabets Median String Problem) (hist | edit) [384 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == {2}^$O(n)$ == Space Complexity == $O(n)$ auxiliary words (Keep track of current string being checked, current best string, and Levenshtein distances (which can be computed recursively using O(n) space)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1965 == Reference ==")
- 11:17, 15 February 2023 Gunther Determinants solution (Counting Solutions; Constructing solutions n-Queens Problem) (hist | edit) [381 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n!)$ == Space Complexity == $O(n!)$ ? words (Seems like this one lists out all of the terms in the discriminant; presumably there is a better way but that amounts to the naive algorithm) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1874 == Reference ==")
- 11:17, 15 February 2023 Nauck (Counting Solutions; Constructing solutions n-Queens Problem) (hist | edit) [232 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n!)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1850 == Reference ==")
- 11:17, 15 February 2023 Dijkstra (Counting Solutions; Constructing solutions n-Queens Problem) (hist | edit) [408 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n!)$ == Space Complexity == $O(n)$ words (Keep track of current configuration being tested and restrictions on where next queen can be placed, along with current count) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1972 == Reference == https://dl.acm.org/citation.cfm?id=1243380")
- 11:17, 15 February 2023 Naive + 1 queen per row restriction (Counting Solutions; Constructing solutions n-Queens Problem) (hist | edit) [312 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n!)$ == Space Complexity == $O(n)$ words (Keep track of current configuration being tested, along with current count) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1850 == Reference ==")
- 11:17, 15 February 2023 Naive Algorithm (Counting Solutions; Constructing solutions n-Queens Problem) (hist | edit) [313 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^n)$ == Space Complexity == $O(n)$ words (Keep track of current configuration being tested, along with current count) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1848 == Reference ==")
- 11:17, 15 February 2023 Outside-In algorithm (Turnpike Problem Turnpike Problem) (hist | edit) [330 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n nlogn)$ == Space Complexity == $O(n)$ words (Seems like this just needs to keep track of current configuration being tested) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1991 == Reference == NA")
- 11:17, 15 February 2023 Gries, Martin (Transitive Reduction Problem of Directed Graphs Transitive Reduction Problem) (hist | edit) [433 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$ words (Generally keeps track of O(1) information for every pair (u, v) of vertices? and not much additional information needed) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1989 == Reference == https://www.sciencedirect.com/science/article/pii/0167642389900397")
- 11:17, 15 February 2023 Aho, Garey & Ullman (Transitive Reduction Problem of Directed Graphs Transitive Reduction Problem) (hist | edit) [333 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^omega)$ where omega is the exponent on boolean matrix multiplication == Space Complexity == $O(n^{2})$ words (see (boolean) matrix multiplication) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1972 == Reference == https://epubs.siam.org/doi/pdf/10.1137/0201008")
- 11:17, 15 February 2023 Guibas, Sedgewick Red-Black Tree ( Self-Balancing Trees Search) (hist | edit) [402 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(logn)$ == Space Complexity == $O({1})$ words (Need to keep track of constant amount of info during search (i.e. which node we're on and what direction to go)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1972 == Reference == https://ieeexplore.ieee.org/document/4567957")
- 11:17, 15 February 2023 Hopcroft 2-3 Tree ( Self-Balancing Trees Search) (hist | edit) [355 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(logn)$ == Space Complexity == $O({1})$ words (Need to keep track of constant amount of info during search (i.e. which node we're on and what direction to go)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1970 == Reference ==")
- 11:17, 15 February 2023 Guibas, Sedgewick Red-Black Tree ( Self-Balancing Trees Deletion) (hist | edit) [301 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(logn)$ == Space Complexity == $O({1})$ words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1972 == Reference == https://ieeexplore.ieee.org/document/4567957")
- 11:17, 15 February 2023 Hopcroft 2-3 Tree ( Self-Balancing Trees Deletion) (hist | edit) [254 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(logn)$ == Space Complexity == $O({1})$ words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1970 == Reference ==")
- 11:17, 15 February 2023 Guibas, Sedgewick Red-Black Tree ( Self-Balancing Trees Insertion) (hist | edit) [301 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(logn)$ == Space Complexity == $O({1})$ words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1972 == Reference == https://ieeexplore.ieee.org/document/4567957")
- 11:17, 15 February 2023 Hopcroft 2-3 Tree ( Self-Balancing Trees Insertion) (hist | edit) [361 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(logn)$ == Space Complexity == $O({1})$ words (Each node being changed requires constant auxiliary space to make changes; can reuse space across nodes being changed) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1970 == Reference ==")
- 11:17, 15 February 2023 Bayer, McCreight B-Tree ( Self-Balancing Trees Creation) (hist | edit) [323 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*b*log(n)$/log(b))? == Space Complexity == $O(n)$ words (Need to keep track of intermediary stages of tree before outputting) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1970 == Reference ==")
- 11:17, 15 February 2023 Tarjan Splay Tree ( Self-Balancing Trees Creation) (hist | edit) [311 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (Need to keep track of intermediary stages of tree before outputting) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1985 == Reference ==")
- 11:17, 15 February 2023 Hopcroft 2-3 Tree ( Self-Balancing Trees Creation) (hist | edit) [311 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (Need to keep track of intermediary stages of tree before outputting) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1970 == Reference ==")
- 11:17, 15 February 2023 Guibas, Sedgewick Red-Black Tree ( Self-Balancing Trees Creation) (hist | edit) [358 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (Need to keep track of intermediary stages of tree before outputting) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1972 == Reference == https://ieeexplore.ieee.org/document/4567957")
- 11:17, 15 February 2023 AVL Tree ( Self-Balancing Trees Creation) (hist | edit) [311 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (Need to keep track of intermediary stages of tree before outputting) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1962 == Reference ==")
- 11:17, 15 February 2023 Pollard's kangaroo algorithm (Discrete Logarithm Over Finite Fields Logarithm Calculations) (hist | edit) [481 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O({1})$ words (Stores a constant number of O(n)-bit values (a, b, x_i, d, x_N, y_i, d_i) per iteration; assumes that the pseudorandom map is part of the input) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1978 == Reference == https://www.ams.org/mcom/1978-32-143/S0025-5718-1978-0491431-9/S0025-5718-1978-0491431...")
- 11:17, 15 February 2023 Pollard's rho algorithm (Discrete Logarithm Over Finite Fields Logarithm Calculations) (hist | edit) [403 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^{(n/{2})})$ == Space Complexity == $O({1})$ words (Stores a constant number of O(n)-bit values per iteration) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1978 == Reference == https://www.ams.org/mcom/1978-32-143/S0025-5718-1978-0491431-9/S0025-5718-1978-0491431-9.pdf")
- 11:17, 15 February 2023 Pohlig-Hellman (Discrete Logarithm Over Finite Fields Logarithm Calculations) (hist | edit) [551 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^{\sqrt{n}})$, only for primes; does much better for composites == Space Complexity == $O({2}^{\sqrt{n}})$ (though only for primes) words (A step in the algorithm involves using baby-steps giant-steps to compute discrete logs; the rest of the algorithm (including CRT and repeated powers) isn't as intensive) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM ==...")
- 11:17, 15 February 2023 Number Field Sieve (NFS) (Discrete Logarithm Over Finite Fields Logarithm Calculations) (hist | edit) [335 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == 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 == 1990 == Reference == http://www.ams.org/notices/199612/pomerance.pdf")
- 11:17, 15 February 2023 Index calculus algorithm (Discrete Logarithm Over Finite Fields, F q Logarithm Calculations) (hist | edit) [414 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(e^{(\sqrt({2}) \sqrt(n*logn))})$ == Space Complexity == $O(n+r^{2})$? bits (See Dixon's algorithm for factoring integers; also works with an O(r)-by-O(r) sized matrix (to obtain discrete logs of primes in factor base)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == RAM? == Year == 1922 == Reference == NA")
- 11:17, 15 February 2023 Function Field Sieve (FFS) (Discrete Logarithm Over Finite Fields Logarithm Calculations) (hist | edit) [342 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O(n^{2/3})$? bits (Derived: same space as Number Field Sieve?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1999 == Reference == https://www.sciencedirect.com/science/article/pii/S0890540198927614")
- 11:17, 15 February 2023 Baby-step Giant-step (Discrete Logarithm Over Finite Fields Logarithm Calculations) (hist | edit) [338 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^{\sqrt{n}})$ == Space Complexity == $O({2}^{\sqrt{n}})$ words (Derived: Uses a hash table of this size) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1971 == Reference == https://doi.org/10.1090/pspum/020")
- 11:17, 15 February 2023 Trial Multiplication (Discrete Logarithm Over Finite Fields Logarithm Calculations) (hist | edit) [430 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O({1})$ words (Derived: Each power $k$ that you try in the brute force search is size $O(\log n)$, which is $O(1)$ when considering $O(\log n)$ size words. Only need to keep track of one at a time.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == NA")
- 11:17, 15 February 2023 Rautiainen, Marschall (Sequence-to-Graph Alignment Sequence-to-Graph Alignment) (hist | edit) [499 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(|V | + m|E|)$ == Space Complexity == $O(mV)$ words (Derived: algorithm uses a V-sized array of bitvectors each of which is of length m, and also uses a priority queue which has at most V elements. The precomputed pattern bitvectors also takes up O(V * m) space.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2019 == Reference == https://www.ncb...")
- 11:17, 15 February 2023 Jain, Chang (Sequence-to-Graph Alignment Sequence-to-Graph Alignment) (hist | edit) [358 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(|V | + m|E|)$ == Space Complexity == $O(V)$ words (https://www.biorxiv.org/content/10.1101/522912v1.full.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2019 == Reference == https://www.biorxiv.org/content/10.1101/522912v1.full.pdf")
- 11:17, 15 February 2023 Rautiainen and Marschall (Sequence-to-Graph Alignment Sequence-to-Graph Alignment) (hist | edit) [348 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(|V | + m|E|)$ == Space Complexity == $O(\sqrt(m)|V|)$ words (same paper) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2017 == Reference == https://www.biorxiv.org/content/10.1101/216127v1")
- 11:17, 15 February 2023 V-ALIGN (Sequence-to-Graph Alignment Sequence-to-Graph Alignment) (hist | edit) [369 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(m|V |E|)$ == Space Complexity == $O(mV)$ words (https://www.biorxiv.org/content/10.1101/124941v1.full) == Description == Dynamic Programming == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2018 == Reference == https://www.biorxiv.org/content/10.1101/124941v1.full")
- 11:17, 15 February 2023 HybridSpades (Sequence-to-Graph Alignment Sequence-to-Graph Alignment) (hist | edit) [306 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(m(|V | log(m|V |)$ + |E|)) == Space Complexity == $O(m*(V+E)$) words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2015 == Reference == https://www.ncbi.nlm.nih.gov/pubmed/26589280")
- 11:17, 15 February 2023 Navarro (Sequence-to-Graph Alignment Sequence-to-Graph Alignment) (hist | edit) [382 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n(|V | + |E|)$) == Space Complexity == $O(V)$ words (same paper) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2000 == Reference == https://www.sciencedirect.com/science/article/pii/S0304397599003333")
- 11:17, 15 February 2023 Amir et al. (Sequence-to-Graph Alignment Sequence-to-Graph Alignment) (hist | edit) [380 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(m(|n | log |m | + |E|)$) == Space Complexity == $O(mn)$ words (https://reader.elsevier.com/reader/sd/pii/S0304397599003333?token=C0E6BDF7BA98CD5C338EDB86675CB3A29AF44F5B046E169EE0F115788255757C815F0F0307EAF080CDF9A9DE7AA37764) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1997 == Reference == https://link.springer.com/chapter/10.1007/3-540-633...")
- 11:17, 15 February 2023 PSLQ algorithm (Integer Relation Integer Relation) (hist | edit) [431 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$ words (Derived: Uses multiple nxn auxiliary matrices) == Description == Partial Sum of Squares using QR decomposition == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1992 == Reference == https://www.ams.org/journals/mcom/1999-68-225/S0025-5718-99-00995-3/S0025-5718-99-00995-3.pdf")
- 11:17, 15 February 2023 PSOS algorithm (Integer Relation Integer Relation) (hist | edit) [416 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$ words (Derived: Uses multiple nxn auxiliary matrices) == Description == Partial Sum of Squares == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1988 == Reference == https://www.ams.org/journals/mcom/1989-53-188/S0025-5718-1989-0979934-9/S0025-5718-1989-0979934-9.pdf")
- 11:17, 15 February 2023 LLL algorithm (Integer Relation Integer Relation) (hist | edit) [399 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{4})$ == Space Complexity == $O(n^{2})$ words (Derived: Uses n auxiliary vectors each of length n, as well as an nxn matrix) == Description == Lattice-based == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1982 == Reference == https://www.math.leidenuniv.nl/~hwl/PUBLICATIONS/1982f/art.pdf")
- 11:17, 15 February 2023 Ferguson–Forcade algorithm (Integer Relation Integer Relation) (hist | edit) [388 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$ words (Derived: Uses auxiliary $n\times n$ matrices) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1979 == Reference == https://www.ams.org/journals/bull/1979-01-06/S0273-0979-1979-14691-3/S0273-0979-1979-14691-3.pdf")
- 11:17, 15 February 2023 Bareiss algorithm with fast multiplication (Determinant of Matrices with Integer Entries Determinant of Matrices with Integer Entries) (hist | edit) [413 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{4}L(log(n)$ + L)log(log(n) + L)) == Space Complexity == $O(n^{2}(n*log(n)$+nL)) bits (Keeps track of $O(n^2)$ entries that have absolute value at most $O(n^{(n/2)}2^{(nL)})$) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? (without O(1) multiplication) == Year == 1968 == Reference == -")
- 11:17, 15 February 2023 Bareiss algorithm (Determinant of Matrices with Integer Entries Determinant of Matrices with Integer Entries) (hist | edit) [507 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{5}L^{2} (log(n)$^{2} + L^{2})) == Space Complexity == $O(n^{2}(n*log(n)$+nL)) bits (Keeps track of $O(n^2)$ entries that have absolute value at most $O(n^{(n/2)}2^{(nL)})$) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? (without O(1) multiplication) == Year == 1968 == Reference == https://www.ams.org/journals/mcom/1968-22-103/S0025-5718-1968-0226829-0...")