New pages
Jump to navigation
Jump to search
(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)
- 10:53, 15 February 2023 Hentenryck et. al. (Arc Consistency? Stable Matching Problem) (hist | edit) [389 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{3})$? words (https://www.sciencedirect.com/science/article/abs/pii/000437029290020X) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1992 == Reference == https://www.sciencedirect.com/science/article/abs/pii/000437029290020X")
- 10:53, 15 February 2023 Manlove; Malley (Stable Marriage Problem Stable Matching Problem) (hist | edit) [362 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$? words (Constructs, preprocesses, and solves an $O(n^2)$-size CSP instance?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2005 == Reference == http://www.dcs.gla.ac.uk/~davidm/pubs/7981.pdf")
- 10:53, 15 February 2023 Irving's Algorithm (Stable Roommates Problem Stable Matching Problem) (hist | edit) [377 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$? words (Manipulates the $O(n)$-many $O(n)$-size preference lists) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1985 == Reference == http://www.dcs.gla.ac.uk/~pat/jchoco/roommates/papers/Comp_sdarticle.pdf")
- 10:53, 15 February 2023 Gale–Shapley algorithm (Stable Marriage Problem Stable Matching Problem) (hist | edit) [374 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words (Only need to keep track of current (provisional) matchings) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1962 == Reference == http://www.eecs.harvard.edu/cs286r/courses/fall09/papers/galeshapley.pdf")
- 10:53, 15 February 2023 Berlekamp–Massey algorithm (Cryptanalysis of Linear Feedback Shift Registers Cryptanalysis of Linear Feedback Shift Registers) (hist | edit) [356 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(N)$? words (Computes and stores constant number of polynomials of degree $O(N)$) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1969 == Reference == https://ieeexplore.ieee.org/document/1054260")
- 10:53, 15 February 2023 Victor Shoup's algorithm (Equal-degree Factorization of Polynomials Over Finite Fields) (hist | edit) [517 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words (Keeps track of a set of factors, where sum of degrees of factors is $O(n)$ so the total number of terms to keep track of is $O(n)$. Also, polynomials in the separating set can be computed in $O(n)$ space) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1990 == Reference == https://www.sciencedirect.co...")
- 10:53, 15 February 2023 Cantor–Zassenhaus algorithm (Equal-degree Factorization of Polynomials Over Finite Fields) (hist | edit) [523 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3} logn)$ == Space Complexity == $O(n)$ words (Keeps track of a set of factors, where sum of degrees of factors is O(n) so the total number of terms to keep track of is O(n). Also, computing h^{((q^d-1)/2)}-1 mod f only requires O(n) space) == Description == == Approximate? == Exact == Randomized? == Yes, Monte Carlo == Model of Computation == Word RAM == Year == 1981 == Reference == https://www.ams.org/journals/mcom/1...")
- 10:53, 15 February 2023 Distinct-degree factorization (Distinct-degree Factorization of Polynomials Over Finite Fields) (hist | edit) [420 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3} + nlogn)$ == Space Complexity == $O(n)$ words (Computes and stores a constant number of polynomials of degree $O(n)$ per iteration. Note that computing $gcd(f, x^{(q^i)}-x)$ can be cleverly done in $O(n)$ space.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1944 == Reference == -")
- 10:53, 15 February 2023 Schubert's algorithm ( Factorization of Polynomials Over Finite Fields) (hist | edit) [245 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n)$ words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == -")
- 10:53, 15 February 2023 Square-free factorization (Square-free Factorization of Polynomials Over Finite Fields) (hist | edit) [328 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n)$ words (Computes and stores a constant number of polynomials of degree $O(n)$ per iteration) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1975 == Reference == -")
- 10:53, 15 February 2023 Berlekamp's algorithm (Distinct-degree; Equal-degree Factorization of Polynomials Over Finite Fields) (hist | edit) [394 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3} logn)$ == Space Complexity == $O(n)$ words (Computes the remainder of $g^{((p-1)/2)}-1 mod f$ (in order to find gcd of $g^{((p-1)/2)}-1$ and f)) == Description == == Approximate? == Exact == Randomized? == Yes, Monte Carlo == Model of Computation == Word RAM == Year == 1967 == Reference == https://ieeexplore.ieee.org/document/6768643/")
- 10:53, 15 February 2023 Korada and R. Urbanke; (Lossy Compression Data Compression) (hist | edit) [347 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*{2}^n)$ == Space Complexity == $O(N)$ words (Derived: size of the polar codes that need to be stored) == Description == Polar codes == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2010 == Reference == https://arxiv.org/pdf/0903.0307.pdf")
- 10:53, 15 February 2023 Jalali; A. Montanari; and T. Weissman (Lossy Compression Data Compression) (hist | edit) [448 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2010 == Reference == https://authors.library.caltech.edu/17983/1/Jalali2010p7459Ieee_T_Inform_Theory.pdf")
- 10:53, 15 February 2023 Jalali and T. Weissman (Lossy Compression Data Compression) (hist | edit) [497 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$? words (Derived: Auxiliary data structures are H_k and m_k. H_k is just a singular value and is constant space, but m_k is a O(n)-size vector.) == Description == Gibbs sampler == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2008 == Reference == https://web.stanford.edu/~tsachy/pdf_files/Lossy%20Source%20Coding%20via%20Markov%20Cha...")
- 10:53, 15 February 2023 Martinian and M. J. Wainwright (Lossy Compression Data Compression) (hist | edit) [397 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*{2}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2006 == Reference == https://arxiv.org/abs/cs/0602046")
- 10:53, 15 February 2023 Miyake 2006 (Lossy Compression Data Compression) (hist | edit) [483 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*{2}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2006 == Reference == https://www.semanticscholar.org/paper/Lossy-Data-Compression-over-Zq-by-LDPC-Code-Miyake/652f0438118898b63126f7261ec4cd2002ff0e0b")
- 10:53, 15 February 2023 Brute force (Lossy Compression Data Compression) (hist | edit) [288 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*{2}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1940 == Reference ==")
- 10:53, 15 February 2023 Matsunaga; Yamamoto (Lossy Compression Data Compression) (hist | edit) [355 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*{2}^n)$ == Space Complexity == exp(n) words (https://doi.org/10.1109/TIT.2003.815805) == Description == Low Density Parity Check (LDPC) == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2003 == Reference == https://doi.org/10.1109/TIT.2003.815805")
- 10:53, 15 February 2023 Ciliberti; Mézard (Lossy Compression Data Compression) (hist | edit) [447 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == Constraint Satisfaction Problem with Random Gates == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2005 == Reference == https://arxiv.org/abs/cond-mat/0504509")
- 10:53, 15 February 2023 Sun; M. Shao; J. Chen; K. Wong; and X. Wu (Lossy Compression Data Compression) (hist | edit) [414 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*{2}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2010 == Reference == https://ieeexplore.ieee.org/document/5474629/")
- 10:53, 15 February 2023 Maneva and M. J. Wainwright (Lossy Compression Data Compression) (hist | edit) [472 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ bits (Derived: size of the factor graph representation of the generator matrix, or size of the generator matrix itself) == Description == Low Density Generator Matrix (LDGM) codes; for a Bernouli(1/2) source == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2005 == Reference == https://ieeexplore.ieee.org/document/1523592")
- 10:53, 15 February 2023 Discrete Cosine Transform (Lossy Compression Data Compression) (hist | edit) [339 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words (Derived: store the DCT coefficient for each input term) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1974 == Reference == https://doi.org/10.1109%2FT-C.1974.223784")
- 10:53, 15 February 2023 Gupta; Verdu (Lossy Compression Data Compression) (hist | edit) [449 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} log^{3} n)$ == Space Complexity == $O(n)$ bits (Derived: Considering the codebook to be part of the input, this only requires storing a single codeword in memory, of size $O(n)$, along with some constants) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2009 == Reference == https://doi.org/10.1109/TIT.2009.2016040")
- 10:53, 15 February 2023 The Multistage Algorithm (Finding Frequent Itemsets Finding Frequent Itemsets) (hist | edit) [366 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (Derived: modification of the Apriori algorithm, with same asymptotic complexities.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1999 == Reference == http://ilpubs.stanford.edu:8090/423/")
- 10:53, 15 February 2023 The Multihash Algorithm (Finding Frequent Itemsets Finding Frequent Itemsets) (hist | edit) [366 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (Derived: modification of the Apriori algorithm, with same asymptotic complexities.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1999 == Reference == http://ilpubs.stanford.edu:8090/423/")
- 10:53, 15 February 2023 A-Priori algorithm (Finding Frequent Itemsets Finding Frequent Itemsets) (hist | edit) [336 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (https://dl.acm.org/doi/pdf/10.1145/1014052.1014091) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1994 == Reference == http://www.vldb.org/conf/1994/P487.PDF")
- 10:53, 15 February 2023 The Algorithm of Park; Chen; and Yu (PCY) (Finding Frequent Itemsets Finding Frequent Itemsets) (hist | edit) [378 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (Derived: modification of the Apriori algorithm, with same asymptotic complexities.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1995 == Reference == https://dl.acm.org/doi/abs/10.1145/568271.223813")
- 10:53, 15 February 2023 GLR parser (CFG Parsing CFG Problems) (hist | edit) [400 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{3})$ words (https://link.springer.com/content/pdf/10.1007/978-3-662-21545-6.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? (implemented on ALGOL) == Year == 1974 == Reference == https://link.springer.com/chapter/10.1007%2F978-3-662-21545-6_18")
- 10:53, 15 February 2023 Earley parser (CFG Parsing CFG Problems) (hist | edit) [526 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$ words (https://web.archive.org/web/20040708052627/http://www-2.cs.cmu.edu/afs/cs.cmu.edu/project/cmt-55/lti/Courses/711/Class-notes/p94-earley.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1968 == Reference == https://web.archive.org/web/20040708052627/http://www-2.cs.cmu.edu/afs/cs.cmu.edu/projec...")
- 10:53, 15 February 2023 Cocke–Younger–Kasami algorithm (CFG Recognition CFG Problems) (hist | edit) [350 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3} * |G|)$ == Space Complexity == $O(n^{2})$ cells (https://core.ac.uk/download/pdf/158319955.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Double-tape TM == Year == 1968 == Reference == https://core.ac.uk/download/pdf/158319955.pdf")
- 10:53, 15 February 2023 Valiant (CFG Recognition CFG Problems) (hist | edit) [438 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^omega * |G|)$ where omega is the exponent for matrix multiplication == Space Complexity == $O(n^{2})$? words/cells (See matrix multiplication space complexity) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM and multitape TM == Year == 1975 == Reference == https://linkinghub.elsevier.com/retrieve/pii/S0022000075800468")
- 10:53, 15 February 2023 Niedermeier, Rossmanith (The Vertex Cover Problem The Vertex Cover Problem) (hist | edit) [415 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(kn + {1.29175}^k k^{2})$. == Space Complexity == $O(k^{3})$ auxiliary? (potentially $O(k^{2})$??) words ((see remark in algo id #576)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1999 == Reference == https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.69.1933&rep=rep1&type=pdf")
- 10:53, 15 February 2023 Downey (The Vertex Cover Problem The Vertex Cover Problem) (hist | edit) [414 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(kn + {1.31951}^k k^{2})$ == Space Complexity == $O(k^{3})$ auxiliary? (potentially $O(k^{2})$??) words ((see remark in algo id #576)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1998 == Reference == https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.12.4079&rep=rep1&type=pdf")
- 10:53, 15 February 2023 Papadimitriou and M Yannakakis (The Vertex Cover Problem The Vertex Cover Problem) (hist | edit) [447 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({3}^k n)$ == Space Complexity == $O(k)$ auxiliary? words (keep track of maximal matching, and subsequent vertices in cover; note that max size is O(k) else we can reject immediately) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1996 == Reference == https://www.sciencedirect.com/science/article/pii/S0022000096900586")
- 10:53, 15 February 2023 Chen; I. Kanj; and W. Jia. (The Vertex Cover Problem The Vertex Cover Problem) (hist | edit) [369 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({1.2738}^k+ kn)$ == Space Complexity == $O(poly(n))$ words (https://www.cs.lafayette.edu/~gexia/research/mfcs06.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference == https://www.cs.lafayette.edu/~gexia/research/mfcs06.pdf")
- 10:53, 15 February 2023 Balasubramanian; Fellows (The Vertex Cover Problem The Vertex Cover Problem) (hist | edit) [401 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(kn + ({1.324718})$^k * k^{2}) == Space Complexity == $O(k^{3})$ auxiliary? (potentially $O(k^{2})$??) words ((see remark in algo id #576)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1996 == Reference == https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.711.8844")
- 10:53, 15 February 2023 J. Chen; L. Liu; and W. Jia. (The Vertex Cover Problem, Degrees Bounded By 3 The Vertex Cover Problem) (hist | edit) [419 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(k*{1.2192}^k)$ == Space Complexity == $O(k^{3})$ auxiliary? (potentially $O(k^{2})$??) words ((see remark in algo id #576)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2000 == Reference == https://onlinelibrary.wiley.com/doi/abs/10.1002/1097-0037(200007)35:4%3C253::AID-NET3%3E3.0.CO;2-K")
- 10:53, 15 February 2023 Chandran and F. Grandoni (The Vertex Cover Problem The Vertex Cover Problem) (hist | edit) [514 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(min({1.2759}^k k^{1.5}, {1.2745}^k k^{4}) + kn)$ == Space Complexity == $O(min({1.2759}^k k^{1.5}, {1.2745}^k k^{4}) + kn)$ but exponential words (https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.136.4409&rep=rep1&type=pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2004 == Reference == https://citeseerx.ist.psu.edu/viewdoc/downloa...")
- 10:53, 15 February 2023 Sam Buss (The Vertex Cover Problem The Vertex Cover Problem) (hist | edit) [447 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(kn + {2}^k k^{({2}k + {2})})$ == Space Complexity == $O(k^{2})$ auxiliary? words (Auxiliary graph contains O(k^2) edges unless the instance is rejected; rest of steps take O(k^2) auxiliary space at most) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1993 == Reference == http://bud.cs.uky.edu/~goldsmit/papers/NondetWithinP.pdf")
- 10:53, 15 February 2023 Brute force (backtracking search) (The Vertex Cover Problem The Vertex Cover Problem) (hist | edit) [305 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^k n^O({1})$) == Space Complexity == $O(k)$ auxiliary words (Just need to keep track of current subset being checked) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 10:53, 15 February 2023 C-LOOK (Disk Scheduling Disk Scheduling) (hist | edit) [256 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*log n)$ == Space Complexity == $O(n)$ auxiliary words (See LOOK) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1979 == Reference == -")
- 10:53, 15 February 2023 LOOK (Disk Scheduling Disk Scheduling) (hist | edit) [314 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*log n)$ == Space Complexity == $O(n)$ auxiliary words (Needs sorted array of requests and seek distance but not much else) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1979 == Reference == -")
- 10:53, 15 February 2023 C-SCAN (Disk Scheduling Disk Scheduling) (hist | edit) [256 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*log n)$ == Space Complexity == $O(n)$ auxiliary words (See SCAN) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1979 == Reference == -")
- 10:53, 15 February 2023 SCAN (Disk Scheduling Disk Scheduling) (hist | edit) [327 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*log n)$ == Space Complexity == $O(n)$ auxiliary words (https://www.geeksforgeeks.org/scan-elevator-disk-scheduling-algorithms/?ref=lbp) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1979 == Reference == -")
- 10:53, 15 February 2023 SSTF (Disk Scheduling Disk Scheduling) (hist | edit) [346 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*log n)$ with binary tree == Space Complexity == $O(n)$ auxiliary words (https://www.geeksforgeeks.org/program-for-sstf-disk-scheduling-algorithm/?ref=lbp) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1979 == Reference == -")
- 10:53, 15 February 2023 FCFS (Disk Scheduling Disk Scheduling) (hist | edit) [335 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary words (Needs to keep track of seek distance but FCFS is fairly straightforward/no extra info needed) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1979 == Reference == -")
- 10:53, 15 February 2023 Catriel Beeri Ronald Fagin John H. Howard (Multivalued Dependency Inference Problem Dependency Inference Problem) (hist | edit) [269 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({4}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1977 == Reference == https://dl.acm.org/doi/10.1145/509404.509414")
- 10:53, 15 February 2023 Räihä; Manilla (Multivalued Dependency Inference Problem Dependency Inference Problem) (hist | edit) [428 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} {2}^n p log p)$ == Space Complexity == $O(n2^n)$? words (bound on size of output (2^n domains, O(n) possible attributes per domain); can probably be improved) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1992 == Reference == https://www.sciencedirect.com/science/article/pii/0166218X92900315")
- 10:53, 15 February 2023 Trino ( 4NF Decomposition) (hist | edit) [222 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2004 == Reference ==")
- 10:53, 15 February 2023 Naive ( 4NF Decomposition) (hist | edit) [222 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1956 == Reference ==")