New pages
Jump to navigation
Jump to search
(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)
- 11:17, 15 February 2023 Binary representation search with matrix multiplication (Unweighted Graph Diameter) (hist | edit) [337 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^omega log(V)$) where omega is the exponent on matrix multiplication == Space Complexity == $O(V^{2} logV)$ words (storing all the matrices) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == - == Reference == -")
- 11:17, 15 February 2023 Dense APSP algorithm (Arbitrary edge weights, Dense graph Graph Diameter) (hist | edit) [255 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{3} / {2}^(logV)$^{0.5}) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == - == Reference == -")
- 11:17, 15 February 2023 Sparse APSP algorithm (Arbitrary edge weights, Sparse graph Graph Diameter) (hist | edit) [243 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{2}logV+VE)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == - == Reference == -")
- 11:17, 15 February 2023 Longest distance first (LDF) page replacement algorithm (Online Page Replacements) (hist | edit) [539 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nk)$? == Space Complexity == $O(k)$ words (Need to keep track of cache + information related to position of pages) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2017 == Reference == https://www.researchgate.net/profile/Gyanendra-Kumar-3/publication/319467661_A_Novel_Longest_Distance_First_Page_Replacement_Algorithm/links/59b209f1aca2728472d146...")
- 11:17, 15 February 2023 ARIES (Steal, No-Force Recovery) (hist | edit) [470 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$? words (Uses write-ahead logging, so keeps track of transaction log, whose entries may be augmented with O(1) more information each. During recovery, needs to keep track of variable/page states) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1992 == Reference == https://dl.acm.org/doi/10.1145/128765.128770")
- 11:17, 15 February 2023 Not frequently used (NFU) (Online Page Replacements) (hist | edit) [292 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nk)$? == Space Complexity == $O(k)$ words (Need to keep track of cache + reference counters only) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 11:17, 15 February 2023 Aging (Online Page Replacements) (hist | edit) [292 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nk)$? == Space Complexity == $O(k)$ words (Need to keep track of cache + reference counters only) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 11:17, 15 February 2023 Random (Online Page Replacements) (hist | edit) [254 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(k)$? words (Need to keep track of cache?) == Description == == Approximate? == Exact == Randomized? == Yes, == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 11: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 ==")
- 11: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 ==")
- 11: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 ==")
- 11: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 ==")
- 11: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 ==")
- 11: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 ==")
- 11: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")
- 11: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 ==")
- 11: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 ==")
- 11: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 ==")
- 11: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 ==")
- 11: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 ==")
- 11: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 ==")
- 11: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 ==")
- 11: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 ==")
- 11: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 ==")
- 11: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 ==")
- 11: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 ==")
- 11: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")
- 11: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")
- 11: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 ==")
- 11: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 ==")
- 11: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")
- 11: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")
- 11: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")
- 11: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 ==")
- 11: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...")
- 11: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")
- 11: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")
- 11: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")
- 11: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")
- 11: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 ==")
- 11: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 ==")
- 11: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 ==")
- 11: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 ==")
- 11: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 ==")
- 11: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...")
- 11: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 ==")
- 11: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 ==")
- 11: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 ==")
- 11: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 ==")
- 11: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 ==")