New pages

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

• 10:53, 15 February 2023 ‎FLOATER 2003 (Mesh Parameterization Mesh Parameterization) (hist | edit) ‎[318 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2003 == Reference == https://www.ams.org/journals/mcom/2003-72-242/S0025-5718-02-01466-7/S0025-5718-02-01466-7.pdf")
• 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 ==")

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