All public logs

Combined display of all available logs of Algorithm Wiki. You can narrow down the view by selecting a log type, the username (case-sensitive), or the affected page (also case-sensitive).

(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)

• 11:17, 15 February 2023 Admin talk contribs created page Not recently used (Online Page Replacements) (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 ==")
• 11:17, 15 February 2023 Admin talk contribs created page The theoretically optimal page replacement algorithm (Offline Page Replacements) (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 ==")
• 11:17, 15 February 2023 Admin talk contribs created page Banker's Algorithm (Deadlock Avoidance Deadlock avoidance) (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")
• 11:17, 15 February 2023 Admin talk contribs created page Multilevel queue scheduling (Unweighted Interval Scheduling, Online?? Interval Scheduling) (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 ==")
• 11:17, 15 February 2023 Admin talk contribs created page Work-conserving schedulers (Unweighted Interval Scheduling, Online?? Interval Scheduling) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
• 11:17, 15 February 2023 Admin talk contribs created page Round-robin scheduling (Unweighted Interval Scheduling, Online?? Interval Scheduling) (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 ==")
• 11:17, 15 February 2023 Admin talk contribs created page First come, first served (Unweighted Interval Scheduling, Online?? Interval Scheduling) (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 ==")
• 11:17, 15 February 2023 Admin talk contribs created page Shortest remaining time first (Unweighted Interval Scheduling, Online?? Interval Scheduling) (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 ==")
• 11:17, 15 February 2023 Admin talk contribs created page Priority scheduling (Unweighted Interval Scheduling, Online?? Interval Scheduling) (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 ==")
• 11:17, 15 February 2023 Admin talk contribs created page $O(n\log n)$ Dynamic Programming (Weighted Activity Selection Problem Interval Scheduling) (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 ==")
• 11:17, 15 February 2023 Admin talk contribs created page $O(n^2)$ Dynamic Programming (Weighted Activity Selection Problem Interval Scheduling) (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 ==")
• 11:17, 15 February 2023 Admin talk contribs created page Fixed priority shortest job first (Unweighted Interval Scheduling, Online?? Interval Scheduling) (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 ==")
• 11:17, 15 February 2023 Admin talk contribs created page $O(n^3)$ Dynamic Programming (Weighted Activity Selection Problem Interval Scheduling) (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 ==")
• 11:17, 15 February 2023 Admin talk contribs created page Brute force algorithm (Weighted Activity Selection Problem Interval Scheduling) (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 ==")
• 11:17, 15 February 2023 Admin talk contribs created page Sthele, Zimmermann (Greatest Common Divisor Greatest Common Divisor) (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")
• 11:17, 15 February 2023 Admin talk contribs created page Binary GCD algorithm (Greatest Common Divisor Greatest Common Divisor) (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")
• 11:17, 15 February 2023 Admin talk contribs created page Euclid's algorithm (Greatest Common Divisor Greatest Common Divisor) (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 ==")
• 11:17, 15 February 2023 Admin talk contribs created page Lehmer's GCD algorithm (Greatest Common Divisor Greatest Common Divisor) (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 ==")
• 11:17, 15 February 2023 Admin talk contribs created page Calvetti, Reichel (2-D Polynomial Interpolation Polynomial Interpolation) (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")
• 11:17, 15 February 2023 Admin talk contribs created page Bjorck (2-D Polynomial Interpolation Polynomial Interpolation) (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")
• 11:17, 15 February 2023 Admin talk contribs created page Higham (2-D Polynomial Interpolation Polynomial Interpolation) (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")
• 11:17, 15 February 2023 Admin talk contribs created page Gaussian elimination (2-D Polynomial Interpolation Polynomial Interpolation) (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 ==")
• 11:17, 15 February 2023 Admin talk contribs created page Rijndael / AES (Block Ciphers Block Ciphers) (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...")
• 11:17, 15 February 2023 Admin talk contribs created page Blowfish (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 == 1993 == Reference == https://link.springer.com/chapter/10.1007/3-540-58108-1_24")
• 11:17, 15 February 2023 Admin talk contribs created page 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")
• 11:17, 15 February 2023 Admin talk contribs created page 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")
• 11:17, 15 February 2023 Admin talk contribs created page 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")
• 11:17, 15 February 2023 Admin talk contribs created page 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:17, 15 February 2023 Admin talk contribs created page 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:17, 15 February 2023 Admin talk contribs created page 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:17, 15 February 2023 Admin talk contribs created page 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:17, 15 February 2023 Admin talk contribs created page 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...")
• 11:17, 15 February 2023 Admin talk contribs created page 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 ==")
• 11:17, 15 February 2023 Admin talk contribs created page 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 ==")
• 11:17, 15 February 2023 Admin talk contribs created page 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 ==")
• 11:17, 15 February 2023 Admin talk contribs created page 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 ==")
• 11:17, 15 February 2023 Admin talk contribs created page 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 ==")
• 11:17, 15 February 2023 Admin talk contribs created page 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 ==")
• 11:17, 15 February 2023 Admin talk contribs created page 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 ==")
• 11:17, 15 February 2023 Admin talk contribs created page 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 ==")
• 11:17, 15 February 2023 Admin talk contribs created page 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 ==")
• 11:17, 15 February 2023 Admin talk contribs created page 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 ==")
• 11:17, 15 February 2023 Admin talk contribs created page 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:17, 15 February 2023 Admin talk contribs created page 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:17, 15 February 2023 Admin talk contribs created page 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")
• 11:17, 15 February 2023 Admin talk contribs created page 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:17, 15 February 2023 Admin talk contribs created page 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:17, 15 February 2023 Admin talk contribs created page 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:17, 15 February 2023 Admin talk contribs created page 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:17, 15 February 2023 Admin talk contribs created page 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 ==")

(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)