New pages
Jump to navigation
Jump to search
(newest | oldest) View (newer 250 | older 250) (20 | 50 | 100 | 250 | 500)
- 12:17, 15 February 2023 Clock (Online Page Replacements) (hist | edit) [304 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nk)$? == Space Complexity == $O(k)$ words (Need to keep track of cache + reference bits only (plus iterator)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 12:17, 15 February 2023 First-in, first-out (Online Page Replacements) (hist | edit) [288 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nk)$? == Space Complexity == $O(k)$ words (Need to keep track of cache + reference bits only) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 12:17, 15 February 2023 Second-chance (Online Page Replacements) (hist | edit) [288 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nk)$? == Space Complexity == $O(k)$ words (Need to keep track of cache + reference bits only) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 12:17, 15 February 2023 Least recently used (Online Page Replacements) (hist | edit) [325 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nk)$? == Space Complexity == $O(k)$ words (Need to keep track of cache + info related to time last referenced for each of k pages) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 12:17, 15 February 2023 Not recently used (Online Page Replacements) (hist | edit) [288 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nk)$? == Space Complexity == $O(k)$ words (Need to keep track of cache + reference bits only) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 12:17, 15 February 2023 Banker's Algorithm (Deadlock Avoidance Deadlock avoidance) (hist | edit) [444 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn^{2})$ == Space Complexity == $O(mn)$ words (Main space-consuming arrays needed include "Max," "Allocation," and "Need," which are all n*m arrays. Other arrays are either O(n) or O(m)-sized) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1966 == Reference == https://www.cs.utexas.edu/users/EWD/ewd01xx/EWD108.PDF")
- 12:17, 15 February 2023 Round-robin scheduling (Unweighted Interval Scheduling, Online?? Interval Scheduling) (hist | edit) [250 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n+k)$? words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 12:17, 15 February 2023 The theoretically optimal page replacement algorithm (Offline Page Replacements) (hist | edit) [370 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(k)$ words (Need to keep track of cache; linear scan for searching for page not being used for the longest only requires O(1) auxiliary space) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 12:17, 15 February 2023 Multilevel queue scheduling (Unweighted Interval Scheduling, Online?? Interval Scheduling) (hist | edit) [288 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n+k)$? words (^see above; also level information for each task) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 12:17, 15 February 2023 Work-conserving schedulers (Unweighted Interval Scheduling, Online?? Interval Scheduling) (hist | edit) [231 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 == 1940 == Reference ==")
- 12:17, 15 February 2023 Fixed priority shortest job first (Unweighted Interval Scheduling, Online?? Interval Scheduling) (hist | edit) [391 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n+k)$? words (Keep track of (sorted, based on criteria) list of (unscheduled, running, etc.; just un-done) tasks, along with machine statuses and task priorities) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 12:17, 15 February 2023 First come, first served (Unweighted Interval Scheduling, Online?? Interval Scheduling) (hist | edit) [250 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n+k)$? words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 12:17, 15 February 2023 Priority scheduling (Unweighted Interval Scheduling, Online?? Interval Scheduling) (hist | edit) [367 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n+k)$? words (Keep track of (sorted, based on criteria) list of (unscheduled, running, etc.; just un-done) tasks, along with machine statuses) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 12:17, 15 February 2023 $O(n^2)$ Dynamic Programming (Weighted Activity Selection Problem Interval Scheduling) (hist | edit) [320 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words (Keep track of answers to O(n) subproblems (cache), and sorted list of intervals) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1953 == Reference ==")
- 12:17, 15 February 2023 $O(n\log n)$ Dynamic Programming (Weighted Activity Selection Problem Interval Scheduling) (hist | edit) [323 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (Keep track of answers to O(n) subproblems (cache), and sorted list of intervals) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1953 == Reference ==")
- 12:17, 15 February 2023 Shortest remaining time first (Unweighted Interval Scheduling, Online?? Interval Scheduling) (hist | edit) [250 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n+k)$? words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 12:17, 15 February 2023 Sthele, Zimmermann (Greatest Common Divisor Greatest Common Divisor) (hist | edit) [389 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n log^{2} n log log n)$ == Space Complexity == $O(n)$?? bits (Depends on Schonhage-Strassen multiplication) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? words size O(1) == Year == 2006 == Reference == https://hal.inria.fr/file/index/docid/71533/filename/RR-5050.pdf")
- 12:17, 15 February 2023 Euclid's algorithm (Greatest Common Divisor Greatest Common Divisor) (hist | edit) [304 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ bits (Store only the current values being iterated on) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? words size O(1) == Year == -300 == Reference ==")
- 12:17, 15 February 2023 Lehmer's GCD algorithm (Greatest Common Divisor Greatest Common Divisor) (hist | edit) [352 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ bits (Store only the current values being iterated on, and an O(1)-sized matrix with O(n)-bit numbers) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? words size O(1) == Year == 1940 == Reference ==")
- 12:17, 15 February 2023 $O(n^3)$ Dynamic Programming (Weighted Activity Selection Problem Interval Scheduling) (hist | edit) [295 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$ words (Keep track of answers to O(n^2) subproblems (i, j)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1953 == Reference ==")
- 12:17, 15 February 2023 Brute force algorithm (Weighted Activity Selection Problem Interval Scheduling) (hist | edit) [292 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O(n)$ words (Need to keep track of which subset is being checked) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 12:17, 15 February 2023 Binary GCD algorithm (Greatest Common Divisor Greatest Common Divisor) (hist | edit) [338 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ bits (Store only the current values being iterated on) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? words size O(1) == Year == 1967 == Reference == https://arxiv.org/abs/0910.0095")
- 12:17, 15 February 2023 Higham (2-D Polynomial Interpolation Polynomial Interpolation) (hist | edit) [379 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words (https://academic.oup.com/imajna/article/8/4/473/758789?login=true) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1988 == Reference == https://academic.oup.com/imajna/article/8/4/473/758789?login=true")
- 12:17, 15 February 2023 Calvetti, Reichel (2-D Polynomial Interpolation Polynomial Interpolation) (hist | edit) [349 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$? words ((maybe similar to the other O(n^2) algorithms?)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1993 == Reference == https://link.springer.com/article/10.1007/BF01990529")
- 12:17, 15 February 2023 Bjorck (2-D Polynomial Interpolation Polynomial Interpolation) (hist | edit) [399 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words (https://academic.oup.com/imajna/article/8/4/473/758789?login=true) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1970 == Reference == https://www.jstor.org/stable/2004623?origin=crossref&seq=5#metadata_info_tab_contents")
- 12:17, 15 February 2023 Rijndael / AES (Block Ciphers Block Ciphers) (hist | edit) [529 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$? bits (Network generally operates on the O(n) bits over O(k) rounds, each round having roughly the same structure (so structure of rounds require O(1) bits to describe)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2001 == Reference == https://csrc.nist.gov/csrc/media/projects/cryptographic-standards-and-guid...")
- 12:17, 15 February 2023 Gaussian elimination (2-D Polynomial Interpolation Polynomial Interpolation) (hist | edit) [316 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$ words (Requires computation of inverse of O(n^2)-sized Vandermonde matrix) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == -150 == Reference ==")
- 12:17, 15 February 2023 Blowfish (Block Ciphers Block Ciphers) (hist | edit) [416 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$? bits (Network has a constant number of rounds and operates on O(n) bits, thus structure should require O(n) bits to describe) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1993 == Reference == https://link.springer.com/chapter/10.1007/3-540-58108-1_24")
- 12:17, 15 February 2023 RC5 (Block Ciphers Block Ciphers) (hist | edit) [465 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(k+rw)$? bits (Requires additional O(k/w)-length array of O(w)-size words (temporary working array) and O(r)-length array of O(w)-size words, as key-independent pseudorandom array.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1994 == Reference == https://link.springer.com/chapter/10.1007/3-540-60590-8_7")
- 12:17, 15 February 2023 Newton's method (Solutions to Nonlinear Equations Solutions to Nonlinear Equations) (hist | edit) [422 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_max)$ == Space Complexity == $O({1})$ words (Store current estimate x_i and the derivative f' (assuming this takes O(1) space); iterations take O(1) time and thus O(1) space, and space can be re-used across iterations) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1669 == Reference ==")
- 12:17, 15 February 2023 Lucifer / DES (Block Ciphers Block Ciphers) (hist | edit) [360 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$? bits (Network has a constant number of rounds and operates on O(n) bits, thus structure should require O(n) bits to describe) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == NA")
- 12:17, 15 February 2023 IDEA (Block Ciphers Block Ciphers) (hist | edit) [254 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$? bits ((^see above)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1991 == Reference == NA")
- 12:17, 15 February 2023 Regula Falsi method (Solutions to Nonlinear Equations Solutions to Nonlinear Equations) (hist | edit) [370 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_max)$ == Space Complexity == $O({1})$ words (Store current endpoint values; iterations take O(1) time and thus O(1) space, and space can be re-used across iterations) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == -200 == Reference ==")
- 12:17, 15 February 2023 Secant method (Solutions to Nonlinear Equations Solutions to Nonlinear Equations) (hist | edit) [384 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_max)$ == Space Complexity == $O({1})$ words (Store previous 2 estimates x_i and x_{i-1}; iterations take O(1) time and thus O(1) space, and space can be re-used across iterations) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == -1400 == Reference ==")
- 12:17, 15 February 2023 Bisection method (Solutions to Nonlinear Equations Solutions to Nonlinear Equations) (hist | edit) [370 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_max)$ == Space Complexity == $O({1})$ words (Store current endpoint values; iterations take O(1) time and thus O(1) space, and space can be re-used across iterations) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == -150 == Reference ==")
- 12:17, 15 February 2023 SHA-3 (Unkeyed Hash Functions One-Way Hash Functions) (hist | edit) [463 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(b+d)$ auxiliary? bits (only need constant padding, O(b)-bit "absorb" state being manipulated, constant-sized non-linear functions (i.e. operating on O(1) bits), and O(d)-sized "squeezed" state being manipulated. In practice b, d are O(1)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2015 == Reference ==")
- 12:17, 15 February 2023 SHA-2 (Unkeyed Hash Functions One-Way Hash Functions) (hist | edit) [299 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary? bits (Based off of Merkel-Damgard construction (see MD5)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2001 == Reference ==")
- 12:17, 15 February 2023 Shamir's scheme ( Secret Sharing) (hist | edit) [481 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(t^{2})$ for secret computation? (requires polynomial interpolation) == Space Complexity == $O({1})$ per person, $O(t^{2})$ to figure out secret? words (Each person only needs to keep track of a single point (O(1) info); figuring out secret depends on polynomial interpolation algorithm) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1979 == Refere...")
- 12:17, 15 February 2023 Blakley's scheme ( Secret Sharing) (hist | edit) [466 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(t^{3})$ for secret computation? (requires linear solver) == Space Complexity == $O(t)$ per person, $O(t^{2})$ to figure out secret words (Each person needs to keep track of coefficients of hyperplane; figuring out secret requires O(t) hyperplanes, with O(t) coefficients) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1979 == Reference ==")
- 12:17, 15 February 2023 BLAKE2 (Optional Key? One-Way Hash Functions) (hist | edit) [374 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary? bits (Generally processes the message in O(1)-sized chunks; parameters into the "compress" function are also technically O(1)-sized) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2012 == Reference ==")
- 12:17, 15 February 2023 Whirlpool ( One-Way Hash Functions) (hist | edit) [299 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary? bits (Based off of Merkel-Damgard construction (see MD5)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2000 == Reference ==")
- 12:17, 15 February 2023 SHA-1 (Unkeyed Hash Functions One-Way Hash Functions) (hist | edit) [299 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary? bits (Based off of Merkel-Damgard construction (see MD5)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1993 == Reference ==")
- 12:17, 15 February 2023 RIPEMD-160 (Unkeyed Hash Functions One-Way Hash Functions) (hist | edit) [306 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary? bits (Likely based off of Merkel-Damgard construction (see MD5)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1996 == Reference ==")
- 12:17, 15 February 2023 Bcrypt (Unkeyed Hash Functions One-Way Hash Functions) (hist | edit) [287 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary?? bits (generally operates in the O(1) scheme) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1999 == Reference ==")
- 12:17, 15 February 2023 MD5 (Unkeyed Hash Functions One-Way Hash Functions) (hist | edit) [426 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary? bits (only need constant padding, 128-bit state being manipulated, and constant-sized non-linear functions (i.e. operating on O(1) bits). Also based off of Merkle-Damgard construction) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1991 == Reference ==")
- 12:17, 15 February 2023 Naive Implementation ( Integral Equations) (hist | edit) [222 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1800 == Reference ==")
- 12: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 ==")
- 12: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")
- 12: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 ==")
- 12: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")
- 12: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")
- 12: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")
- 12: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")
- 12: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")
- 12: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 ==")
- 12: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 ==")
- 12: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 ==")
- 12: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 ==")
- 12: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 ==")
- 12: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")
- 12: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 ==")
- 12: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")
- 12: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")
- 12: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")
- 12: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")
- 12: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 ==")
- 12: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")
- 12: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 ==")
- 12: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")
- 12: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 ==")
- 12: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 ==")
- 12: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 ==")
- 12: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 ==")
- 12: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")
- 12: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 ==")
- 12: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")
- 12: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...")
- 12: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 ==...")
- 12: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")
- 12: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")
- 12: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")
- 12: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")
- 12: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")
- 12: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")
- 12: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...")
- 12: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")
- 12: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")
- 12: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")
- 12: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")
- 12: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...")
- 12: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")
- 12: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")
- 12: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")
- 12: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...")
- 12: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 == -")
- 12: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")
- 12:16, 15 February 2023 Ruchansky (Minimum Wiener Connector problem Wiener Index) (hist | edit) [452 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(q(m*log(n)$+n*log^{2}(n))) == Space Complexity == $O(q(m+n*log(n)$)? words (Keeps track of $O(qm)$ shortest-path distances and $O(q*log(n))$ approximate Steiner trees, each of size $O(n)$) == Description == == Approximate? == Approximate Approximation Factor: O(1) == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2015 == Reference == https://arxiv.org/abs/1504.00513")
- 12:16, 15 February 2023 Dunning; Gupta & Silberholz (Maximum Cut, Approximate Maximum Cut) (hist | edit) [297 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(VE)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2018 == Reference == https://pubsonline.informs.org/doi/epdf/10.1287/ijoc.2017.0798")
- 12:16, 15 February 2023 PINKALL U.; POLTHIER K 1993 (Mesh Parameterization Mesh Parameterization) (hist | edit) [274 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1993 == Reference == http://www.cs.jhu.edu/~misha/Fall09/Pinkall93.pdf")
- 12:16, 15 February 2023 LEE Y.; KIM H. S.; LEE S 2002 (Mesh Parameterization Mesh Parameterization) (hist | edit) [302 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n log^{3}n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2002 == Reference == https://www.sciencedirect.com/science/article/abs/pii/S0097849302001231")
- 12:16, 15 February 2023 FLOATER 1997 (Mesh Parameterization Mesh Parameterization) (hist | edit) [274 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1997 == Reference == http://www.cs.jhu.edu/~misha/Fall09/Floater97.pdf")
- 12:16, 15 February 2023 ECK M.; DEROSE T.; DUCHAMP T.; 1995 (Mesh Parameterization Mesh Parameterization) (hist | edit) [269 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1995 == Reference == https://dl.acm.org/doi/10.1145/218380.218440")
- 12:16, 15 February 2023 V. A. Lyul’ka and I. E. Mikhailov 2003 (Hyperbolic Spline Interpolation Hyperbolic Spline Interpolation) (hist | edit) [316 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{4})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2003 == Reference == http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=zvmmf&paperid=943&option_lang=eng")
- 12:16, 15 February 2023 V. I. Paasonen 1968 (Hyperbolic Spline Interpolation Hyperbolic Spline Interpolation) (hist | edit) [227 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{5} logK)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1968 == Reference ==")
- 12:16, 15 February 2023 P. Costantini; B. I. Kvasov; and C. Manni 1999 (Hyperbolic Spline Interpolation Hyperbolic Spline Interpolation) (hist | edit) [409 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{5} logK)$ == Space Complexity == $O(n)$? words (Derived: Pentadiagonal matrix in the linear system only requires O(n) space) == Description == Pentadiagonal linear system == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1999 == Reference == https://link.springer.com/article/10.1023/A:1018988312596")
- 12:16, 15 February 2023 B. I. Kvasov 2000 (Hyperbolic Spline Interpolation Hyperbolic Spline Interpolation) (hist | edit) [222 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{4})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2000 == Reference ==")
- 12:16, 15 February 2023 V. A. Lyul’ka and A. V. Romanenko 1994 (Hyperbolic Spline Interpolation Hyperbolic Spline Interpolation) (hist | edit) [261 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{5})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1994 == Reference == https://www.mathnet.ru/eng/zvmmf2544")
- 12:16, 15 February 2023 Kvasov 2006 (Hyperbolic Spline Interpolation Hyperbolic Spline Interpolation) (hist | edit) [293 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3} log^{2}K)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2008 == Reference == https://link.springer.com/article/10.1134/S0965542508040039")
- 12:16, 15 February 2023 Sorted Neighborhood Algorithm (SNA) (Duplicate Elimination Duplicate Elimination) (hist | edit) [362 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words (Derived: store a key for each entry in the "Create Key" phase) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1998 == Reference == https://link.springer.com/article/10.1023/A:1009761603038")
- 12:16, 15 February 2023 Adaptive Duplicate Detection Algorithm (ADD) (Duplicate Elimination Duplicate Elimination) (hist | edit) [384 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O({1})$ words (Derived: For SVM, only need to store a constant number of support vectors) == Description == SVM string similarity == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2003 == Reference == https://dl.acm.org/doi/10.1145/956750.956759")
- 12:16, 15 February 2023 Duplicate Elimination Sorted Neighborhood Algorithm (DE-SNA) (Duplicate Elimination Duplicate Elimination) (hist | edit) [225 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2002 == Reference ==")
- 12:16, 15 February 2023 Priority Queue Algorithm (Duplicate Elimination Duplicate Elimination) (hist | edit) [331 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words (Derived: Auxiliary space needed for the priority queue) == Description == Selection sort using priority queue? == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference ==")
- 12:16, 15 February 2023 Sorting based (Merge Sort) + real-time elimination (Duplicate Elimination Duplicate Elimination) (hist | edit) [225 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1964 == Reference ==")
- 12:16, 15 February 2023 BST Algorithm (Duplicate Elimination Duplicate Elimination) (hist | edit) [302 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(\log n)$ words (Derived: Space required for the recursion stack space) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1999 == Reference ==")
- 12:16, 15 February 2023 Sorting based (Merge Sort) (Duplicate Elimination Duplicate Elimination) (hist | edit) [279 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (Derived: linear space for mergesort) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1964 == Reference ==")
- 12:16, 15 February 2023 Berger & Müller-Hannemann (DAG Realization Problem Graph Realization Problems) (hist | edit) [272 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(\exp(n)$) == Space Complexity == ? words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2011 == Reference == https://arxiv.org/abs/1203.3636")
- 12:16, 15 February 2023 Muzychuk (Circulant graphs Graph Isomorphism Problem) (hist | edit) [341 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (derived in notes) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2004 == Reference == https://londmathsoc.onlinelibrary.wiley.com/doi/abs/10.1112/S0024611503014412")
- 12:16, 15 February 2023 Babai & Codenotti (Hypergraphs isomorphism Graph Isomorphism Problem) (hist | edit) [295 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $exp(O(k^{2} \sqrt{n})$ == Space Complexity == check words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2008 == Reference == https://oa.mg/work/10.1109/focs.2008.80")
- 12:16, 15 February 2023 Fulkerson–Chen–Anstee (Digraph Realization Problem Graph Realization Problems) (hist | edit) [841 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ words (Derived: Checking an inequality that involves 3 summations, of max value $O(n^2)$ each (assuming max degree $\leq n$) which is $O(1)$ words in our Word RAM. We check this inequality for each $k = 1, \ldots, n$, but you can store the summations dynamically, so you only need to run $O(1)$ operations per iteration) == Description == Makes use of (0,1) matrix properties, checks a property of the inp...")
- 12:16, 15 February 2023 Bodlaender (Partial k-trees Graph Isomorphism Problem) (hist | edit) [317 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{(k+{4.5})})$ == Space Complexity == check words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1990 == Reference == https://www.sciencedirect.com/science/article/pii/0196677490900135")
- 12:16, 15 February 2023 Kleitman–Wang Algorithm (Digraph Realization Problem Graph Realization Problems) (hist | edit) [425 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ words (Derived: Space complexity bounded by time complexity; keep track of a constant number of sets of size $O(n)$) == Description == Constructs graph == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1973 == Reference == https://linkinghub.elsevier.com/retrieve/pii/0012365X7390037X")
- 12:16, 15 February 2023 Schmidt & Druffel ( Graph Isomorphism Problem) (hist | edit) [307 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*n!)$ == Space Complexity == $O(n^{2})$ words (derived in sheet) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == https://dl.acm.org/doi/10.1145/321958.321963")
- 12:16, 15 February 2023 Ullman (Subgraph Isomorphism Graph Isomorphism Problem) (hist | edit) [259 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1976 == Reference == https://dl.acm.org/doi/10.1145/321921.321925")
- 12:16, 15 February 2023 Babai ( Graph Isomorphism Problem) (hist | edit) [342 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == {2}^{$O(\log n)$^3} == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2017 == Reference == http://people.cs.uchicago.edu/~laci/update.html, http://people.cs.uchicago.edu/~laci/17groups/version2.1.pdf")
- 12:16, 15 February 2023 Babai (Graph Isomorphism, Bounded Number of Vertices of Each Color Graph Isomorphism Problem) (hist | edit) [364 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == o(\exp({2}n^{1/2}\log^{2}n)) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1980 == Reference == https://epubs.siam.org/doi/10.1137/0209018")
- 12:16, 15 February 2023 McKay ( Graph Isomorphism Problem) (hist | edit) [338 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O((m1 + m2)n^{3} + m2 n^{2} L)$ == Space Complexity == ${2}mn+{10}n+m+(m+{4})K+{2}mL$ words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1981 == Reference == http://users.cecs.anu.edu.au/~bdm/papers/pgi.pdf")
- 12:16, 15 February 2023 Spielman (Isomorphism of strongly regular graphs Graph Isomorphism Problem) (hist | edit) [315 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $n^{O(n^{({1}/{3})} log n)}$ == Space Complexity == check words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1996 == Reference == https://www.cs.yale.edu/homes/spielman/PAPERS/srg.pdf")
- 12:16, 15 February 2023 Demand-Driven Register Allocation (Global Register Allocation Register Allocation) (hist | edit) [401 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (Derived: Requires storing a so-called $\Delta$-table of size $n \times n$ to keep track of $\Delta$-estimates) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1996 == Reference == https://dl.acm.org/doi/10.1145/236114.236117")
- 12:16, 15 February 2023 Sethi–Ullman Algorithm (Arithmetic Expression Binary Tree AST to Code Translation) (hist | edit) [368 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ words (Derived: Only uses in-situ updates to the input tree, no auxiliary data structures) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1970 == Reference == https://dl.acm.org/doi/10.1145/321607.321620")
- 12:16, 15 February 2023 Babai and Luks (Graph Isomorphism, General Graphs Graph Isomorphism Problem) (hist | edit) [349 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == \exp(n^{\frac{1}{2} + o({1})}) == Space Complexity == words () == Description == Construct canonical forms of graphs and compare == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1983 == Reference == https://dl.acm.org/doi/10.1145/800061.808746")
- 12:16, 15 February 2023 Dynamic Programming (Longest Palindromic Substring Longest Palindromic Substring) (hist | edit) [314 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (https://www.geeksforgeeks.org/longest-palindrome-substring-set-1/) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1953 == Reference == -")
- 12:16, 15 February 2023 Gusfield (Longest Palindromic Substring Longest Palindromic Substring) (hist | edit) [537 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ auxiliary words (At the very least it pre-processes and stores the string and the reverse of the string, requiring O(n) space. Space usage is bounded from above by runtime, so at most O(n) space is used.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1997 == Reference == https://www.cambridge.org/core/books/al...")
- 12:16, 15 February 2023 Jeuring (Longest Palindromic Substring Longest Palindromic Substring) (hist | edit) [377 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ auxiliary? words (Stores (and uses) previously computed palindrome information; unclear if O(n) is best bound possible) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1994 == Reference == https://doi.org/10.1007%2FBF01182773")
- 12:16, 15 February 2023 Manacher (Longest Palindromic Substring Longest Palindromic Substring) (hist | edit) [432 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ auxiliary words (At the very least it stores the radii for each center, requiring O(n) space. Space usage is bounded from above by runtime, so at most O(n) space is used.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1975 == Reference == https://doi.org/10.1145%2F321892.321896")
- 12:16, 15 February 2023 Record linking (Entity Resolution Entity Resolution) (hist | edit) [223 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2}k)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1993 == Reference ==")
- 12:16, 15 February 2023 Naive (Longest Palindromic Substring Longest Palindromic Substring) (hist | edit) [312 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O({1})$ auxiliary words (https://www.geeksforgeeks.org/longest-palindrome-substring-set-1/) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == -")
- 12:16, 15 February 2023 Ananthakrishna (Entity Resolution Entity Resolution) (hist | edit) [426 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} k)$ == Space Complexity == $O(n)$ words (Derived: the token table, the children table, and the tuples in G are stored in main memory, each are of size $O(n)$) == Description == Delphi algorithm == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2002 == Reference == https://doi.org/10.1016/B978-155860869-6/50058-5")
- 12:16, 15 February 2023 Ravikumar & Cohen Generative Models (Entity Resolution Entity Resolution) (hist | edit) [333 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} k)$ == Space Complexity == $O(k)$ words (Derived: One value per feature in the discretized vector) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2004 == Reference == https://arxiv.org/abs/1207.4180")
- 12:16, 15 February 2023 Chen Ensembles of classifiers (Entity Resolution Entity Resolution) (hist | edit) [242 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} logn)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1989 == Reference ==")
- 12:16, 15 February 2023 EM Based Winkler (Entity Resolution Entity Resolution) (hist | edit) [376 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3}k)$ == Space Complexity == $O(k)$ words (Derived: One value per feature in the discretized vector) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2000 == Reference == https://courses.cs.washington.edu/courses/cse590q/04au/papers/WinklerEM.pdf")
- 12:16, 15 February 2023 Bellare Active Learning (Entity Resolution Entity Resolution) (hist | edit) [327 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} logn clogc)$ == Space Complexity == () == Description == Pairwise ER Active Learning == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2012 == Reference == https://dl.acm.org/doi/10.1145/2339530.2339707")
- 12:16, 15 February 2023 McCreight (Constructing Suffix Trees Constructing Suffix Trees) (hist | edit) [376 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ words (Needs to store the intermediate steps of constructing a suffix tree, which can reach size O(n)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == http://libeccio.di.unisa.it/TdP/suffix.pdf")
- 12:16, 15 February 2023 Gupta & Sarawagi CRF (Entity Resolution Entity Resolution) (hist | edit) [428 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3}k)$ == Space Complexity == () == Description == Bipartite method to compute pairwise ER == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2009 == Reference == https://doi.org/10.14778/1687627.1687661")
- 12:16, 15 February 2023 Fellegi & Sunter Model (Entity Resolution Entity Resolution) (hist | edit) [450 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3}k)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1969 == Reference == https://www.tandfonline.com/doi/abs/10.1080/01621459.1969.10501049")
- 12:16, 15 February 2023 Rytter (Constructing Suffix Trees Constructing Suffix Trees) (hist | edit) [472 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(logn)$ == Space Complexity == $O(n)$ words (https://www.researchgate.net/publication/228945502_On_parallel_transformations_of_suffix_arrays_into_suffix_trees) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == CREW PRAM == Year == 2004 == Reference == https://www.researchgate.net/publication/228945502_On_parallel_transformations_of_suffix_arrays_into_suffix_trees")
- 12:16, 15 February 2023 Farach (Constructing Suffix Trees Constructing Suffix Trees) (hist | edit) [361 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(log n)$ == Space Complexity == $O(n)$ words (https://www.cs.rutgers.edu/~farach/pubs/PRAMSuffixICALP.pdf) == Description == == Approximate? == Exact == Randomized? == Yes, Las Vegas == Model of Computation == CRCW PRAM == Year == 1997 == Reference == https://www.cs.rutgers.edu/~farach/pubs/PRAMSuffixICALP.pdf")
- 12:16, 15 February 2023 Hariharan (Constructing Suffix Trees Constructing Suffix Trees) (hist | edit) [384 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(log^{4}(n)$) == Space Complexity == $O(n)$ words (https://www.sciencedirect.com/science/article/pii/S0022000097914963) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == CREW PRAM == Year == 1997 == Reference == https://www.sciencedirect.com/science/article/pii/S0022000097914963")
- 12:16, 15 February 2023 Süleyman Cenk Sahinalp ; Uzi Vishkin (Constructing Suffix Trees Constructing Suffix Trees) (hist | edit) [415 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(log^{2}(n)$) == Space Complexity == $O(n^{({1}+\eps)})$ for any fixed eps>{0} words (https://link.springer.com/content/pdf/10.1007/3-540-57811-0_3.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == CRCW PRAM == Year == 1994 == Reference == https://link.springer.com/content/pdf/10.1007/3-540-57811-0_3.pdf")
- 12:16, 15 February 2023 Pratt (Constructing Suffix Trees Constructing Suffix Trees) (hist | edit) [235 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 == 1973 == Reference == -")
- 12:16, 15 February 2023 Ukkonen (Constructing Suffix Trees Constructing Suffix Trees) (hist | edit) [391 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ words (Needs to store the intermediate steps of constructing a suffix tree, which can reach size O(n)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1995 == Reference == https://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf")
- 12:16, 15 February 2023 Ukkonen and D. Wood (Constructing Suffix Trees Constructing Suffix Trees) (hist | edit) [352 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (https://link.springer.com/article/10.1007/BF01769703) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1993 == Reference == https://link.springer.com/article/10.1007/BF01769703")
- 12:16, 15 February 2023 Ioannidou; Kyriaki; Mertzios; George B.; Nikolopoulos; Stavros D. (Longest Path on Interval Graphs Longest Path Problem) (hist | edit) [382 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{4})$ == Space Complexity == $O(n^{3})$ words (https://link.springer.com/content/pdf/10.1007/s00453-010-9411-3.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2011 == Reference == https://community.dur.ac.uk/george.mertzios/papers/Conf/Conf_Longest-Interval.pdf")
- 12:16, 15 February 2023 Weiner's algorithm (Constructing Suffix Trees Constructing Suffix Trees) (hist | edit) [376 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ words (Needs to store the intermediate steps of constructing a suffix tree, which can reach size O(n)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1973 == Reference == https://dl.acm.org/citation.cfm?id=1441766")
- 12:16, 15 February 2023 Naive (Constructing Suffix Trees Constructing Suffix Trees) (hist | edit) [339 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words (Needs to store the intermediate steps of constructing a suffix tree, which can reach size O(n)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1973 == Reference == -")
- 12:16, 15 February 2023 Gent; I.P.; Irving; R.W.; Manlove; D.F.; Prosser; P.; Smith; B.M. (Stable Marriage Problem Stable Matching Problem) (hist | edit) [372 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$? words (Constructs, preprocesses, and solves an O(n^2)-size CSP instance?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2001 == Reference == https://link.springer.com/chapter/10.1007/3-540-45578-7_16")
- 12:16, 15 February 2023 Patrick Posser (Stable Roommates Problem Stable Matching Problem) (hist | edit) [370 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n)$ words (https://link.springer.com/chapter/10.1007%2F978-3-319-07046-9_2) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2014 == Reference == https://link.springer.com/chapter/10.1007%2F978-3-319-07046-9_2")
- 12:16, 15 February 2023 Unsworth; C.; Prosser; P (Stable Marriage Problem Stable Matching Problem) (hist | edit) [409 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$? words (Constructs, preprocesses, and solves an $O(n^2)$-size CSP instance? (see original reference)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2005 == Reference == http://www.dcs.gla.ac.uk/~pat/roommates/distribution/papers/SM2N.pdf")
- 12:16, 15 February 2023 S. S. TSENG and R. C. T. LEE (Stable Marriage Problem Stable Matching Problem) (hist | edit) [377 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ per processor? words (Only need to keep track of current (provisional) matchings) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1984 == Reference == https://link.springer.com/content/pdf/10.1007/BF02136029.pdf")
- 12: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 == -")
- 12: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 ==")
- 12: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 ==")
- 12: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 ==")
- 12: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 ==")
- 12: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 ==")
- 12: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")
- 12: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 ==")
- 12: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 ==")
- 12: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 ==")
- 12: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 ==")
- 12: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 ==")
- 12: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 ==")
- 12: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")
- 12: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")
- 12: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")
- 12: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")
- 12: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")
- 12: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...")
- 12: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")
- 12: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")
- 12: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")
- 12: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")
- 12: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")
- 12: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")
- 12: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...")
- 12: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")
- 12: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")
- 12: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")
- 12: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")
- 12: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")
- 12: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")
- 12: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")
- 12: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")
- 12: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")
- 12: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")
- 12: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")
- 12: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")
- 12: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")
- 12: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-...")
- 12: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")
- 12: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")
- 12: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")
- 12: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")
- 12: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...")
- 12: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")
- 12: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")
- 12: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")
- 12:15, 15 February 2023 Naïve algorithm ( Variance Calculations) (hist | edit) [318 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary words (Maintain number of values, sum of values, and sum of squares of values) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1940 == Reference == -")
- 12: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")
- 12: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")
- 12:15, 15 February 2023 Two-pass algorithm ( Variance Calculations) (hist | edit) [336 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary words (Maintain number of values, sum of values, and sum of squares of (value minus mean) terms) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1940 == Reference == -")
- 12:15, 15 February 2023 Bowyer–Watson algorithm (Voronoi Diagrams Voronoi Diagrams) (hist | edit) [409 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ auxiliary words (Computes the Delaunay triangulation first (O(n) space), then uses that to generate the Voronoi diagram) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1981 == Reference == https://academic.oup.com/comjnl/article/24/2/167/338200")
- 12:15, 15 February 2023 Fortune's algorithm (Voronoi Diagrams Voronoi Diagrams) (hist | edit) [413 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ auxiliary words (https://www.wias-berlin.de/people/si/course/files/Fortune87-SweepLine-Voronoi.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1986 == Reference == http://www.wias-berlin.de/people/si/course/files/Fortune87-SweepLine-Voronoi.pdf")
- 12:15, 15 February 2023 Kong and Wilken Algorithm (Global Register Allocation Register Allocation) (hist | edit) [368 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == ? Probably also dependent on the ILP solver () == Description == Integer programming for irregular register architectures == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1998 == Reference == https://dl.acm.org/doi/10.5555/290940.291002")
- 12:15, 15 February 2023 Optimal Register Allocation (ORA), Goodwin & Wilken Algorithm (Global Register Allocation Register Allocation) (hist | edit) [478 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == Depends on the choice of {0}-{1} ILP solver ("Memory usage is dominated by the usage of the integer program solver.") == Description == 0-1 integer linear programming problem == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1996 == Reference == https://onlinelibrary.wiley.com/doi/abs/10.1002/%28SICI%291097-024X%28199608%2926%3A8%3C929%3A%3AA...")
- 12:15, 15 February 2023 Linde–Buzo–Gray algorithm ( Voronoi Diagrams) (hist | edit) [291 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1980 == Reference == https://ieeexplore.ieee.org/document/1094577/")
- 12:15, 15 February 2023 Chow's Algorithm (Global Register Allocation Register Allocation) (hist | edit) [479 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (Derived: this algorithm also uses a register interference graph (RIG)) == Description == Assumes all variables allocated in main memory (i.e. assumes no spill handling required). Priority-based RIG coloring == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1984 == Reference == https://dl.acm.org/doi/10.1145/502874.50...")
- 12:15, 15 February 2023 Chaitin's Algorithm (Global Register Allocation Register Allocation) (hist | edit) [432 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (Derived: this algorithm uses both an adjacency matrix (called the bit matrix) and adjacency lists (called the adjacency vectors)) == Description == RIG coloring == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1981 == Reference == https://dl.acm.org/doi/10.1145/872726.806984")
- 12:15, 15 February 2023 Cooper and Dasgupta algorithm ( Register Allocation) (hist | edit) [222 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1983 == Reference ==")
- 12:15, 15 February 2023 Linear Scan, Poletto & Sarkar (Global Register Allocation Register Allocation) (hist | edit) [471 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(r)$ words (Derived: given the live ranges, the only auxiliary data structure is an "active" list that contains the active live ranges and this has length at most $r$) == Description == Greedy assignment == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1999 == Reference == http://web.cs.ucla.edu/~palsberg/course/cs132/linearscan.pdf")
- 12:15, 15 February 2023 Bottom-m sketches streaming algorithm (streaming Cardinality Estimation) (hist | edit) [339 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(N)$ == Space Complexity == $O(m)$ words (only keep track of m minimum values. also assuming hash function requires O(1) space) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM == Year == 1980 == Reference ==")
- 12:15, 15 February 2023 Min/max sketches streaming algorithm (streaming Cardinality Estimation) (hist | edit) [338 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(N)$ == Space Complexity == $O({1})$ words (only keep track of minimum value. also assuming hash function requires O(1) space) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM == Year == 1980 == Reference ==")
- 12:15, 15 February 2023 LogLog algorithm ( Cardinality Estimation) (hist | edit) [384 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(N)$ == Space Complexity == $O(log(log(n)$)) words (http://algo.inria.fr/flajolet/Publications/DuFl03-LNCS.pdf) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM == Year == 2003 == Reference == http://algo.inria.fr/flajolet/Publications/DuFl03-LNCS.pdf")
- 12:15, 15 February 2023 Flajolet–Martin algorithm ( Cardinality Estimation) (hist | edit) [386 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(N)$ == Space Complexity == $O(log n)$ words (https://www.sciencedirect.com/science/article/pii/S0022000097915452) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM == Year == 1984 == Reference == http://algo.inria.fr/flajolet/Publications/src/FlMa85.pdf")
- 12:15, 15 February 2023 HyperLogLog++ ( Cardinality Estimation) (hist | edit) [392 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(N)$ == Space Complexity == $O(eps^{-2}*log(log(n)$))+log(n)) words ((see hyperloglog?)) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM == Year == 2014 == Reference == https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/40671.pdf")
- 12:15, 15 February 2023 HyperLogLog algorithm ( Cardinality Estimation) (hist | edit) [417 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(N)$ == Space Complexity == $O(eps^{-2}*log(log(n)$))+log(n)) words (https://oertl.github.io/hyperloglog-sketch-estimation-paper/paper/paper.pdf) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM == Year == 2007 == Reference == http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf")
- 12:15, 15 February 2023 Generalized expectation maximization (GEM) algorithm ( Maximum Likelihood Parameters) (hist | edit) [485 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{4} log^{0.{1}.5}n)$ == Space Complexity == $O(n+r)$? words (Stores current theta and Z guesses, which is updated each iteration. Also assumes description of log-likelihood takes O(n+r) auxiliary space.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1994 == Reference == https://web.eecs.umich.edu/~fessler/papers/files/jour/94/web/fessler-94-...")
- 12:15, 15 February 2023 Α-EM algorithm ( Maximum Likelihood Parameters) (hist | edit) [440 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n+r)$? words (Stores current theta and Z guesses, which is updated each iteration. Also assumes description of alpha-log-likelihood takes O(n+r) auxiliary space.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 2003 == Reference == https://dl.acm.org/doi/10.1109/TIT.2002.808105")
- 12:15, 15 February 2023 Naive solution ( Cardinality Estimation) (hist | edit) [302 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(N)$ == Space Complexity == $O(n)$ words (keep track of exact histogram, may require storing all values) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == -")
- 12:15, 15 February 2023 Expectation conditional maximization (ECM) ( Maximum Likelihood Parameters) (hist | edit) [427 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} logn)$ == Space Complexity == $O(n+r)$? words (Stores current theta and Z guesses, which is updated each iteration. Also assumes description of log-likelihood takes O(n+r) auxiliary space.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 2017 == Reference == https://arxiv.org/abs/1709.06970")
- 12:15, 15 February 2023 Parameter-expanded expectation maximization (PX-EM) algorithm ( Maximum Likelihood Parameters) (hist | edit) [434 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n+r)$? words (Stores current theta (+ alpha) and Z guesses, which is updated each iteration. Also assumes description of log-likelihood takes O(n+r) auxiliary space.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1998 == Reference == https://www.jstor.org/stable/2337481")
- 12:15, 15 February 2023 Newton–Raphson algorithm ( Maximum Likelihood Parameters) (hist | edit) [450 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n+r^{2})$? words (Stores current theta guess, which is updated each iteration, and requires computation of the (inverse of the) Hessian matrix. Also assumes description of log-likelihood takes O(n+r) auxiliary space.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1685 == Reference == -")
- 12:15, 15 February 2023 Expectation–maximization (EM) algorithm ( Maximum Likelihood Parameters) (hist | edit) [424 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n+r)$? words (Stores current theta and Z guesses, which is updated each iteration. Also assumes description of log-likelihood takes O(n+r) auxiliary space.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1977 == Reference == https://www.jstor.org/stable/2984875")
- 12:15, 15 February 2023 Haselgrove; Leech and Trotter (Bounded Subgroup Index Coset Enumeration) (hist | edit) [387 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O(ng)$? words (Implementation stores a table whose number of required registers is the product of the number of generators (n) and the number of cosets (O(g))) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1940 == Reference ==")
- 12:15, 15 February 2023 Knuth–Bendix algorithm (General Groups (uncompleted?) Coset Enumeration) (hist | edit) [462 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({1.5}^n n^{2} logn)$ == Space Complexity == $O(ng)$??? words (Can store a table whose number of required registers is the product of the number of generators (n) and the number of cosets (O(g))) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1970 == Reference == https://www.cs.tufts.edu/~nr/cs257/archive/don-knuth/knuth-bendix.pdf")
- 12:15, 15 February 2023 Todd–Coxeter algorithm (Bounded Subgroup Index Coset Enumeration) (hist | edit) [501 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O(gkc)$ words (Defines O(k) tables, each with O(g) columns and O(c) rows) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1936 == Reference == https://www.cambridge.org/core/journals/proceedings-of-the-edinburgh-mathematical-society/article/practical-method-for-enumerating-cosets-of-a-finite-abstract-group/030657...")
- 12:15, 15 February 2023 Muller's method (General Root Computation Root Computation) (hist | edit) [479 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_{max})$ == Space Complexity == $O({1})$ words (Store previous 3 estimates x_i, x_{i-1}, and x_{i-2}; iterations take O(1) time and thus O(1) space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1956 == Reference == https://www.jstor.org/stable/200...")
- 12:15, 15 February 2023 Secant method (General Root Computation Root Computation) (hist | edit) [434 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_{max})$ == Space Complexity == $O({1})$ words (Store previous 2 estimates x_i and x_{i-1}; iterations take O(1) time and thus O(1) space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1940 == Reference == -")
- 12:15, 15 February 2023 Ridder's method (General Root Computation Root Computation) (hist | edit) [478 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_{max})$ == Space Complexity == $O({1})$ words (Store previous 2 estimates x_i and x_{i-1}; iterations take O(1) time and thus O(1) space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1979 == Reference == https://ieeexplore.ieee.org/document/1084580/")
- 12:15, 15 February 2023 Halley's method (Root Computation with continuous second derivative Root Computation) (hist | edit) [482 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_{max})$ == Space Complexity == $O({1})$ words (Store current estimate x_i and the derivatives f' and f'' (assuming this takes O(1) space); iterations take O(1) time and thus O(1) space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1940 == Reference...")
- 12:15, 15 February 2023 Newton's method (Root Computation with continuous first derivative Root Computation) (hist | edit) [479 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_{max})$ == Space Complexity == $O({1})$ words (Store current estimate $x_i$ and the derivative $f'$ (assuming this takes $O(1)$ space); iterations take $O(1)$ time and thus $O(1)$ space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1940 == Referenc...")
- 12:15, 15 February 2023 Bisection method (General Root Computation Root Computation) (hist | edit) [425 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_{max})$ == Space Complexity == $O({1})$ words (Store current endpoint values; iterations take $O(1)$ time and thus $O(1)$ space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1820 == Reference == -")
- 12:15, 15 February 2023 MRRR algorithm (Any eigenpair; Any eigenvalue Eigenvalues (Iterative Methods)) (hist | edit) [426 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n^{2})$ words (Need to compute and store some matrix of the form $(A-mu*I)^{(-1)}$ (for inverse iteration-like uses)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1999 == Reference == https://www.cs.utexas.edu/users/inderjit/public_papers/DesignMRRR_toms06.pdf")
- 12:15, 15 February 2023 False position method (General Root Computation Root Computation) (hist | edit) [425 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_{max})$ == Space Complexity == $O({1})$ words (Store current endpoint values; iterations take $O(1)$ time and thus $O(1)$ space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1690 == Reference == -")
- 12:15, 15 February 2023 Divide-and-conquer (All eigenvalues; Any eigenvalue Eigenvalues (Iterative Methods)) (hist | edit) [411 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n^{2})$ words (Stores reduction to tridiagonal form; recursion (S(n)=2S(n/2)+O(n^2)) should work out to O(n^2)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1986 == Reference == https://link.springer.com/content/pdf/10.1007/BF01389480.pdf")
- 12:15, 15 February 2023 Folded spectrum method (Eigenpair closest to mu; Any eigenpair; Any eigenvalue Eigenvalues (Iterative Methods)) (hist | edit) [438 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$? words (Requires only a constant number of O(n)-sized vectors per iteration; matrix-to-vector multiplication only requires O(n) aux space) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1934 == Reference == https://journals.aps.org/pr/abstract/10.1103/PhysRev.46.828")
- 12:15, 15 February 2023 Homotopy method (All eigenpairs; Eigenpair closest to mu; Any eigenpair; Any eigenvalue; All eigenvalues Eigenvalues (Iterative Methods)) (hist | edit) [403 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$?? words (Conservative bound on space used per iteration) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1992 == Reference == https://www.scirp.org/(S(czeh2tfqyw2orz553k1w0r45))/reference/ReferencesPapers.aspx?ReferenceID=530065")
- 12:15, 15 February 2023 Bisection method (Any eigenvalue Eigenvalues (Iterative Methods)) (hist | edit) [424 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$? words (Computing characteristic polynomial takes $O(n^2)$ space (via e.g. Faddeev–LeVerrier algorithm); rest of algo can be done in $O(n)$ space (related to root computation)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1985 == Reference == -")
- 12:15, 15 February 2023 QR algorithm (All eigenvalues; Any eigenvalue Eigenvalues (Iterative Methods)) (hist | edit) [361 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (Computes and stores QR factorization at each iteration) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1962 == Reference == https://academic.oup.com/comjnl/article/4/4/332/432033")
- 12:15, 15 February 2023 Laguerre iteration (Any eigenvalue Eigenvalues (Iterative Methods)) (hist | edit) [266 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$? words (^ see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1940 == Reference == -")
- 12:15, 15 February 2023 Jacobi eigenvalue algorithm (All eigenvalues; Any eigenvalue Eigenvalues (Iterative Methods)) (hist | edit) [355 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$? words (Computes and stores results of GSG^T iterations) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1846 == Reference == https://gdz.sub.uni-goettingen.de/id/PPN243919689_0030")