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:18, 15 February 2023 Admin talk contribs created page Steffensen's method (General Root Computation Root Computation) (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 Admin talk contribs created page Householder's Method (Root Computation with continuous derivatives (up to d) Root Computation) (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 Admin talk contribs created page Illinois Algorithm (General Root Computation Root Computation) (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/article/10.1007/BF01934364")
• 11:18, 15 February 2023 Admin talk contribs created page Anderson–Björck algorithm (General Root Computation Root Computation) (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/article/10.1007/BF01951936")
• 11:18, 15 February 2023 Admin talk contribs created page ITP Method (General Root Computation Root Computation) (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 Admin talk contribs created page Gabow, Galil, Spencer (general Maximum-weight matching) (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/abstract/document/715935")
• 11:18, 15 February 2023 Admin talk contribs created page Galil, Micali, Gabow (general Maximum-weight matching) (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/docview/919855909?pq-origsite=gscholar&fromopenview=true")
• 11:18, 15 February 2023 Admin talk contribs created page Gabow (general Maximum-weight matching) (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/docview/287948024?pq-origsite=gscholar&fromopenview=true")
• 11:18, 15 February 2023 Admin talk contribs created page Johnson (Edmonds-Karp-based) (bipartite (i.e. assignment), general Maximum-weight matching) (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/science/article/pii/0020019075900010")
• 11:18, 15 February 2023 Admin talk contribs created page Edmonds-Karp (bipartite (i.e. assignment), general Maximum-weight matching) (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 Admin talk contribs created page Fredman-Tarjan (Edmonds-Karp-based) (bipartite (i.e. assignment), general Maximum-weight matching) (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/doi/10.1145/28869.28874")
• 11:18, 15 February 2023 Admin talk contribs created page Zaks' prefix reversal algorithm ( All permutations) (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/content/pdf/10.1007/BF01937486.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1984 == Reference == https://link.springer.com/article/10.1007/BF01937486")
• 11:18, 15 February 2023 Admin talk contribs created page Ives' algorithm c ( All permutations) (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/doi/abs/10.1145/359997.360002")
• 11:18, 15 February 2023 Admin talk contribs created page Ord-Smith ( All permutations) (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/doi/pdf/10.1145/362896.362913")
• 11:18, 15 February 2023 Admin talk contribs created page Langdon ( All permutations) (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/doi/pdf/10.1145/363282.363315")
• 11:18, 15 February 2023 Admin talk contribs created page Wells ( All permutations) (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/stable/2004229#metadata_info_tab_contents")
• 11:18, 15 February 2023 Admin talk contribs created page Divide and Conquer ( Minimum value in each row of an implicitly-defined totally monotone matrix) (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/article/10.1007/BF01840359")
• 11:18, 15 February 2023 Admin talk contribs created page Micali, Vazirani (general graph Maximum cardinality matching) (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/document/4567800")
• 11:18, 15 February 2023 Admin talk contribs created page Blossom Algorithm (general graph Maximum cardinality matching) (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/core/journals/canadian-journal-of-mathematics/article/paths-trees-and-flowers/08B492B72...")
• 11:18, 15 February 2023 Admin talk contribs created page Alt, Blum, Mehlhorn, Paul (bipartite graph Maximum cardinality matching) (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/science/article/pii/002001909190195N")
• 11:18, 15 February 2023 Admin talk contribs created page Masek, Paterson (Edit sequence, constant-size alphabet Sequence Alignment) (Created page with "== Time Complexity == $O(mn/log(n)$) == Space Complexity == $O(mn/log(n)$) words (https://www.sciencedirect.com/science/article/pii/0022000080900021?via%3Dihub) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1980 == Reference == https://www.sciencedirect.com/science/article/pii/0022000080900021?via%3Dihub")
• 11:18, 15 February 2023 Admin talk contribs created page Wagner-Fischer algorithm (Edit sequence, constant-size alphabet Sequence Alignment) (Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(mn)$ words (https://dl.acm.org/doi/10.1145/360825.360861) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1974 == Reference == https://dl.acm.org/doi/abs/10.1145/321796.321811")
• 11:18, 15 February 2023 Admin talk contribs created page Wagner-Fischer algorithm (Edit distance, constant-size alphabet Sequence Alignment) (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/doi/abs/10.1145/321796.321811")
• 11:18, 15 February 2023 Admin talk contribs created page Wu and Manber, Fuzzy String Matching ( String Search) (Created page with "== Time Complexity == $O(nk \lceil m/w \rceil)$ == Space Complexity == $O(ms + k \lceil m/w \rceil)$ (https://dl.acm.org/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/doi/pdf/10.1145/135239.135244")
• 11:18, 15 February 2023 Admin talk contribs created page Focused D* ( Informed Search) (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 Admin talk contribs created page D* Lite ( Informed Search) (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/10.1109%2Ftro.2004.838026")
• 11:18, 15 February 2023 Admin talk contribs created page Shi 2009 (NAE 3SAT Boolean Satisfiability) (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/stamp/stamp.jsp?tp=&arnumber=5211463) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Adelman-Lipton == Year == 2009 == Reference == https://ieeexplore.ieee.org/abstract/document/52...")
• 11:18, 15 February 2023 Admin talk contribs created page Anytime Dynamic A* (ADA*) ( Informed Search) (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 Admin talk contribs created page Hertli (Modified PPSZ) (4SAT Boolean Satisfiability) (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/doi/abs/10.1137/120868177")
• 11:18, 15 February 2023 Admin talk contribs created page Hertli (Modified PPSZ) (3SAT Boolean Satisfiability) (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/doi/abs/10.1137/120868177")
• 11:18, 15 February 2023 Admin talk contribs created page Paturi, Pudlák, Saks, Zane (PPSZ) 2005 (k-SAT Boolean Satisfiability) (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/doi/abs/10.1145/1066100.1066101")
• 11:18, 15 February 2023 Admin talk contribs created page Lewis 1978 (Renamable Horn Boolean Satisfiability) (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/doi/10.1145/322047.322059")
• 11:18, 15 February 2023 Admin talk contribs created page Quantum Adiabatic Algorithm (QAA) (CNF-SAT Boolean Satisfiability) (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 Admin talk contribs created page WalkSAT (CNF-SAT Boolean Satisfiability) (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 Admin talk contribs created page GSAT (CNF-SAT Boolean Satisfiability) (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 Admin talk contribs created page Conflict-Driven Clause Learning (CDCL) (CNF-SAT Boolean Satisfiability) (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/document/769433")
• 11:17, 15 February 2023 Admin talk contribs created page Davis-Putnam-Logemann-Loveland Algorithm (DPLL) (CNF-SAT Boolean Satisfiability) (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/doi/10.1145/368273.368557")
• 11:17, 15 February 2023 Admin talk contribs created page Zwick 2002 (Directed, Unweighted All-Pairs Shortest Paths (APSP)) (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/doi/abs/10.1145/567112.567114")
• 11:17, 15 February 2023 Admin talk contribs created page Johnson's algorithm (Directed, Weighted (Arbitrary weights) All-Pairs Shortest Paths (APSP)) (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/doi/10.1145/321992.321993")
• 11:17, 15 February 2023 Admin talk contribs created page Binary representation search with matrix multiplication (Unweighted Graph Diameter) (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 Admin talk contribs created page Sparse APSP algorithm (Arbitrary edge weights, Sparse graph Graph Diameter) (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 Admin talk contribs created page Dense APSP algorithm (Arbitrary edge weights, Dense graph Graph Diameter) (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 Admin talk contribs created page Longest distance first (LDF) page replacement algorithm (Online Page Replacements) (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 Admin talk contribs created page ARIES (Steal, No-Force Recovery) (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 Admin talk contribs created page Not frequently used (NFU) (Online Page Replacements) (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 Admin talk contribs created page Aging (Online Page Replacements) (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 Admin talk contribs created page Random (Online Page Replacements) (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 Admin talk contribs created page Least recently used (Online Page Replacements) (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 Admin talk contribs created page Second-chance (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 Clock (Online Page Replacements) (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 ==")

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