User contributions for Admin

10:5310:53, 15 February 2023 diff hist +392‎ N Berlekamp's algorithm (Distinct-degree; Equal-degree Factorization of Polynomials Over Finite Fields) ‎ 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:5310:53, 15 February 2023 diff hist +304‎ N Jalali; A. Montanari; and T. Weissman (Lossy Compression Data Compression) ‎ 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:5310:53, 15 February 2023 diff hist +347‎ N Korada and R. Urbanke; (Lossy Compression Data Compression) ‎ 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" current
10:5310:53, 15 February 2023 diff hist +497‎ N Jalali and T. Weissman (Lossy Compression Data Compression) ‎ 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..." current
10:5310:53, 15 February 2023 diff hist +259‎ N Martinian and M. J. Wainwright (Lossy Compression Data Compression) ‎ 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:5310:53, 15 February 2023 diff hist +356‎ N Miyake 2006 (Lossy Compression Data Compression) ‎ 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:5310:53, 15 February 2023 diff hist +224‎ N Brute force (Lossy Compression Data Compression) ‎ Created page with "== Time Complexity == $O(n*{2}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1940 == Reference =="
10:5310:53, 15 February 2023 diff hist +272‎ N Sun; M. Shao; J. Chen; K. Wong; and X. Wu (Lossy Compression Data Compression) ‎ 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:5310:53, 15 February 2023 diff hist +355‎ N Matsunaga; Yamamoto (Lossy Compression Data Compression) ‎ 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" current
10:5310:53, 15 February 2023 diff hist +312‎ N Ciliberti; Mézard (Lossy Compression Data Compression) ‎ 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:5310:53, 15 February 2023 diff hist +339‎ N Discrete Cosine Transform (Lossy Compression Data Compression) ‎ 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" current
10:5310:53, 15 February 2023 diff hist +464‎ N Maneva and M. J. Wainwright (Lossy Compression Data Compression) ‎ 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:5310:53, 15 February 2023 diff hist +449‎ N Gupta; Verdu (Lossy Compression Data Compression) ‎ 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" current
10:5310:53, 15 February 2023 diff hist +366‎ N The Multistage Algorithm (Finding Frequent Itemsets Finding Frequent Itemsets) ‎ 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/" current
10:5310:53, 15 February 2023 diff hist +366‎ N The Multihash Algorithm (Finding Frequent Itemsets Finding Frequent Itemsets) ‎ 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/" current
10:5310:53, 15 February 2023 diff hist +336‎ N A-Priori algorithm (Finding Frequent Itemsets Finding Frequent Itemsets) ‎ 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" current
10:5310:53, 15 February 2023 diff hist +378‎ N The Algorithm of Park; Chen; and Yu (PCY) (Finding Frequent Itemsets Finding Frequent Itemsets) ‎ 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" current
10:5310:53, 15 February 2023 diff hist +403‎ N GLR parser (CFG Parsing CFG Problems) ‎ 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:5310:53, 15 February 2023 diff hist +526‎ N Earley parser (CFG Parsing CFG Problems) ‎ 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..." current
10:5310:53, 15 February 2023 diff hist +438‎ N Valiant (CFG Recognition CFG Problems) ‎ 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" current
10:5310:53, 15 February 2023 diff hist +350‎ N Cocke–Younger–Kasami algorithm (CFG Recognition CFG Problems) ‎ 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" current
10:5310:53, 15 February 2023 diff hist +415‎ N Niedermeier, Rossmanith (The Vertex Cover Problem The Vertex Cover Problem) ‎ 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" current
10:5310:53, 15 February 2023 diff hist +414‎ N Downey (The Vertex Cover Problem The Vertex Cover Problem) ‎ 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" current
10:5310:53, 15 February 2023 diff hist +447‎ N Papadimitriou and M Yannakakis (The Vertex Cover Problem The Vertex Cover Problem) ‎ 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" current
10:5310:53, 15 February 2023 diff hist +419‎ N J. Chen; L. Liu; and W. Jia. (The Vertex Cover Problem, Degrees Bounded By 3 The Vertex Cover Problem) ‎ 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" current
10:5310:53, 15 February 2023 diff hist +401‎ N Balasubramanian; Fellows (The Vertex Cover Problem The Vertex Cover Problem) ‎ 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" current
10:5310:53, 15 February 2023 diff hist +369‎ N Chen; I. Kanj; and W. Jia. (The Vertex Cover Problem The Vertex Cover Problem) ‎ 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:5310:53, 15 February 2023 diff hist +514‎ N Chandran and F. Grandoni (The Vertex Cover Problem The Vertex Cover Problem) ‎ 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..." current
10:5310:53, 15 February 2023 diff hist +457‎ N Sam Buss (The Vertex Cover Problem The Vertex Cover Problem) ‎ 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:5310:53, 15 February 2023 diff hist +315‎ N Brute force (backtracking search) (The Vertex Cover Problem The Vertex Cover Problem) ‎ 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:5310:53, 15 February 2023 diff hist +265‎ N C-LOOK (Disk Scheduling Disk Scheduling) ‎ 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:5310:53, 15 February 2023 diff hist +265‎ N C-SCAN (Disk Scheduling Disk Scheduling) ‎ 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:5310:53, 15 February 2023 diff hist +323‎ N LOOK (Disk Scheduling Disk Scheduling) ‎ 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:5310:53, 15 February 2023 diff hist +336‎ N SCAN (Disk Scheduling Disk Scheduling) ‎ 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:5310:53, 15 February 2023 diff hist +355‎ N SSTF (Disk Scheduling Disk Scheduling) ‎ 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:5310:53, 15 February 2023 diff hist +345‎ N FCFS (Disk Scheduling Disk Scheduling) ‎ 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:5310:53, 15 February 2023 diff hist +269‎ N Catriel Beeri Ronald Fagin John H. Howard (Multivalued Dependency Inference Problem Dependency Inference Problem) ‎ 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" current
10:5310:53, 15 February 2023 diff hist +428‎ N Räihä; Manilla (Multivalued Dependency Inference Problem Dependency Inference Problem) ‎ 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" current
10:5310:53, 15 February 2023 diff hist +222‎ N Trino ( 4NF Decomposition) ‎ Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2004 == Reference ==" current
10:5310:53, 15 February 2023 diff hist +222‎ N Naive ( 4NF Decomposition) ‎ Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1956 == Reference ==" current
10:5310:53, 15 February 2023 diff hist +222‎ N Derek's + Maxwell ( 4NF Decomposition) ‎ Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2001 == Reference ==" current
10:5310:53, 15 February 2023 diff hist +222‎ N Maxwell ( 4NF Decomposition) ‎ Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2000 == Reference ==" current
10:5310:53, 15 February 2023 diff hist +222‎ N Russell et. al. ( 4NF Decomposition) ‎ Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1989 == Reference ==" current
10:5310:53, 15 February 2023 diff hist +222‎ N Xu; Renio ( 4NF Decomposition) ‎ Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1972 == Reference ==" current
10:5310:53, 15 February 2023 diff hist +222‎ N Derek's Algorithm ( 4NF Decomposition) ‎ Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1983 == Reference ==" current
10:5310:53, 15 February 2023 diff hist +327‎ N Liu (Decisional BCNF BCNF Decomposition) ‎ Created page with "== Time Complexity == $O(kn^{2})$ == Space Complexity == $O(n)$ words (Derived: Creates an auxiliary database) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1992 == Reference == https://doi.org/10.1016/0950-5849(92)90028-N" current
10:5310:53, 15 February 2023 diff hist +222‎ N Tradu; Mirc ( 4NF Decomposition) ‎ Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1967 == Reference ==" current
10:5310:53, 15 February 2023 diff hist +368‎ N Schlimmer (Functional Dependency Inference Problem Dependency Inference Problem) ‎ Created page with "== Time Complexity == $O(n {2}^n p)$ == Space Complexity == $O({2}^n)$ words ((original source, but without user-supplied bound) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1993 == Reference == https://www.aaai.org/Papers/Workshops/1993/WS-93-02/WS93-02-017.pdf" current
10:5310:53, 15 February 2023 diff hist +428‎ N Brute force algorithm (Functional Dependency Inference Problem Dependency Inference Problem) ‎ 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 == 1967 == Reference == https://www.sciencedirect.com/science/article/pii/0166218X92900315"
10:5210:52, 15 February 2023 diff hist +299‎ N Naive algorithm (Subset Sum The Subset-Sum Problem) ‎ Created page with "== Time Complexity == $O({2}^n * n)$ == Space Complexity == $O(n)$ auxiliary words (https://dl.acm.org/doi/10.1145/321812.321823) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference =="

User contributions for Admin

15 February 2023

Navigation menu

Search