New pages
Jump to navigation
Jump to search
(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)
- 11:18, 15 February 2023 Steffensen's method (General Root Computation Root Computation) (hist | edit) [416 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_max)$ == Space Complexity == $O({1})$ words (Store previous estimate x_i; 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 ==")
- 11:18, 15 February 2023 Householder's Method (Root Computation with continuous derivatives (up to d) Root Computation) (hist | edit) [497 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(d*n_max)$? == Space Complexity == $O(d)$ words (Store current estimate x_i and the derivatives f' through f^{(d)} (assuming these take O(1) space each); 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(?...")
- 11:18, 15 February 2023 ITP Method (General Root Computation Root Computation) (hist | edit) [437 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_0+log((b-a)$/epsilon)) == 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 == 1940? == Reference == -")
- 11:18, 15 February 2023 Anderson–Björck algorithm (General Root Computation Root Computation) (hist | edit) [470 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 == 1973 == Reference == https://link-springer-com.ezproxy.canberra.edu.au/article/10.1007/BF01951936")
- 11:18, 15 February 2023 Illinois Algorithm (General Root Computation Root Computation) (hist | edit) [470 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 == 1971 == Reference == https://link-springer-com.ezproxy.canberra.edu.au/article/10.1007/BF01934364")
- 11:18, 15 February 2023 Gabow, Galil, Spencer (general Maximum-weight matching) (hist | edit) [332 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn*log(log(log(n)$/log({2}+m/n))) + n^{2}*log(n)) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1989 == Reference == https://ieeexplore-ieee-org.ezproxy.canberra.edu.au/abstract/document/715935")
- 11:18, 15 February 2023 Galil, Micali, Gabow (general Maximum-weight matching) (hist | edit) [323 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn*log(n)$) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1982 == Reference == https://www-proquest-com.ezproxy.canberra.edu.au/docview/919855909?pq-origsite=gscholar&fromopenview=true")
- 11:18, 15 February 2023 Gabow (general Maximum-weight matching) (hist | edit) [341 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1974 == Reference == https://www-proquest-com.ezproxy.canberra.edu.au/docview/287948024?pq-origsite=gscholar&fromopenview=true")
- 11:18, 15 February 2023 Johnson (Edmonds-Karp-based) (bipartite (i.e. assignment), general Maximum-weight matching) (hist | edit) [341 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn*log(n)$/log({2}+m/n)) == Space Complexity == $O(n^{2})$ words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1975 == Reference == https://www-sciencedirect-com.ezproxy.canberra.edu.au/science/article/pii/0020019075900010")
- 11:18, 15 February 2023 Fredman-Tarjan (Edmonds-Karp-based) (bipartite (i.e. assignment), general Maximum-weight matching) (hist | edit) [309 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn+n^{2}log(n)$) == Space Complexity == $O(n^{2})$ words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1984 == Reference == https://dl-acm-org.ezproxy.canberra.edu.au/doi/10.1145/28869.28874")
- 11:18, 15 February 2023 Edmonds-Karp (bipartite (i.e. assignment), general Maximum-weight matching) (hist | edit) [581 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*(SP+))$ where $(SP+)$ denotes the time for one SSSP computation on a nonnegatively weighted graph. Initially $O(n^{3})$ == Space Complexity == $O(n^{2})$ words (Keeps track of current flow, which is of size O(n^2), and an O(n)-sized labeling function. SSSP computation has time bounded by O(n^2) and thus should use O(n^2) space at most) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Co...")
- 11:18, 15 February 2023 Zaks' prefix reversal algorithm ( All permutations) (hist | edit) [422 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ on specific permutations == Space Complexity == $O(n)$ auxiliary (see NEXT algorithm in same paper) words (https://link-springer-com.ezproxy.canberra.edu.au/content/pdf/10.1007/BF01937486.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1984 == Reference == https://link-springer-com.ezproxy.canberra.edu.au/article/10.1007/BF01937486")
- 11:18, 15 February 2023 Ives' algorithm c ( All permutations) (hist | edit) [392 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({1})$ per permutation == Space Complexity == $O(n)$ auxiliary words (O(n) words needed to keep track of which elements have cycled how many times) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == https://dl-acm-org.ezproxy.canberra.edu.au/doi/abs/10.1145/359997.360002")
- 11:18, 15 February 2023 Ord-Smith ( All permutations) (hist | edit) [358 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({1})$ per permutation == Space Complexity == $O(n)$ auxiliary words (O(n)-sized array q (as in paper) necessary) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1967 == Reference == https://dl-acm-org.ezproxy.canberra.edu.au/doi/pdf/10.1145/362896.362913")
- 11:18, 15 February 2023 Langdon ( All permutations) (hist | edit) [391 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ per permutation == Space Complexity == $O({1})$ auxiliary words (Only need the auxiliary variable N, according to the flowchart in the paper) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1967 == Reference == https://dl-acm-org.ezproxy.canberra.edu.au/doi/pdf/10.1145/363282.363315")
- 11:18, 15 February 2023 Wells ( All permutations) (hist | edit) [367 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({1})$ per permutation == Space Complexity == $O(n)$ auxiliary words (O(n)-sized array for t_k's necessary) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1961 == Reference == https://www-jstor-org.ezproxy.canberra.edu.au/stable/2004229#metadata_info_tab_contents")
- 11:18, 15 February 2023 Divide and Conquer ( Minimum value in each row of an implicitly-defined totally monotone matrix) (hist | edit) [402 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(m*log(n)$) == Space Complexity == $O(log(n)$) auxiliary? words (Need to keep track of the specific indices where the minimums occur, up to depth log(n)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1987 == Reference == https://link-springer-com.ezproxy.canberra.edu.au/article/10.1007/BF01840359")
- 11:18, 15 February 2023 Micali, Vazirani (general graph Maximum cardinality matching) (hist | edit) [409 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{0.5} E)$ == Space Complexity == $O(E)$ auxiliary? words (Manipulates a constant number of graphs? Contractions can be kept track of in O(E) space) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM == Year == 1980 == Reference == https://ieeexplore-ieee-org.ezproxy.canberra.edu.au/document/4567800")
- 11:18, 15 February 2023 Blossom Algorithm (general graph Maximum cardinality matching) (hist | edit) [498 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{2}E)$ == Space Complexity == $O(E)$ auxiliary? words (Manipulates a constant number of graphs? Contractions can be kept track of in O(E) space) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM == Year == 1961 == Reference == https://www-cambridge-org.ezproxy.canberra.edu.au/core/journals/canadian-journal-of-mathematics/article/paths-trees-and-flowers/08B492B72...")
- 11:18, 15 February 2023 Alt, Blum, Mehlhorn, Paul (bipartite graph Maximum cardinality matching) (hist | edit) [433 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{1.5}*(E/logV)$^{0.5}) == Space Complexity == $O(E)$ auxiliary? words (Uses constant number of O(E)-sized data structures in pseudocode of algorithm) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM == Year == 1991 == Reference == https://www-sciencedirect-com.ezproxy.canberra.edu.au/science/article/pii/002001909190195N")
- 11:18, 15 February 2023 Masek, Paterson (Edit sequence, constant-size alphabet Sequence Alignment) (hist | edit) [410 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn/log(n)$) == Space Complexity == $O(mn/log(n)$) words (https://www-sciencedirect-com.ezproxy.canberra.edu.au/science/article/pii/0022000080900021?via%3Dihub) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1980 == Reference == https://www-sciencedirect-com.ezproxy.canberra.edu.au/science/article/pii/0022000080900021?via%3Dihub")
- 11:18, 15 February 2023 Wagner-Fischer algorithm (Edit sequence, constant-size alphabet Sequence Alignment) (hist | edit) [334 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(mn)$ words (https://dl-acm-org.ezproxy.canberra.edu.au/doi/10.1145/360825.360861) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1974 == Reference == https://dl-acm-org.ezproxy.canberra.edu.au/doi/abs/10.1145/321796.321811")
- 11:18, 15 February 2023 Wagner-Fischer algorithm (Edit distance, constant-size alphabet Sequence Alignment) (hist | edit) [303 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(m)$ words (Easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1974 == Reference == https://dl-acm-org.ezproxy.canberra.edu.au/doi/abs/10.1145/321796.321811")
- 11:18, 15 February 2023 Wu and Manber, Fuzzy String Matching ( String Search) (hist | edit) [433 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nk \lceil m/w \rceil)$ == Space Complexity == $O(ms + k \lceil m/w \rceil)$ (https://dl-acm-org.ezproxy.canberra.edu.au/doi/pdf/10.1145/135239.135244) == Description == == Approximate? == Approximate Approximation Factor: Levensthein Distance = k == Randomized? == No, deterministic == Model of Computation == not mentioned == Year == 1992 == Reference == https://dl-acm-org.ezproxy.canberra.edu.au/doi/pdf/10.1145/135239.135244")
- 11:18, 15 February 2023 Focused D* ( Informed Search) (hist | edit) [331 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(b^d)$ == Space Complexity == $O(b^d)$ (Stores all generated nodes in memory) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2005 == Reference == https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.8257")
- 11:18, 15 February 2023 D* Lite ( Informed Search) (hist | edit) [308 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(b^d)$ == Space Complexity == $O(b^d)$ (Stores all generated nodes in memory) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2005 == Reference == https://doi-org.ezproxy.canberra.edu.au/10.1109%2Ftro.2004.838026")
- 11:18, 15 February 2023 Anytime Dynamic A* (ADA*) ( Informed Search) (hist | edit) [353 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(b^d)$ == Space Complexity == $O(b^d)$ (Stores all generated nodes in memory) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2005 == Reference == https://www.ri.cmu.edu/publications/anytime-dynamic-a-an-anytime-replanning-algorithm/")
- 11:18, 15 February 2023 Shi 2009 (NAE 3SAT Boolean Satisfiability) (hist | edit) [480 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({12}m*t_extract + {2}m*t_discard + {2}n*t_append + (n+{2}m)$*t_merge + (n-{1})*t_amplify) == Space Complexity == $O(n)$ tubes or $O({2}^n)$ library strands (https://ieeexplore-ieee-org.ezproxy.canberra.edu.au/stamp/stamp.jsp?tp=&arnumber=5211463) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Adelman-Lipton == Year == 2009 == Reference == https://ieeexplore-ieee-org.ezproxy.canberra.edu.au/abstract/document/52...")
- 11:18, 15 February 2023 Hertli (Modified PPSZ) (4SAT Boolean Satisfiability) (hist | edit) [319 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({1.46899}^n)$ == Space Complexity == $O(kn)$ words (Not sure, please look) == Description == == Approximate? == Exact == Randomized? == Yes, Monte Carlo == Model of Computation == Word RAM == Year == 2014 == Reference == https://epubs-siam-org.ezproxy.canberra.edu.au/doi/abs/10.1137/120868177")
- 11:18, 15 February 2023 Hertli (Modified PPSZ) (3SAT Boolean Satisfiability) (hist | edit) [319 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({1.30704}^n)$ == Space Complexity == $O(kn)$ words (Not sure, please look) == Description == == Approximate? == Exact == Randomized? == Yes, Monte Carlo == Model of Computation == Word RAM == Year == 2014 == Reference == https://epubs-siam-org.ezproxy.canberra.edu.au/doi/abs/10.1137/120868177")
- 11:18, 15 February 2023 Paturi, Pudlák, Saks, Zane (PPSZ) 2005 (k-SAT Boolean Satisfiability) (hist | edit) [317 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == O^*({2}^{n-cn/k}) == Space Complexity == $O(kn)$ words (Derived in notes) == Description == == Approximate? == Exact == Randomized? == Yes, Monte Carlo == Model of Computation == Word RAM == Year == 2005 == Reference == https://dl-acm-org.ezproxy.canberra.edu.au/doi/abs/10.1145/1066100.1066101")
- 11:18, 15 February 2023 Lewis 1978 (Renamable Horn Boolean Satisfiability) (hist | edit) [270 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn^{2})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1978 == Reference == https://dl-acm-org.ezproxy.canberra.edu.au/doi/10.1145/322047.322059")
- 11:18, 15 February 2023 Quantum Adiabatic Algorithm (QAA) (CNF-SAT Boolean Satisfiability) (hist | edit) [310 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O(poly(n)$) qubits () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Quantum == Year == 2001 == Reference == https://arxiv.org/pdf/quant-ph/0001106.pdf")
- 11:17, 15 February 2023 WalkSAT (CNF-SAT Boolean Satisfiability) (hist | edit) [316 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*mt*mf)$ == Space Complexity == $O(n)$ (same as above) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == == Year == 1994 == Reference == https://www.aaai.org/Papers/AAAI/1994/AAAI94-051.pdf")
- 11:17, 15 February 2023 GSAT (CNF-SAT Boolean Satisfiability) (hist | edit) [327 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*mt*mf)$ == Space Complexity == $O(n)$ (derived in notes) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == == Year == 1992 == Reference == http://www.cs.cornell.edu/selman/papers/pdf/92.aaai.gsat.pdf")
- 11:17, 15 February 2023 Conflict-Driven Clause Learning (CDCL) (CNF-SAT Boolean Satisfiability) (hist | edit) [268 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1999 == Reference == https://ieeexplore-ieee-org.ezproxy.canberra.edu.au/document/769433")
- 11:17, 15 February 2023 Davis-Putnam-Logemann-Loveland Algorithm (DPLL) (CNF-SAT Boolean Satisfiability) (hist | edit) [337 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O(n)$ Binary Search Tree (https://en.wikipedia.org/wiki/DPLL_algorithm) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1961 == Reference == https://dl-acm-org.ezproxy.canberra.edu.au/doi/10.1145/368273.368557")
- 11:17, 15 February 2023 Zwick 2002 (Directed, Unweighted All-Pairs Shortest Paths (APSP)) (hist | edit) [277 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{2.575})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2002 == Reference == https://dl-acm-org.ezproxy.canberra.edu.au/doi/abs/10.1145/567112.567114")
- 11:17, 15 February 2023 Johnson's algorithm (Directed, Weighted (Arbitrary weights) All-Pairs Shortest Paths (APSP)) (hist | edit) [298 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{2} log V + VE)$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == == Year == 1977 == Reference == https://dl-acm-org.ezproxy.canberra.edu.au/doi/10.1145/321992.321993")
- 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.ezproxy.canberra.edu.au/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 ==")