User contributions for Admin

15 February 2023

• 11:1711:17, 15 February 2023 diff hist +465‎ N RC5 (Block Ciphers Block Ciphers) ‎ 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" current
• 11:1711:17, 15 February 2023 diff hist +254‎ N IDEA (Block Ciphers Block Ciphers) ‎ 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" current
• 11:1711:17, 15 February 2023 diff hist +360‎ N Lucifer / DES (Block Ciphers Block Ciphers) ‎ 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" current
• 11:1711:17, 15 February 2023 diff hist +420‎ N Newton's method (Solutions to Nonlinear Equations Solutions to Nonlinear Equations) ‎ 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 =="
• 11:1711:17, 15 February 2023 diff hist +382‎ N Secant method (Solutions to Nonlinear Equations Solutions to Nonlinear Equations) ‎ 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 =="
• 11:1711:17, 15 February 2023 diff hist +368‎ N Regula Falsi method (Solutions to Nonlinear Equations Solutions to Nonlinear Equations) ‎ 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 =="
• 11:1711:17, 15 February 2023 diff hist +368‎ N Bisection method (Solutions to Nonlinear Equations Solutions to Nonlinear Equations) ‎ 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 =="
• 11:1711:17, 15 February 2023 diff hist +481‎ N Shamir's scheme ( Secret Sharing) ‎ 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..." current
• 11:1711:17, 15 February 2023 diff hist +466‎ N Blakley's scheme ( Secret Sharing) ‎ 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 ==" current
• 11:1711:17, 15 February 2023 diff hist +374‎ N BLAKE2 (Optional Key? One-Way Hash Functions) ‎ 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 ==" current
• 11:1711:17, 15 February 2023 diff hist +299‎ N SHA-2 (Unkeyed Hash Functions One-Way Hash Functions) ‎ 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 ==" current
• 11:1711:17, 15 February 2023 diff hist +463‎ N SHA-3 (Unkeyed Hash Functions One-Way Hash Functions) ‎ 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 ==" current
• 11:1711:17, 15 February 2023 diff hist +299‎ N Whirlpool ( One-Way Hash Functions) ‎ 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 ==" current
• 11:1711:17, 15 February 2023 diff hist +306‎ N RIPEMD-160 (Unkeyed Hash Functions One-Way Hash Functions) ‎ 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 ==" current
• 11:1711:17, 15 February 2023 diff hist +287‎ N Bcrypt (Unkeyed Hash Functions One-Way Hash Functions) ‎ 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 ==" current
• 11:1711:17, 15 February 2023 diff hist +299‎ N SHA-1 (Unkeyed Hash Functions One-Way Hash Functions) ‎ 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 ==" current
• 11:1711:17, 15 February 2023 diff hist +426‎ N MD5 (Unkeyed Hash Functions One-Way Hash Functions) ‎ 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 ==" current
• 11:1711:17, 15 February 2023 diff hist +222‎ N Naive Implementation ( Integral Equations) ‎ Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1800 == Reference ==" current
• 11:1711:17, 15 February 2023 diff hist +316‎ N Rabin Karp (The Frequent Words Problem The Frequent Words Problem) ‎ Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(max(n, sigma^k)$) auxiliary? words (Keep track of counts on at most n-k+1 or sigma^k words) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1987 == Reference =="
• 11:1711:17, 15 February 2023 diff hist +315‎ N Naive solution (The Frequent Words Problem The Frequent Words Problem) ‎ Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(max(n, sigma^k)$) auxiliary words (Keep track of counts on at most n-k+1 or sigma^k words) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference =="
• 11:1711:17, 15 February 2023 diff hist +317‎ N Hanoi graph (Tower of Hanoi Tower of Hanoi) ‎ 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" current
• 11:1711:17, 15 February 2023 diff hist +308‎ N Gray-code based (Tower of Hanoi Tower of Hanoi) ‎ Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O(n)$ auxiliary bits (Need to keep track of an n-bit counter for Gray codes) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == NA"
• 11:1711:17, 15 February 2023 diff hist +303‎ N Non-recursion based (Tower of Hanoi Tower of Hanoi) ‎ Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O(n)$ auxiliary bits (Only need to keep track of current configuration) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == NA"
• 11:1711:17, 15 February 2023 diff hist +387‎ N Recursion based (Tower of Hanoi Tower of Hanoi) ‎ Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O(n*log n)$ auxiliary bits (Need to keep track of an O(n)-sized recursive stack, each entry requiring O(log n) space (i.e. which tower size to manipulate)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == NA"
• 11:1711:17, 15 February 2023 diff hist +303‎ N Iteration based (Tower of Hanoi Tower of Hanoi) ‎ Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O(n)$ auxiliary bits (Only need to keep track of current configuration) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1883 == Reference == NA"
• 11:1711:17, 15 February 2023 diff hist +456‎ N Naive solution ( Frequent Words with Mismatches Problem) ‎ 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 ==" current
• 11:1711:17, 15 February 2023 diff hist +362‎ N Rivin, Zabih (Counting Solutions n-Queens Problem) ‎ 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" current
• 11:1711:17, 15 February 2023 diff hist +394‎ N Naive Solution (Median String Problem with Unbounded Alphabets Median String Problem) ‎ Created page with "== Time Complexity == {2}^$O(n)$ == Space Complexity == $O(n)$ auxiliary words (Keep track of current string being checked, current best string, and Levenshtein distances (which can be computed recursively using O(n) space)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1965 == Reference =="
• 11:1711:17, 15 February 2023 diff hist +381‎ N Gunther Determinants solution (Counting Solutions; Constructing solutions n-Queens Problem) ‎ 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 ==" current
• 11:1711:17, 15 February 2023 diff hist +232‎ N Nauck (Counting Solutions; Constructing solutions n-Queens Problem) ‎ Created page with "== Time Complexity == $O(n!)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1850 == Reference ==" current
• 11:1711:17, 15 February 2023 diff hist +408‎ N Dijkstra (Counting Solutions; Constructing solutions n-Queens Problem) ‎ 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" current
• 11:1711:17, 15 February 2023 diff hist +312‎ N Naive + 1 queen per row restriction (Counting Solutions; Constructing solutions n-Queens Problem) ‎ 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 ==" current
• 11:1711:17, 15 February 2023 diff hist +313‎ N Naive Algorithm (Counting Solutions; Constructing solutions n-Queens Problem) ‎ 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 ==" current
• 11:1711:17, 15 February 2023 diff hist +330‎ N Outside-In algorithm (Turnpike Problem Turnpike Problem) ‎ 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" current
• 11:1711:17, 15 February 2023 diff hist +433‎ N Gries, Martin (Transitive Reduction Problem of Directed Graphs Transitive Reduction Problem) ‎ 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" current
• 11:1711:17, 15 February 2023 diff hist 0‎ Aho, Garey & Ullman (Transitive Reduction Problem of Directed Graphs Transitive Reduction Problem) ‎No edit summary Tag: Reverted
• 11:1711:17, 15 February 2023 diff hist +1‎ Aho, Garey & Ullman (Transitive Reduction Problem of Directed Graphs Transitive Reduction Problem) ‎No edit summary Tag: Reverted
• 11:1711:17, 15 February 2023 diff hist −1‎ Aho, Garey & Ullman (Transitive Reduction Problem of Directed Graphs Transitive Reduction Problem) ‎No edit summary Tag: Reverted
• 11:1711:17, 15 February 2023 diff hist 0‎ Aho, Garey & Ullman (Transitive Reduction Problem of Directed Graphs Transitive Reduction Problem) ‎No edit summary Tag: Reverted
• 11:1711:17, 15 February 2023 diff hist +1‎ Aho, Garey & Ullman (Transitive Reduction Problem of Directed Graphs Transitive Reduction Problem) ‎No edit summary Tag: Reverted
• 11:1711:17, 15 February 2023 diff hist 0‎ Aho, Garey & Ullman (Transitive Reduction Problem of Directed Graphs Transitive Reduction Problem) ‎No edit summary Tag: Reverted
• 11:1711:17, 15 February 2023 diff hist +1‎ Aho, Garey & Ullman (Transitive Reduction Problem of Directed Graphs Transitive Reduction Problem) ‎No edit summary
• 11:1711:17, 15 February 2023 diff hist −61‎ Aho, Garey & Ullman (Transitive Reduction Problem of Directed Graphs Transitive Reduction Problem) ‎No edit summary
• 11:1711:17, 15 February 2023 diff hist +392‎ N Aho, Garey & Ullman (Transitive Reduction Problem of Directed Graphs Transitive Reduction Problem) ‎ Created page with "== Time Complexity == $O(n^omega)$ where omega is the exponent on boolean matrix multiplication == Space Complexity == $O(n^{2})$ words (see (boolean) matrix multiplication) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1972 == Reference == https://epubs.siam.org/doi/pdf/10.1137/0201008"
• 11:1711:17, 15 February 2023 diff hist +400‎ N Guibas, Sedgewick Red-Black Tree ( Self-Balancing Trees Search) ‎ Created page with "== Time Complexity == $O(logn)$ == Space Complexity == $O({1})$ words (Need to keep track of constant amount of info during search (i.e. which node we're on and what direction to go)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1972 == Reference == https://ieeexplore.ieee.org/document/4567957"
• 11:1711:17, 15 February 2023 diff hist +353‎ N Hopcroft 2-3 Tree ( Self-Balancing Trees Search) ‎ Created page with "== Time Complexity == $O(logn)$ == Space Complexity == $O({1})$ words (Need to keep track of constant amount of info during search (i.e. which node we're on and what direction to go)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1970 == Reference =="
• 11:1711:17, 15 February 2023 diff hist +299‎ N Guibas, Sedgewick Red-Black Tree ( Self-Balancing Trees Deletion) ‎ Created page with "== Time Complexity == $O(logn)$ == Space Complexity == $O({1})$ words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1972 == Reference == https://ieeexplore.ieee.org/document/4567957"
• 11:1711:17, 15 February 2023 diff hist +252‎ N Hopcroft 2-3 Tree ( Self-Balancing Trees Deletion) ‎ Created page with "== Time Complexity == $O(logn)$ == Space Complexity == $O({1})$ words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1970 == Reference =="
• 11:1711:17, 15 February 2023 diff hist +299‎ N Guibas, Sedgewick Red-Black Tree ( Self-Balancing Trees Insertion) ‎ Created page with "== Time Complexity == $O(logn)$ == Space Complexity == $O({1})$ words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1972 == Reference == https://ieeexplore.ieee.org/document/4567957"
• 11:1711:17, 15 February 2023 diff hist +359‎ N Hopcroft 2-3 Tree ( Self-Balancing Trees Insertion) ‎ 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 =="