New pages
Jump to navigation
Jump to search
(newest | oldest) View (newer 500 | older 500) (20 | 50 | 100 | 250 | 500)
- 12:24, 3 May 2023 Reduction from Point on 3 Lines to 3 Points on Line (hist | edit) [452 bytes] Admin (talk | contribs) (Created page with "FROM: Point on 3 Lines TO: 3 Points on Line == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2")
- 10:19, 28 April 2023 The SUSAN corner detector (Corner Detection Feature Detection) (hist | edit) [252 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 1997 == Reference ==")
- 10:19, 28 April 2023 L. Kitchen and A. Rosenfeld (Corner Detection Feature Detection) (hist | edit) [325 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 1982 == Reference == https://www.sciencedirect.com/science/article/abs/pii/0167865582900204")
- 10:19, 28 April 2023 Harris and Stephens algorithm (Corner Detection Feature Detection) (hist | edit) [299 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 1988 == Reference == http://www.bmva.org/bmvc/1988/avc-88-023.pdf")
- 10:08, 28 April 2023 K-ANNS for a dense 3D map of geometric points (hist | edit) [887 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:k-ANNS for a dense 3D map of geometric points (Nearest Neighbor Search)}} == Description == Within a dataset of $n$ points in a dense 3D geometric map, find approximately the $k$ closest points to a specified point. == Related Problems == Generalizations: k Approximate Nearest Neighbors Search Related: k Nearest Neighbors Search == Parameters == $n$: number of points in dataset $k$: number of neighbors to find == Table of Algorithms ==...")
- 10:00, 10 April 2023 Reduction from Triangle Detection to Disjunctive Reachability Queries in MDPs (hist | edit) [650 bytes] Admin (talk | contribs) (Created page with "FROM: Triangle Detection TO: Disjunctive Reachability Queries in MDPs == Description == == Implications == assume: Strong Triangle<br/>then: there is no combinatorial $O(n^{3-\epsilon})$ or $O((k \cdot n^{2})^{1-\epsilon})$ algorithm for any $\epsilon > {0}$ for target. The bounds holf for dense MDPs with $m=\Theta(n^{2})$ == Year == 2016 == Reference == Chatterjee, Krishnendu, et al. "Model and objective separation with conditional lower bounds: Dis...")
- 09:56, 10 April 2023 Wen (1-dimensional Maximum subarray problem) (hist | edit) [309 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(log n)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == EREW PRAM == Year == 1995 == Reference == https://www.sciencedirect.com/science/article/abs/pii/016781919400063G")
- 09:55, 10 April 2023 Masek, Paterson (Edit sequence Sequence Alignment) (hist | edit) [410 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn/log(n)$) == Space Complexity == $O(mn/log(n)$) words (https://www.sciencedirect.com/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")
- 09:55, 10 April 2023 Wagner-Fischer algorithm (Edit sequence Sequence Alignment) (hist | edit) [334 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(mn)$ words (https://dl.acm.org/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")
- 09:55, 10 April 2023 Wagner-Fischer algorithm (Edit distance Sequence Alignment) (hist | edit) [303 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(m)$ words (Easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1974 == Reference == https://dl.acm.org/doi/abs/10.1145/321796.321811")
- 09:49, 10 April 2023 Kingsford (Motif Search Motif Search) (hist | edit) [418 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(m^{2}n^{2})$ words (Creates an ILP with $O(m^2n^2)$ variables and $O(n^2m)$ constraints, each involving $O(m)$ variables) == Description == ILP formulation == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference == https://link.springer.com/chapter/10.1007/11780441_22")
- 09:49, 10 April 2023 Liang Cwinnower (Motif Search Motif Search) (hist | edit) [364 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nm^{0.5})$ == Space Complexity == $O(m^{2})$ words (Considers a graph on $O(m)$ nodes and $O(m^2)$ edges) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2003 == Reference == https://www.worldscientific.com/doi/10.1142/S0219720004000466")
- 09:49, 10 April 2023 Sagot M (Motif Search Motif Search) (hist | edit) [370 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n \log(n)$ m^{1.{4}5}) == Space Complexity == $O(mn^{2}/w)$ words (https://link.springer.com/chapter/10.1007/BFb0054337) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1988 == Reference == https://link.springer.com/chapter/10.1007/BFb0054337")
- 09:49, 10 April 2023 Bailey TL; Elkan C MEME (Motif Search Motif Search) (hist | edit) [407 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2}m^{2})$ == Space Complexity == $O(mn)$ words (Uses iterations of the EM algorithm as in (Lawrence, Reilly 1990), and thus uses similar amounts of space) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1995 == Reference == https://link.springer.com/article/10.1007/BF00993379")
- 09:49, 10 April 2023 Sinha S; Tompa M YMF (Yeast Motif Finder) (Motif Search Motif Search) (hist | edit) [367 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{0.{6}6} m)$ == Space Complexity == $O(m)$ words (Derived: store number of occurances for each motif of a specified length) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2000 == Reference == https://www.ncbi.nlm.nih.gov/pubmed/10977095")
- 09:49, 10 April 2023 Tompa M (Motif Search Motif Search) (hist | edit) [410 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(m^{2})$ words (Requires considering an $O(m^2)*O(m^2)$ matrix with $O(m^2)$ nonzero entries, based on a DFA with $O(m^2)$ states) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1999 == Reference == https://www.aaai.org/Papers/ISMB/1999/ISMB99-030.pdf")
- 09:49, 10 April 2023 Van Helden J; Rios AF; Collado-Vides J (Motif Search Motif Search) (hist | edit) [378 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(m)$ words (Derived: store number of occurances for each motif of a specified length) == Description == Dyad analysis == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2000 == Reference == https://www.ncbi.nlm.nih.gov/pmc/articles/PMC102821/")
- 09:49, 10 April 2023 Helden Oligo-Analysis (Motif Search Motif Search) (hist | edit) [431 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(m)$ words (Derived: store number of occurances for each motif of a specified length) == Description == Uses oligonucleotides? Also only detects "short" motifs, and used for yeast == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1998 == Reference == https://www.ncbi.nlm.nih.gov/pubmed/9719638")
- 09:48, 10 April 2023 B. I. Kvasov (Hyperbolic Spline Interpolation Hyperbolic Spline Interpolation) (hist | edit) [441 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{4})$ == Space Complexity == $O(n)$?? words (Requires computing the coefficients b_i and functions Phi(x) and Psi(x) as in equations 17 and 18) == Description == Discrete Generalized Splines == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2000 == Reference == http://sutir.sut.ac.th:8080/sutir/bitstream/123456789/431/1/bib115.pdf")
- 09:48, 10 April 2023 P. Costantini, B. I. Kvasov, and C. Manni (Hyperbolic Spline Interpolation Hyperbolic Spline Interpolation) (hist | edit) [411 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{5} \log K)$ == Space Complexity == $O(n)$? words (Derived: Pentadiagonal matrix in the linear system only requires O(n) space) == Description == Pentadiagonal linear system == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1999 == Reference == https://link.springer.com/article/10.1023/A:1018988312596")
- 09:48, 10 April 2023 V. I. Paasonen (Hyperbolic Spline Interpolation Hyperbolic Spline Interpolation) (hist | edit) [229 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{5} \log K)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1968 == Reference ==")
- 09:48, 10 April 2023 V. A. Lyul’ka and I. E. Mikhailov (Hyperbolic Spline Interpolation Hyperbolic Spline Interpolation) (hist | edit) [316 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{4})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2003 == Reference == http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=zvmmf&paperid=943&option_lang=eng")
- 09:48, 10 April 2023 V. A. Lyul’ka and A. V. Romanenko (Hyperbolic Spline Interpolation Hyperbolic Spline Interpolation) (hist | edit) [261 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{5})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1994 == Reference == https://www.mathnet.ru/eng/zvmmf2544")
- 09:48, 10 April 2023 B.I. Kvasov (Hyperbolic Spline Interpolation Hyperbolic Spline Interpolation) (hist | edit) [413 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3} \log^{2}K)$ == Space Complexity == $O(n)$? words (Derived: Tridiagonal matrices in the linear system only require O(n) space) == Description == Tridiagonal linear system == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2008 == Reference == https://link.springer.com/article/10.1134/S0965542508040039")
- 09:42, 10 April 2023 Knuth–Bendix algorithm (Coset Enumeration Coset Enumeration) (hist | edit) [462 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({1.5}^n n^{2} logn)$ == Space Complexity == $O(ng)$??? words (Can store a table whose number of required registers is the product of the number of generators (n) and the number of cosets (O(g))) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1970 == Reference == https://www.cs.tufts.edu/~nr/cs257/archive/don-knuth/knuth-bendix.pdf")
- 09:42, 10 April 2023 Haselgrove-Leech-Trotter (HLT) algorithm (Coset Enumeration Coset Enumeration) (hist | edit) [387 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O(ng)$? words (Implementation stores a table whose number of required registers is the product of the number of generators (n) and the number of cosets (O(g))) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1940 == Reference ==")
- 09:42, 10 April 2023 Todd–Coxeter algorithm (Coset Enumeration Coset Enumeration) (hist | edit) [501 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O(gkc)$ words (Defines O(k) tables, each with O(g) columns and O(c) rows) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1936 == Reference == https://www.cambridge.org/core/journals/proceedings-of-the-edinburgh-mathematical-society/article/practical-method-for-enumerating-cosets-of-a-finite-abstract-group/030657...")
- 09:36, 10 April 2023 Fortune ( Delaunay Triangulation) (hist | edit) [460 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n \log n)$ == Space Complexity == $O(n)$ words (See Fortune's Algorithm (Voronoi diagrams); Voronoi diagram gives us O(n) circumcenters which can be used to find the O(n) triangles) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1987 == Reference == http://www.wias-berlin.de/people/si/course/files/Fortune87-SweepLine-Voronoi.pdf")
- 09:33, 10 April 2023 Conjugate Gradient (Positive Definite Matrix Linear System) (hist | edit) [409 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(m k^{0.5})$ == Space Complexity == $O(m)$ words (http://www.cs.cmu.edu/~quake-papers/painless-conjugate-gradient.pdf) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1952 == Reference == https://nvlpubs.nist.gov/nistpubs/jres/049/jresv49n6p409_A1b.pdf")
- 09:33, 10 April 2023 Shell Sort (Sedgewick) (Comparison Sorting Sorting) (hist | edit) [343 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{1.{3}3})$ == Space Complexity == $O({1})$ words (in-situ sorting) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1986 == Reference == https://www.sciencedirect.com/science/article/pii/0196677486900015?via%3Dihub")
- 09:33, 10 April 2023 Shell Sort (Pratt) (Comparison Sorting Sorting) (hist | edit) [312 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n \log^{2} n)$ == Space Complexity == $O({1})$ words (in-situ sorting) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1971 == Reference == https://apps.dtic.mil/sti/pdfs/AD0740110.pdf")
- 09:33, 10 April 2023 Shell Sort (Frank & Lazarus) (Comparison Sorting Sorting) (hist | edit) [313 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{1.5})$ == Space Complexity == $O({1})$ words (in-situ sorting) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1960 == Reference == https://dl.acm.org/citation.cfm?doid=366947.366957")
- 09:32, 10 April 2023 Shell Sort (Shell) (Comparison Sorting Sorting) (hist | edit) [311 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O({1})$ words (in-situ sorting) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1959 == Reference == https://dl.acm.org/citation.cfm?doid=368370.368387")
- 09:32, 10 April 2023 Khuller; Matias ( Closest Pair Problem) (hist | edit) [444 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$, not sure if this is auxiliary not mentioned (https://www.sciencedirect.com/science/article/pii/S0890540185710498, Theorem 2.3) == Description == Randomized Sieve == Approximate? == Exact == Randomized? == Yes, Las Vegas == Model of Computation == not mentioned == Year == 1995 == Reference == https://www.sciencedirect.com/science/article/pii/S0890540185710498")
- 09:29, 10 April 2023 Nivasch (Cycle Detection Cycle Detection) (hist | edit) [388 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(\mu + \lambda)$ == Space Complexity == $O(\log\mu)$ Stack size (https://www.gabrielnivasch.org/fun/cycle-detection) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == not mentioned == Year == 2004 == Reference == https://drive.google.com/file/d/16H_lrjeaBJqWvcn07C_w-6VNHldJ-ZZl/view")
- 09:29, 10 April 2023 Sedgewick; Szymanski; and Yao (Cycle Detection Cycle Detection) (hist | edit) [400 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $(\mu + \lambda)({1}+\Theta({1}/sqrt(M)))$ == Space Complexity == M Memory cells (https://epubs.siam.org/doi/abs/10.1137/0211030?journalCode=smjcat) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1982 == Reference == https://epubs.siam.org/doi/abs/10.1137/0211030?journalCode=smjcat")
- 09:29, 10 April 2023 Eppstein (Subset Sum The Subset-Sum Problem) (hist | edit) [380 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $\tilde{O}(n max(S))$ == Space Complexity == $O(t logt)$ (https://dl.acm.org/doi/pdf/10.1145/3329863, Table 1) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1997 == Reference == https://www.sciencedirect.com/science/article/abs/pii/S019667749690841X?via%3Dihub")
- 09:29, 10 April 2023 Compression/Clustering (Vector Quantization) (k-ANNS Nearest Neighbor Search) (hist | edit) [305 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == Varies by codebook structure == Space Complexity == Varies by codebook structure (Table 2) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 1992 == Reference ==")
- 09:29, 10 April 2023 Projected radial search (k-ANNS for a dense 3D map of geometric points Nearest Neighbor Search) (hist | edit) [418 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(k)$ == Space Complexity == $O({1})$ words (Derived: There are 5 local variables and no tables or lists aside from input/output) == Description == == Approximate? == Approximate Approximation Factor: ? == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2013 == Reference == http://www.araa.asn.au/acra/acra2013/papers/pap148s1-file1.pdf")
- 09:29, 10 April 2023 Locality-sensitive hashing (k-ANNS Nearest Neighbor Search) (hist | edit) [474 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nLkt)$ (pre-processing) $O(L(kt+dnP_2^k))$ (query-time) == Space Complexity == $O(nL)$ hash table cells (https://en.wikipedia.org/wiki/Locality-sensitive_hashing#LSH_algorithm_for_nearest_neighbor_search) == Description == == Approximate? == Approximate Approximation Factor: c == Randomized? == No, deterministic == Model of Computation == == Year == 2010 == Reference == http://infolab.stanford.edu/~ullman/mmds/ch3n.pdf")
- 09:29, 10 April 2023 Hierarchical Navigable Small World (HNSW) (k-ANNS Nearest Neighbor Search) (hist | edit) [419 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(M)$ bytes of memory (https://arxiv.org/abs/1603.09320, "Memory usage is proportional to choice of M") == Description == == Approximate? == Approximate Approximation Factor: ? experimental results == Randomized? == No, deterministic == Model of Computation == == Year == 2018 == Reference == https://doi.org/10.1109/TPAMI.2018.2889473")
- 08:57, 10 April 2023 Multilevel queue scheduling (Unweighted Interval Scheduling, Online Interval Scheduling) (hist | edit) [288 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n+k)$? words (^see above; also level information for each task) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 08:57, 10 April 2023 Work-conserving schedulers (Unweighted Interval Scheduling, Online Interval Scheduling) (hist | edit) [231 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 08:57, 10 April 2023 First come, first served (Unweighted Interval Scheduling, Online Interval Scheduling) (hist | edit) [250 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n+k)$? words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 08:57, 10 April 2023 Round-robin scheduling (Unweighted Interval Scheduling, Online Interval Scheduling) (hist | edit) [250 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n+k)$? words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 08:57, 10 April 2023 Fixed priority shortest job first (Unweighted Interval Scheduling, Online Interval Scheduling) (hist | edit) [394 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n \log n)$ == Space Complexity == $O(n+k)$? words (Keep track of (sorted, based on criteria) list of (unscheduled, running, etc.; just un-done) tasks, along with machine statuses and task priorities) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 08:57, 10 April 2023 Priority scheduling (Unweighted Interval Scheduling, Online Interval Scheduling) (hist | edit) [367 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n+k)$? words (Keep track of (sorted, based on criteria) list of (unscheduled, running, etc.; just un-done) tasks, along with machine statuses) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 08:57, 10 April 2023 Shortest remaining time first (Unweighted Interval Scheduling, Online Interval Scheduling) (hist | edit) [250 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n+k)$? words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 08:57, 10 April 2023 BOYS algorithm (Entity Resolution Entity Resolution) (hist | edit) [394 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} k)$ == Space Complexity == $O(n^{2})$ words (Derived: As written stores counts/probabailities for all pairs of entries.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1993 == Reference == https://www.sciencedirect.com/science/article/abs/pii/016794739390116B")
- 08:56, 10 April 2023 Gremban; Miller; Zagha (Inexact Laplacian Solver SDD Systems Solvers) (hist | edit) [454 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (https://www.cs.cmu.edu/~glmiller/Publications/Papers/GrMiZa94-tr.pdf) == Description == Support Tree Conjugate Gradients (STCG) == Approximate? == Approximate Approximation Factor: ? == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1995 == Reference == https://www.cs.cmu.edu/~glmiller/Publications/Papers/GrMiZa94-tr.pdf")
- 08:55, 10 April 2023 Closed formula (Square Matrix LU Decomposition LU Decomposition) (hist | edit) [238 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n \log n)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1975 == Reference ==")
- 08:55, 10 April 2023 David (Square Matrix LU Decomposition LU Decomposition) (hist | edit) [238 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n \log n)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference ==")
- 08:54, 10 April 2023 Masek; Patterson (Edit distance Sequence Alignment) (hist | edit) [382 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn / log(n))$ == Space Complexity == $O(n)$ words (https://www.sciencedirect.com/science/article/pii/0022000080900021) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1980 == Reference == https://www.sciencedirect.com/science/article/pii/0022000080900021")
- 08:54, 10 April 2023 Hirschberg's algorithm (Edit sequence Sequence Alignment) (hist | edit) [329 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(n)$ words (https://dl.acm.org/doi/10.1145/360825.360861) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1975 == Reference == https://dl.acm.org/doi/10.1145/360825.360861")
- 08:53, 10 April 2023 No-Steal, Force (hist | edit) [492 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:No-Steal, Force (Recovery)}} == Description == Recovery is the process of reverting back to a safe state prior to a system failure. With a No-Steal/Force policy, the recovery algorithm will never write uncommited data to memory, but will force all commits to memory. == Related Problems == Related: Steal, No-Force == Parameters == $n$: number of transactions before crash == Table of Algorithms == Currently no algorithms in our database for t...")
- 08:53, 10 April 2023 Steal, No-Force (hist | edit) [914 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Steal, No-Force (Recovery)}} == Description == Recovery is the process of reverting back to a safe state prior to a system failure. With a Steal/No-Force policy, the recovery algorithm will write possibly uncommited data to memory, while not forcing all commits to memory. == Related Problems == Related: No-Steal, Force == Parameters == $n$: number of transactions before crash == Table of Algorithms == {| class="wikitable sortable" style="t...")
- 08:53, 10 April 2023 Unweighted Interval Scheduling, Online (hist | edit) [3,094 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Unweighted Interval Scheduling, Online (Interval Scheduling)}} == Description == Given are $n$ intervals of the form $(s_j , f_j)$ with $s_j < f_j$, for $j = 1, \ldots , n$. These intervals are the jobs that require uninterrupted processing during that interval. We will assume (without loss of generality) that the $s_j$’s and the $f_j$’s are nonnegative integers. We say that two intervals (or jobs) overlap if their intersection is nonempty, otherwise...")
- 08:52, 10 April 2023 Root Computation with continuous first derivative (hist | edit) [764 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Root Computation with continuous first derivative (Root Computation)}} == Description == Given a real function with continuous first derivative, compute one of the roots. == Related Problems == Related: General Root Computation == Parameters == $\epsilon$: (additive) tolerance error $a, b$: endpoint values, with $b>a$ $n_{max}$: maximum number of iterations == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;"...")
- 08:52, 10 April 2023 General Root Computation (hist | edit) [2,713 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:General Root Computation (Root Computation)}} == Description == Given a real continuous function, compute one of the roots. == Related Problems == Related: Root Computation with continuous first derivative == Parameters == $\epsilon$: (additive) tolerance error $a, b$: endpoint values, with $b>a$ $n_{max}$: maximum number of iterations == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name...")
- 15:52, 15 February 2023 Reduction from OV to Disjunctive Reachability Queries in MDPs (hist | edit) [563 bytes] Admin (talk | contribs) (Created page with "FROM: OV TO: Disjunctive Reachability Queries in MDPs == Description == == Implications == assume: Strong Triangle<br/>then: there is no $O(m^{2-\epsilon})$ or $O((k \cdot m)^{1-\epsilon})$ algorithm, for any $\epsilon > {0}$ for target. == Year == 2016 == Reference == Chatterjee, Krishnendu, et al. "Model and objective separation with conditional lower bounds: Disjunction is harder than conjunction." Proceedings of the 31st Annual ACM/IEEE Symposium...")
- 12:19, 15 February 2023 Reduction from OV to k-OV (hist | edit) [135 bytes] Admin (talk | contribs) (Created page with "FROM: OV TO: k-OV == Description == == Implications == == Year == == Reference ==")
- 12:19, 15 February 2023 Reduction from Max-Weight K-Clique to Maximum Square Subarray (hist | edit) [596 bytes] Admin (talk | contribs) (Created page with "FROM: Max-Weight K-Clique TO: Maximum Square Subarray == Description == == Implications == if: to-time: $O(n^{d+{1}-\epsilon})$ for $d$-dimensional hypercube arrays<br/>then: from-time: $O(n^{k-\epsilon})$ on $n$ vertex graphs for $k=d+{1}$ == Year == 2016 == Reference == Backurs, Arturs, Nishanth Dikkala, and Christos Tzamos. "Tight Hardness Results for Maximum Weight Rectangles}}." 43rd International Colloquium on Automata, Languages, and Programm...")
- 12:19, 15 February 2023 Reduction from Max-Weight K-Clique to Weighted Depth (hist | edit) [619 bytes] Admin (talk | contribs) (Created page with "FROM: Max-Weight K-Clique TO: Weighted Depth == Description == == Implications == if: to-time: $O(n^{\lfloor d/{2}\rfloor-\epsilon})$ for $N$ weighted axis-parallel boxes in $\mathbb{R}^d$<br/>then: from-time: $O(n^{k-{2}\epsilon})$ on $n$ vertex graphs for $k=d$ == Year == 2016 == Reference == Backurs, Arturs, Nishanth Dikkala, and Christos Tzamos. "Tight Hardness Results for Maximum Weight Rectangles}}." 43rd International Colloquium on Automata,...")
- 12:19, 15 February 2023 Reduction from Max-Weight k-Clique to Maximum Subarray (hist | edit) [623 bytes] Admin (talk | contribs) (Created page with "FROM: Max-Weight k-Clique TO: Maximum Subarray == Description == == Implications == if: to-time: $O(n^{d+\lfloor d/{2}\rfloor-\epsilon})$ for $d$-dimensional hypercube arrays<br/>then: from-time: $O(n^{k-\epsilon})$ on $n$ vertex graphs for $k=d+\lfloor d/{2}\rfloor$ == Year == 2016 == Reference == Backurs, Arturs, Nishanth Dikkala, and Christos Tzamos. "Tight Hardness Results for Maximum Weight Rectangles}}." 43rd International Colloquium on Automa...")
- 12:19, 15 February 2023 Reduction from 3-OV to k-OV (hist | edit) [141 bytes] Admin (talk | contribs) (Created page with "FROM: 3-OV TO: k-OV == Description == == Implications == == Year == == Reference ==")
- 12:19, 15 February 2023 Reduction from Max-Weight k-Clique to Max-Weight Rectangle (hist | edit) [616 bytes] Admin (talk | contribs) (Created page with "FROM: Max-Weight k-Clique TO: Max-Weight Rectangle == Description == == Implications == if: to-time: $O(N^{d-\epsilon})$ on $N$ weighted points in $d$ dimensions<br/>then: from-time: $O(n^{k-\epsilon})$ on $n$ vertices, where $k=\lceil d^{2}\epsilon^{-1}\rceil$ == Year == 2016 == Reference == Backurs, Arturs, Nishanth Dikkala, and Christos Tzamos. "Tight Hardness Results for Maximum Weight Rectangles}}." 43rd International Colloquium on Automata, Lan...")
- 12:19, 15 February 2023 Reduction from Weighted, Undirected APSP to 2D Maximum Subarray (hist | edit) [572 bytes] Admin (talk | contribs) (Created page with "FROM: Weighted, Undirected APSP TO: 2D Maximum Subarray == Description == == Implications == if: to-time: $O(n^{3-\epsilon})$ on $n\times n$ matrices<br/>then: from-time: $O(n^{3-\epsilon/{1}0})$ on $n$ vertex graphs == Year == 2016 == Reference == Backurs, Arturs, Nishanth Dikkala, and Christos Tzamos. "Tight Hardness Results for Maximum Weight Rectangles}}." 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Vol. 5...")
- 12:19, 15 February 2023 Reduction from Bichromatic Hamming Close Pair to Approximate Hard-Margin SVM (hist | edit) [701 bytes] Admin (talk | contribs) (Created page with "FROM: Bichromatic Hamming Close Pair TO: Approximate Hard-Margin SVM == Description == == Implications == assume: SETH<br/>then: let $k(a,a')$ be the Gaussian kernel with $C={100}\log n$ and let $\epsilon = \exp(-\omega(\log^{2} n))$, then approximating the optimal value of target within multiplicative factor ${1}+\epsilon$ requires almost quadratic time. == Year == 2017 == Reference == Backurs, A., Indyk, P., & Schmidt, L. (2017). On the fine-graine...")
- 12:19, 15 February 2023 Reduction from Negative Triangle Detection to 2D Maximum Subarray (hist | edit) [569 bytes] Admin (talk | contribs) (Created page with "FROM: Negative Triangle Detection TO: 2D Maximum Subarray == Description == == Implications == if: to-time: $O(n^{3-\epsilon})$ on $n\times n$ matrices<br/>then: from-time: $O(n^{3-\epsilon})$ on $n$ vertex graphs == Year == 2016 == Reference == Backurs, Arturs, Nishanth Dikkala, and Christos Tzamos. "Tight Hardness Results for Maximum Weight Rectangles}}." 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Vol. 55....")
- 12:19, 15 February 2023 Reduction from Maximum Inner Product Search to Stable Pair Checking (hist | edit) [641 bytes] Admin (talk | contribs) (Created page with "FROM: Maximum Inner Product Search TO: Stable Pair Checking == Description == == Implications == assume: OVH<br/>then: for any $\epsilon > {0}$, there is a $c$ such that determining whether a given pair is part of any or all stable matchings in the boolean $d$-attribute model with $d = c\log n$ dimensions requires time $\Omega(n^{2-\epsilon})$ == Year == 2016 == Reference == Moeller, Daniel, Ramamohan Paturi, and Stefan Schneider. "Subquadratic algor...")
- 12:19, 15 February 2023 Reduction from OV to Disjunctive Queries of Safety in Graphs (hist | edit) [590 bytes] Admin (talk | contribs) (Created page with "FROM: OV TO: Disjunctive Queries of Safety in Graphs == Description == == Implications == assume: OVH<br/>then: there is no $O(m^{2-\epsilon})$ or $O((k \cdot m)^{1 - \epsilon})$ algorithm for any $\epsilon > {0}$ for disjunctive safety ovjectives/queries in MDPs. == Year == 2016 == Reference == Chatterjee, Krishnendu, et al. "Model and objective separation with conditional lower bounds: Disjunction is harder than conjunction." Proceedings of the 31s...")
- 12:19, 15 February 2023 Reduction from Maximum Inner Product Search to Stable Matching Verification (hist | edit) [585 bytes] Admin (talk | contribs) (Created page with "FROM: Maximum Inner Product Search TO: Stable Matching Verification == Description == == Implications == assume: OVH<br/>then: for an $\epsilon > {0}$ there is a $c$ such that verifying a stable matching in the boolean $d$-attribute model with $d = c\log n$ dimensions requires time $\Omega(n^{2-\epsilon}). == Year == 2016 == Reference == Moeller, Daniel, Ramamohan Paturi, and Stefan Schneider. "Subquadratic algorithms for succinct stable matching." I...")
- 12:19, 15 February 2023 Reduction from Maximum Inner Product Search to Boolean d-Attribute Stable Matching (hist | edit) [591 bytes] Admin (talk | contribs) (Created page with "FROM: Maximum Inner Product Search TO: Boolean d-Attribute Stable Matching == Description == == Implications == assume: OVH<br/>then: for an $\epsilon > {0}$ there is a $c$ such that finding a stable matching in the boolean $d$-attribute model with $d = c\log n$ dimensions requires time $\Omega(n^{2-\epsilon})$. == Year == 2016 == Reference == Moeller, Daniel, Ramamohan Paturi, and Stefan Schneider. "Subquadratic algorithms for succinct stable matchi...")
- 12:19, 15 February 2023 Reduction from OV to Disjunctive Queries of Reachability in MDPs (hist | edit) [563 bytes] Admin (talk | contribs) (Created page with "FROM: OV TO: Disjunctive Queries of Reachability in MDPs == Description == == Implications == assume: Strong Triangle<br/>then: there is no $O(m^{2-\epsilon})$ or $O((k \cdot m)^{1-\epsilon})$ algorithm, for any $\epsilon > {0}$ for target. == Year == 2016 == Reference == Chatterjee, Krishnendu, et al. "Model and objective separation with conditional lower bounds: Disjunction is harder than conjunction." Proceedings of the 31st Annual ACM/IEEE Sympos...")
- 12:19, 15 February 2023 Reduction from Triangle Detection to Disjunctive Queries of Safety in Graphs (hist | edit) [642 bytes] Admin (talk | contribs) (Created page with "FROM: Triangle Detection TO: Disjunctive Queries of Safety in Graphs == Description == == Implications == assume: Strong Triangle<br/>then: there is no combinatorial $O(n^{3-\epsilon})$ or $O((k \cdot n^{2})^{1-\epsilon})$ algorithm, for any $\epsilon > {0}$ for disjunctive safety (objectives or queries) in graphs. == Year == 2016 == Reference == Chatterjee, Krishnendu, et al. "Model and objective separation with conditional lower bounds: Disjunction...")
- 12:19, 15 February 2023 Reduction from Triangle Detection to Disjunctive Queries of Reachability in MDPs (hist | edit) [653 bytes] Admin (talk | contribs) (Created page with "FROM: Triangle Detection TO: Disjunctive Queries of Reachability in MDPs == Description == == Implications == assume: Strong Triangle<br/>then: there is no combinatorial $O(n^{3-\epsilon})$ or $O((k \cdot n^{2})^{1-\epsilon})$ algorithm for any $\epsilon > {0}$ for target. The bounds holf for dense MDPs with $m=\Theta(n^{2})$ == Year == 2016 == Reference == Chatterjee, Krishnendu, et al. "Model and objective separation with conditional lower bounds:...")
- 12:19, 15 February 2023 Reduction from Triangle Detection to Disjunctive coBüchi Objectives (hist | edit) [692 bytes] Admin (talk | contribs) (Created page with "FROM: Triangle Detection TO: Disjunctive coBüchi Objectives == Description == == Implications == assume: Strong Triangle<br/>then: there is no combinatorial $O(n^{3-\epsilon})$ or $O((k\cdot n^{2})^{1-\epsilon})$-time algorithm for any $epsilon > {0}$ for generalized Büchi games. In particular, there is no such algorithm deciding whether the winning set is non-empty or deciding whether a specific vertex is in the winning set. == Year == 2016 == Refer...")
- 12:19, 15 February 2023 Reduction from OV to Generalized Büchi Games (hist | edit) [678 bytes] Admin (talk | contribs) (Created page with "FROM: OV TO: Generalized Büchi Games == Description == == Implications == assume: OVH<br/>then: there is no $O(m^{2-\epsilon})$ or $O(\min_{1 \leq i \leq k} b_i \cdot (k \cdot m)^{1-\epsilon})$-time algorithm (for any $\epsilon > {0}$ for generalized Büchi games. In particular there is no such algorithm for deciding whether the winning set is non-empty or deciding whether a specifc vertex is in the winning set. == Year == 2016 == Reference == Chat...")
- 12:19, 15 February 2023 Reduction from OV to Largest Common Subtree (hist | edit) [563 bytes] Admin (talk | contribs) (Created page with "FROM: OV TO: Largest Common Subtree == Description == == Implications == assume: OVH<br/>then: for all constants $d \geq {2}$, target on two rooted trees of size at most $n$, degree $d$, and height $h \leq \log_d n + O(\log \log n)$ cannot be solved in truly subquadtratic $O(n^{2-\epsilon})$ time == Year == 2018 == Reference == Abboud, A., Backurs, A., Hansen, T. D., Vassilevska Williams, V., & Zamir, O. (2018). Subtree isomorphism revisited. ACM Tra...")
- 12:19, 15 February 2023 Reduction from OV to Subtree Isomorphism (hist | edit) [557 bytes] Admin (talk | contribs) (Created page with "FROM: OV TO: Subtree Isomorphism == Description == == Implications == assume: OVH<br/>then: for all $d \geq {2}$, target on two rooted unordered trees of size $O(n)$, degree $d$, and height $h \leq {2}\log_d n + O(\log \log n)$ cannot be solved in truly subquadratic $O(n^{2-\epsilon})$ time == Year == 2018 == Reference == Abboud, A., Backurs, A., Hansen, T. D., Vassilevska Williams, V., & Zamir, O. (2018). Subtree isomorphism revisited. ACM Transacti...")
- 12:19, 15 February 2023 Reduction from k-SAT to Subset Sum (hist | edit) [544 bytes] Admin (talk | contribs) (Created page with "FROM: k-SAT TO: Subset Sum == Description == == Implications == assume: SETH<br/>then: for any $\epsilon > {0}$ there exists a $\delta > {0}$ such that Subset Sum is not in time $O(T^{1-\epsilon}{2}^{\delta n})$, and $k$-Sum is not in time $O(T^{1-\epsilon}n^{\delta k})$ == Year == 2022 == Reference == Abboud, A., Bringmann, K., Hermelin, D., & Shabtay, D. (2022). SETH-based lower bounds for subset sum and bicriteria path. ACM Transactions on Algorit...")
- 12:19, 15 February 2023 Reduction from k-Clique to CFG Recognition (hist | edit) [594 bytes] Admin (talk | contribs) (Created page with "FROM: k-Clique TO: CFG Recognition == Description == == Implications == assume: k-Clique Hypothesis<br/>then: there is no $O(N^{\omega-\epsilon}) time algorithm for target for any $\epsilon > {0}$ == Year == 2017 == Reference == Abboud, A., Backurs, A., Bringmann, K., & Künnemann, M. (2017, October). Fine-grained complexity of analyzing compressed data: Quantifying improvements over decompress-and-solve. In 2017 IEEE 58th Annual Symposium on Foundat...")
- 12:19, 15 February 2023 Reduction from k-Clique to RNA Folding (hist | edit) [590 bytes] Admin (talk | contribs) (Created page with "FROM: k-Clique TO: RNA Folding == Description == == Implications == assume: k-Clique Hypothesis<br/>then: there is no $O(N^{\omega-\epsilon}) time algorithm for target for any $\epsilon > {0}$ == Year == 2017 == Reference == Abboud, A., Backurs, A., Bringmann, K., & Künnemann, M. (2017, October). Fine-grained complexity of analyzing compressed data: Quantifying improvements over decompress-and-solve. In 2017 IEEE 58th Annual Symposium on Foundations...")
- 12:19, 15 February 2023 Reduction from OV to Bichromatic Hamming Close Pair (hist | edit) [525 bytes] Admin (talk | contribs) (Created page with "FROM: OV TO: Bichromatic Hamming Close Pair == Description == == Implications == assume: OVH<br/>then: there is no algorithm to solve target in time $O({2}^{o(d)}n^{2-\epsilon})$ on a set of $n$ points in $\{0,{1}\}^{c\log n}$ == Year == 2015 == Reference == Alman, J., & Williams, R. (2015, October). Probabilistic polynomials and hamming nearest neighbors. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (pp. 136-150). IEEE. htt...")
- 12:19, 15 February 2023 Reduction from CNF-SAT to sensitive incremental ST-Reach (hist | edit) [590 bytes] Admin (talk | contribs) (Created page with "FROM: CNF-SAT TO: sensitive incremental ST-Reach == Description == == Implications == assume: SETH<br/>then: let $\epsilon > {0}$, $t \in \mathbb{N}$, there exists no algorithm for target with preprocessing time $O(n^t)$, update time $u(n)$ and query time $q(n)$, such that $max\{u(n),q(n)\}=O(n^{1-\epsilon})$ with constant sensitivity $K(\epsilon,t)$ == Year == 2017 == Reference == Henzinger, M., Lincoln, A., Neumann, S., & Williams, V. V. (2017). Co...")
- 12:19, 15 February 2023 Reduction from CNF-SAT to constant sensitivity (4/3)-approximate incremental diameter (hist | edit) [619 bytes] Admin (talk | contribs) (Created page with "FROM: CNF-SAT TO: constant sensitivity (4/3)-approximate incremental diameter == Description == == Implications == assume: SETH<br/>then: let $\epsilon > {0}$, $t \in \mathbb{N}$, there exists no algorithm for target with preprocessing time $O(n^t)$, update time $u(n)$ and query time $q(n)$, such that $max\{u(n),q(n)\}=O(n^{1-\epsilon})$ with constant sensitivity $K(\epsilon,t)$ == Year == 2017 == Reference == Henzinger, M., Lincoln, A., Neumann, S.,...")
- 12:19, 15 February 2023 Reduction from Directed, Weighted APSP to 1-sensitive decremental diameter (hist | edit) [545 bytes] Admin (talk | contribs) (Created page with "FROM: Directed, Weighted APSP TO: 1-sensitive decremental diameter == Description == == Implications == assume: APSP Hypothesis<br/>then: target cannot be solved with preprocessing time $O(n^{3-\epsilon})$ and update and query times $O(n^{2-\epsilon})$ for any $\epsilon > {0}$ in undirected weighted graphs == Year == 2017 == Reference == Henzinger, M., Lincoln, A., Neumann, S., & Williams, V. V. (2017). Conditional hardness for sensitivity problems....")
- 12:19, 15 February 2023 Reduction from Directed, Weighted APSP to 2-sensitive decremental st-shortest paths (hist | edit) [554 bytes] Admin (talk | contribs) (Created page with "FROM: Directed, Weighted APSP TO: 2-sensitive decremental st-shortest paths == Description == == Implications == assume: APSP Hypothesis<br/>then: target cannot be solved with preprocessing time $O(n^{3-\epsilon})$ and update and query times $O(n^{2-\epsilon})$ for any $\epsilon > {0}$ in undirected weighted graphs == Year == 2017 == Reference == Henzinger, M., Lincoln, A., Neumann, S., & Williams, V. V. (2017). Conditional hardness for sensitivity p...")
- 12:19, 15 February 2023 Reduction from Replacement Paths Problem (RPP) to 1-sensitive decremental st-shortest paths (hist | edit) [560 bytes] Admin (talk | contribs) (Created page with "FROM: Replacement Paths Problem (RPP) TO: 1-sensitive decremental st-shortest paths == Description == == Implications == assume: APSP Hypothesis<br/>then: target cannot be solved with preprocessing time $O(n^{3-\epsilon})$ and update and query times $O(n^{2-\epsilon})$ for any $\epsilon > {0}$ in directed weighted graphs == Year == 2017 == Reference == Henzinger, M., Lincoln, A., Neumann, S., & Williams, V. V. (2017). Conditional hardness for sensiti...")
- 12:19, 15 February 2023 Reduction from CNF-SAT to sensitive incremental (hist | edit) [586 bytes] Admin (talk | contribs) (Created page with "FROM: CNF-SAT TO: sensitive incremental #SSR == Description == == Implications == assume: SETH<br/>then: let $\epsilon > {0}$, $t \in \mathbb{N}$, there exists no algorithm for target with preprocessing time $O(n^t)$, update time $u(n)$ and query time $q(n)$, such that $max\{u(n),q(n)\}=O(n^{1-\epsilon})$ with constant sensitivity $K(\epsilon,t)$ == Year == 2017 == Reference == Henzinger, M., Lincoln, A., Neumann, S., & Williams, V. V. (2017). Condit...")
- 12:19, 15 February 2023 Reduction from BMM to 1-sensitive decremental st-shortest paths (hist | edit) [547 bytes] Admin (talk | contribs) (Created page with "FROM: BMM TO: 1-sensitive decremental st-shortest paths == Description == == Implications == assume: BMM<br/>then: for directed unweighted graphs with $n$ vertices and $m \geq n$ edges require either $m^{1-o({1})}\sqrt{n}$ preprocessing time or $m^{1-o({1})}/\sqrt{n}$ query time for every function $m$ of $n$ == Year == 2017 == Reference == Henzinger, M., Lincoln, A., Neumann, S., & Williams, V. V. (2017). Conditional hardness for sensitivity problems...")
- 12:19, 15 February 2023 Reduction from BMM to 1-sensitive (4/3)-approximate decremental eccentricity (hist | edit) [527 bytes] Admin (talk | contribs) (Created page with "FROM: BMM TO: 1-sensitive (4/3)-approximate decremental eccentricity == Description == == Implications == assume: BMM<br/>then: combinatorial algorithms cannot solve target with preprocessing time $O(n^{3-\epsilon})$, and update and query times $O(n^{2-\epsilon})$ for any $\epsilon > {0}$ == Year == 2017 == Reference == Henzinger, M., Lincoln, A., Neumann, S., & Williams, V. V. (2017). Conditional hardness for sensitivity problems. arXiv preprint arX...")
- 12:19, 15 February 2023 Reduction from BMM to 1-sensitive (4/3)-approximate decremental diameter (hist | edit) [555 bytes] Admin (talk | contribs) (Created page with "FROM: BMM TO: 1-sensitive (4/3)-approximate decremental diameter == Description == == Implications == assume: BMM<br/>then: combinatorial algorithms cannot solve target with preprocessing time $O(n^{3-\epsilon})$, and update and query times $O(n^{2-\epsilon})$ for any $\epsilon > {0}$ in undirected unweighted graphs == Year == 2017 == Reference == Henzinger, M., Lincoln, A., Neumann, S., & Williams, V. V. (2017). Conditional hardness for sensitivity...")
- 12:19, 15 February 2023 Reduction from BMM to (5/3)-approximate ap-shortest paths (hist | edit) [508 bytes] Admin (talk | contribs) (Created page with "FROM: BMM TO: (5/3)-approximate ap-shortest paths == Description == == Implications == assume: BMM<br/>then: combinatorial algorithms cannot solve target with preprocessing time $O(n^{3-\epsilon})$, and update and query times $O(n^{2-\epsilon})$ for any $\epsilon > {0}$ == Year == 2017 == Reference == Henzinger, M., Lincoln, A., Neumann, S., & Williams, V. V. (2017). Conditional hardness for sensitivity problems. arXiv preprint arXiv:1703.01638. htt...")
- 12:19, 15 February 2023 Reduction from BMM to 1-sensitive (3/2)-approximate ss-shortest paths (hist | edit) [552 bytes] Admin (talk | contribs) (Created page with "FROM: BMM TO: 1-sensitive (3/2)-approximate ss-shortest paths == Description == == Implications == assume: BMM<br/>then: combinatorial algorithms cannot solve target with preprocessing time $O(n^{3-\epsilon})$, and update and query times $O(n^{2-\epsilon})$ for any $\epsilon > {0}$ in undirected unweighted graphs == Year == 2017 == Reference == Henzinger, M., Lincoln, A., Neumann, S., & Williams, V. V. (2017). Conditional hardness for sensitivity pro...")
- 12:19, 15 February 2023 Reduction from BMM to 2-sensitive (7/5)-approximate st-shortest paths (hist | edit) [552 bytes] Admin (talk | contribs) (Created page with "FROM: BMM TO: 2-sensitive (7/5)-approximate st-shortest paths == Description == == Implications == assume: BMM<br/>then: combinatorial algorithms cannot solve target with preprocessing time $O(n^{3-\epsilon})$, and update and query times $O(n^{2-\epsilon})$ for any $\epsilon > {0}$ in undirected unweighted graphs == Year == 2017 == Reference == Henzinger, M., Lincoln, A., Neumann, S., & Williams, V. V. (2017). Conditional hardness for sensitivity pro...")
- 12:19, 15 February 2023 Reduction from BMM to ap-reach (hist | edit) [481 bytes] Admin (talk | contribs) (Created page with "FROM: BMM TO: ap-reach == Description == == Implications == assume: BMM<br/>then: combinatorial algorithms cannot solve target with preprocessing time $O(n^{3-\epsilon})$, and update and query times $O(n^{2-\epsilon})$ for any $\epsilon > {0}$ == Year == 2017 == Reference == Henzinger, M., Lincoln, A., Neumann, S., & Williams, V. V. (2017). Conditional hardness for sensitivity problems. arXiv preprint arXiv:1703.01638. https://arxiv.org/pdf/1703.016...")
- 12:19, 15 February 2023 Reduction from BMM to 2-sensitive incremental st-reach (hist | edit) [505 bytes] Admin (talk | contribs) (Created page with "FROM: BMM TO: 2-sensitive incremental st-reach == Description == == Implications == assume: BMM<br/>then: combinatorial algorithms cannot solve target with preprocessing time $O(n^{3-\epsilon})$, and update and query times $O(n^{2-\epsilon})$ for any $\epsilon > {0}$ == Year == 2017 == Reference == Henzinger, M., Lincoln, A., Neumann, S., & Williams, V. V. (2017). Conditional hardness for sensitivity problems. arXiv preprint arXiv:1703.01638. https:...")
- 12:19, 15 February 2023 Reduction from BMM to 1-sensitive incremental ss-reach (hist | edit) [505 bytes] Admin (talk | contribs) (Created page with "FROM: BMM TO: 1-sensitive incremental ss-reach == Description == == Implications == assume: BMM<br/>then: combinatorial algorithms cannot solve target with preprocessing time $O(n^{3-\epsilon})$, and update and query times $O(n^{2-\epsilon})$ for any $\epsilon > {0}$ == Year == 2017 == Reference == Henzinger, M., Lincoln, A., Neumann, S., & Williams, V. V. (2017). Conditional hardness for sensitivity problems. arXiv preprint arXiv:1703.01638. https:...")
- 12:19, 15 February 2023 Reduction from OuMv to Bipartite Graph MCM (hist | edit) [550 bytes] Admin (talk | contribs) (Created page with "FROM: OuMv TO: Bipartite Graph MCM == Description == == Implications == assume: OMv<br/>then: there is no algorithm for solving incremental (or decremental) maximum cardinality bipartite matching with amortized time $O(n^{1-\epsilon})$ per insertion (or deletion) and $O(n^{2-\epsilon})$ time per query for any $\epsilon > {0}$ == Year == 2016 == Reference == Dahlgaard, S. (2016). On the hardness of partially dynamic graph problems and connections to d...")
- 12:19, 15 February 2023 Reduction from Triangle Collection* to dynamic 4/3-Diameter (hist | edit) [666 bytes] Admin (talk | contribs) (Created page with "FROM: Triangle Collection* TO: dynamic 4/3-Diameter == Description == == Implications == assume: SETH or {3}SUM Hypothesis or APSP Hypothesis<br/>then: there exists no incremental (or decremental) algorithm that approximates the diameter of unweighted graph within a factor of ${4}/{3}-\epsilon$ running in amortized time $O(n^{1/{2}-\epsilon'})$ for any $\epsilon,\epsilon' > {0}$. Furthermore, if we allow node insertions in the incremental case the bound is...")
- 12:19, 15 February 2023 Reduction from CNF-SAT to dynamic st-Maximum Flow (hist | edit) [551 bytes] Admin (talk | contribs) (Created page with "FROM: CNF-SAT TO: dynamic st-Maximum Flow == Description == == Implications == assume: SETH<br/>then: there is no algorithm for solving incremental (or decremental) st-max-flow on a weighted and directed graph with $n$ nodes and $\tilde{O}(n)$ edges with amortized time $O(m^{1-\epsilon})$ per operation for any $\epsilon > {0}$ == Year == 2016 == Reference == Dahlgaard, S. (2016). On the hardness of partially dynamic graph problems and connections to...")
- 12:19, 15 February 2023 Reduction from OuMV to dynamic st-Maximum Flow (hist | edit) [548 bytes] Admin (talk | contribs) (Created page with "FROM: OuMV TO: dynamic st-Maximum Flow == Description == == Implications == assume: OMv<br/>then: there is no algorithm for solving incremental (or decremental) st-max-flow on unweifghted directed graphs or weighted undirected graphs on $n$ nodes with amortized time $O(n^{1-\epsilon})$ per operation for any $\epsilon > {0}$ == Year == 2016 == Reference == Dahlgaard, S. (2016). On the hardness of partially dynamic graph problems and connections to dia...")
- 12:18, 15 February 2023 Reduction from GeomBase to Visibility Between Segments (hist | edit) [455 bytes] Admin (talk | contribs) (Created page with "FROM: GeomBase TO: Visibility Between Segments == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2")
- 12:18, 15 February 2023 Reduction from Strips Cover Box to Point Covering (hist | edit) [450 bytes] Admin (talk | contribs) (Created page with "FROM: Strips Cover Box TO: Point Covering == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2")
- 12:18, 15 February 2023 Reduction from Triangles Cover Triangle to Triangle Measure (hist | edit) [460 bytes] Admin (talk | contribs) (Created page with "FROM: Triangles Cover Triangle TO: Triangle Measure == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2")
- 12:18, 15 February 2023 Reduction from Hole in Union to Triangles Cover Triangle (hist | edit) [457 bytes] Admin (talk | contribs) (Created page with "FROM: Hole in Union TO: Triangles Cover Triangle == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2")
- 12:18, 15 February 2023 Reduction from Strips Cover Box to Triangles Cover Triangle (hist | edit) [460 bytes] Admin (talk | contribs) (Created page with "FROM: Strips Cover Box TO: Triangles Cover Triangle == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2")
- 12:18, 15 February 2023 Reduction from Triangles Cover Triangle to Hole in Union (hist | edit) [457 bytes] Admin (talk | contribs) (Created page with "FROM: Triangles Cover Triangle TO: Hole in Union == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2")
- 12:18, 15 February 2023 Reduction from GeomBase to Separator2 (hist | edit) [438 bytes] Admin (talk | contribs) (Created page with "FROM: GeomBase TO: Separator2 == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2")
- 12:18, 15 February 2023 Reduction from GeomBase to Strips Cover Box (hist | edit) [444 bytes] Admin (talk | contribs) (Created page with "FROM: GeomBase TO: Strips Cover Box == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2")
- 12:18, 15 February 2023 Reduction from GeomBase to Separator1 (hist | edit) [438 bytes] Admin (talk | contribs) (Created page with "FROM: GeomBase TO: Separator1 == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2")
- 12:18, 15 February 2023 Reduction from GeomBase to 3SUM' (hist | edit) [433 bytes] Admin (talk | contribs) (Created page with "FROM: GeomBase TO: 3SUM' == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2")
- 12:18, 15 February 2023 Reduction from 3 Points on Line to Point on 3 Lines (hist | edit) [452 bytes] Admin (talk | contribs) (Created page with "FROM: 3 Points on Line TO: Point on 3 Lines == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2")
- 12:18, 15 February 2023 Reduction from 3SUM to 3 Points on Line (hist | edit) [440 bytes] Admin (talk | contribs) (Created page with "FROM: 3SUM TO: 3 Points on Line == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2")
- 12:18, 15 February 2023 Reduction from 3SUM' to 3SUM (hist | edit) [429 bytes] Admin (talk | contribs) (Created page with "FROM: 3SUM' TO: 3SUM == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2")
- 12:18, 15 February 2023 Reduction from 3SUM' to GeomBase (hist | edit) [433 bytes] Admin (talk | contribs) (Created page with "FROM: 3SUM' TO: GeomBase == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2")
- 12:18, 15 February 2023 Reduction from UOV to Longest Common Subsequence (hist | edit) [300 bytes] Admin (talk | contribs) (Created page with "FROM: UOV TO: Longest Common Subsequence == Description == == Implications == If: to-time: $O((nm)^{({1}-\epsilon)})$, where $|x| = O(nd)$ and $|y| = O(md)$<br/>Then: from-time: $O((nm)^{({1}-\epsilon/{2})})$ == Year == 2015 == Reference == https://arxiv.org/pdf/1502.01063.pdf")
- 12:18, 15 February 2023 Reduction from 3SUM to 3SUM' (hist | edit) [429 bytes] Admin (talk | contribs) (Created page with "FROM: 3SUM TO: 3SUM' == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2")
- 12:18, 15 February 2023 Reduction from UOV to Dynamic Time Warping (hist | edit) [294 bytes] Admin (talk | contribs) (Created page with "FROM: UOV TO: Dynamic Time Warping == Description == == Implications == If: to-time: $O((nm)^{({1}-\epsilon)})$, where $|x| = O(nd)$ and $|y| = O(md)$<br/>Then: from-time: $O((nm)^{({1}-\epsilon/{2})})$ == Year == 2015 == Reference == https://arxiv.org/pdf/1502.01063.pdf")
- 12:18, 15 February 2023 Reduction from OV to Partial Match (hist | edit) [332 bytes] Admin (talk | contribs) (Created page with "FROM: OV TO: Partial Match == Description == == Implications == If: to-time: $n^{2-\epsilon}*poly(d)$ for some $\epsilon > {0}$<br/>Then: from-time: $n^{2-\epsilon'}*poly(d)$ for some $\epsilon' > {0}$ == Year == 2020 == Reference == 6.S078 Lecture 6 https://people.csail.mit.edu/virgi/6.s078/lecture6-post.txt")
- 12:18, 15 February 2023 Reduction from Partial Match to OV (hist | edit) [332 bytes] Admin (talk | contribs) (Created page with "FROM: Partial Match TO: OV == Description == == Implications == If: to-time: $n^{2-\epsilon}*poly(d)$ for some $\epsilon > {0}$<br/>Then: from-time: $n^{2-\epsilon'}*poly(d)$ for some $\epsilon' > {0}$ == Year == 2020 == Reference == 6.S078 Lecture 6 https://people.csail.mit.edu/virgi/6.s078/lecture6-post.txt")
- 12:18, 15 February 2023 Reduction from CNF-SAT to Frechet Distance (hist | edit) [495 bytes] Admin (talk | contribs) (Created page with "FROM: CNF-SAT TO: Frechet Distance == Description == == Implications == If: to-time: $O({2}^{({2}-\epsilon)}$ for any $\epsilon > {0}$<br/>Then: from-time: $O({2}^{({1}-\delta/{2})N}$ where $N$ is s.t there are $n=\tilde{O}({2}^{N/2})$ vertices on each curve == Year == 2014 == Reference == Karl Bringmann, Why walking the dog takes time: Fréchet distance has no strongly subquadratic algorithms unless SETH fails https://people.mpi-inf.mpg.de/~kbringm...")
- 12:18, 15 February 2023 Reduction from OV to Edit Distance (hist | edit) [536 bytes] Admin (talk | contribs) (Created page with "FROM: OV TO: Edit Distance == Description == == Implications == If: to-time: $O(n^{({2}-\epsilon)})$ where $n$ is length of sequence<br/>Then: from-time: $O(d^(O({1})*(N)^{({2}-\epsilon)})$ where ${2}$ sets of $n$ $d$-dimensional vectors == Year == 2014 == Reference == Backurs, Arturs, and Piotr Indyk. "Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)." Proceedings of the forty-seventh annual ACM symposium on Theo...")
- 12:18, 15 February 2023 Reduction from CNF-SAT to k-OV (hist | edit) [466 bytes] Admin (talk | contribs) (Created page with "FROM: CNF-SAT TO: k-OV == Description == == Implications == If: to-time: $N^{(k-\epsilon)} poly(m)$ where $m$-dimensional vectors, $k$-OV, $N$ vectors per set<br/>Then: from-time: ${2}^{(n-\epsilon')} \poly(m)$ where $\epsilon' = \epsilon/k > {0}$, $n$ variables, $m$ clauses == Year == 2005 == Reference == Ryan Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. Theor. Comput. Sci., 348(2-3):357–365, 2005.")
- 12:18, 15 February 2023 Reduction from OV to Diameter 2 vs 3 (hist | edit) [506 bytes] Admin (talk | contribs) (Created page with "FROM: OV TO: Diameter 2 vs 3 == Description == == Implications == If: to-time: $O(N^{({2}-\epsilon)})$ where $N = nd$ and $V,E = O(n)$<br/>Then: from-time: $O((nd)^{({2}-\epsilon)}) \leq n^{({2}-\epsilon)} poly(d)$ where {2} sets of $n$ $d$-dimensional vectors == Year == 2013 == Reference == L. Roditty and V. Vassilevska Williams. Fast approximation algorithms for the diameter and radius of sparse graphs. In STOC, pages 515–524, 2013. https://peop...")
- 12:18, 15 February 2023 Reduction from 3-OV to Diameter 3 vs 7 (hist | edit) [469 bytes] Admin (talk | contribs) (Created page with "FROM: 3-OV TO: Diameter 3 vs 7 == Description == == Implications == If: to-time: $O(N^{({3}/{2}-\epsilon)}$ where $N=n^{2} d^{2}$ and $\epsilon > {0}$<br/>Then: from-time: $n^{3-{2}\epsilon} poly(d)$ == Year == 2018 == Reference == Arturs Backurs, Liam Roditty, Gilad Segal, Virginia Vassilevska Williams, and Nicole Wein. Towards tight approximation bounds for graph diameter and eccentricities. https://dl.acm.org/doi/pdf/10.1145/3188745.3188950")
- 12:18, 15 February 2023 Fagin (4NF Decomposition for Functional and Multivalued Dependency Sets 4NF Decomposition) (hist | edit) [350 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == exponential == Space Complexity == exponential words (https://link.springer.com/article/10.1007/BF01934180) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1977 == Reference == https://dl.acm.org/doi/abs/10.1145/320557.320571")
- 12:18, 15 February 2023 Global Newton Method (n player games Nash Equilibria) (hist | edit) [307 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == Unknown == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == == Year == 2008 == Reference == https://www.sciencedirect.com/science/article/pii/S0022053108000811")
- 12:18, 15 February 2023 Sciore (4NF Decomposition for Conflict-Free Dependency Sets 4NF Decomposition) (hist | edit) [285 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == poly-time == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1981 == Reference == https://dl.acm.org/doi/abs/10.1145/582318.582337")
- 12:18, 15 February 2023 Lien (4NF Decomposition for Conflict-Free Dependency Sets 4NF Decomposition) (hist | edit) [387 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(k^{2} n^{2})$ == Space Complexity == $O(k^{2})$ words (Derived: Uses an auxiliary array of size $k \times k$) == Description == Multiway Decomposition Algorithm == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1982 == Reference == https://dl.acm.org/doi/abs/10.1145/319540.319546")
- 12:18, 15 February 2023 Grahne and Räihä (4NF Decomposition for Functional and Multivalued Dependency Sets 4NF Decomposition) (hist | edit) [360 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == exponential == Space Complexity == exponential words (https://link.springer.com/article/10.1007/BF01934180) == Description == Synthesis Algorithm == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1983 == Reference == https://www.vldb.org/conf/1983/P186.PDF")
- 12:18, 15 February 2023 Lipton, Markakis and Mehta method 2 (n player games Nash Equilibria) (hist | edit) [357 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{ck^{2} log (k^{2}n)$/eps^2}) == Space Complexity == $O(k^{2}log^{2} n/eps^{2})$ words () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM words == Year == 2003 == Reference == https://dl.acm.org/doi/10.1145/779928.779933")
- 12:18, 15 February 2023 Mixed Integer Programming (n player games Nash Equilibria) (hist | edit) [292 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == Unknown == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == == Year == 2005 == Reference == https://www.aaai.org/Papers/AAAI/2005/AAAI05-078.pdf")
- 12:18, 15 February 2023 Support enumeration and search (n player games Nash Equilibria) (hist | edit) [293 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == Unknown == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == == Year == 2004 == Reference == https://www.aaai.org/Library/AAAI/2004/aaai04-105.php")
- 12:18, 15 February 2023 Tango Tree ( Self-Balancing Trees Search) (hist | edit) [303 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O((k+{1})$log(log(n))) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2004 == Reference == http://erikdemaine.org/papers/Tango_SICOMP/paper.pdf")
- 12:18, 15 February 2023 Treap ( Self-Balancing Trees Search) (hist | edit) [292 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$? words (^see above) == Description == == Approximate? == Exact == Randomized? == Yes, == Model of Computation == Word RAM == Year == 1989 == Reference == http://faculty.washington.edu/aragon/pubs/rst89.pdf")
- 12:18, 15 February 2023 Lipton, Markakis and Mehta method (2 player games Nash Equilibria) (hist | edit) [340 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{c log n/eps^2})$ == Space Complexity == $O(log^{2} n/eps^{2})$ words () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM words == Year == 2003 == Reference == https://dl.acm.org/doi/10.1145/779928.779933")
- 12:18, 15 February 2023 Blum, Shelton, Koller (Graphical games, Multi-agent influence diagrams Nash Equilibria) (hist | edit) [396 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == Unknown? == Space Complexity == words () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM == Year == 2003 == Reference == https://www.semanticscholar.org/paper/A-Continuation-Method-for-Nash-Equilibria-in-Games-Blum-Shelton/4a3b80041922298db147debc2a2307bc4a5a42e9")
- 12:18, 15 February 2023 Lemke-Howson Algorithm (2 player games Nash Equilibria) (hist | edit) [335 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == Exponential == Space Complexity == $O(mn)$? words (I am not sure if this can be optimized?) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM == Year == 1964 == Reference == https://doi.org/10.1137/0112033")
- 12:18, 15 February 2023 Scapegoat Tree ( Self-Balancing Trees Search) (hist | edit) [322 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O({1})$? words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1989 == Reference == https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.138.4859")
- 12:18, 15 February 2023 Tarjan Splay Tree ( Self-Balancing Trees Search) (hist | edit) [249 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1985 == Reference ==")
- 12:18, 15 February 2023 Scapegoat Tree ( Self-Balancing Trees Deletion) (hist | edit) [318 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$? words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1989 == Reference == https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.138.4859")
- 12:18, 15 February 2023 Treap ( Self-Balancing Trees Deletion) (hist | edit) [292 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$? words (^see above) == Description == == Approximate? == Exact == Randomized? == Yes, == Model of Computation == Word RAM == Year == 1989 == Reference == http://faculty.washington.edu/aragon/pubs/rst89.pdf")
- 12:18, 15 February 2023 Bayer, McCreight B-Tree ( Self-Balancing Trees Search) (hist | edit) [264 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(b*log(n)$/log(b))? == Space Complexity == $O({1})$ words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1970 == Reference ==")
- 12:18, 15 February 2023 AVL Tree ( Self-Balancing Trees Search) (hist | edit) [353 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(logn)$ == Space Complexity == $O({1})$ words (Need to keep track of constant amount of info during search (i.e. which node we're on and what direction to go)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1962 == Reference ==")
- 12:18, 15 February 2023 Bayer, McCreight B-Tree ( Self-Balancing Trees Deletion) (hist | edit) [299 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(b*log(n)$/log(b))? == Space Complexity == $O(b)$? words (^see above, but with branching factor involved) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1970 == Reference ==")
- 12:18, 15 February 2023 Tarjan Splay Tree ( Self-Balancing Trees Deletion) (hist | edit) [249 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1985 == Reference ==")
- 12:18, 15 February 2023 Treap ( Self-Balancing Trees Insertion) (hist | edit) [292 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$? words (^see above) == Description == == Approximate? == Exact == Randomized? == Yes, == Model of Computation == Word RAM == Year == 1989 == Reference == http://faculty.washington.edu/aragon/pubs/rst89.pdf")
- 12:18, 15 February 2023 Scapegoat Tree ( Self-Balancing Trees Insertion) (hist | edit) [318 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$? words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1989 == Reference == https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.138.4859")
- 12:18, 15 February 2023 Bayer, McCreight B-Tree ( Self-Balancing Trees Insertion) (hist | edit) [299 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(b*log(n)$/log(b))? == Space Complexity == $O(b)$? words (^see above, but with branching factor involved) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1970 == Reference ==")
- 12:18, 15 February 2023 AVL Tree ( Self-Balancing Trees Deletion) (hist | edit) [252 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(logn)$ == Space Complexity == $O({1})$ words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1962 == Reference ==")
- 12:18, 15 February 2023 Tarjan Splay Tree ( Self-Balancing Trees Insertion) (hist | edit) [249 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1985 == Reference ==")
- 12:18, 15 February 2023 Scapegoat Tree ( Self-Balancing Trees Creation) (hist | edit) [376 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (Need to keep track of intermediary stages of tree before outputting) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1989 == Reference == https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.138.4859")
- 12:18, 15 February 2023 Babai 1980 (Graph Isomorphism, Bounded Vertex Valences Graph Isomorphism Problem) (hist | edit) [356 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == \exp(n^{\frac{1}{2} + $O({1})$}) == Space Complexity == $O(n^{2})$ words (https://epubs.siam.org/doi/epdf/10.1137/0209018) == Description == == Approximate? == Exact == Randomized? == Yes, Las Vegas == Model of Computation == Word RAM == Year == 1980 == Reference == https://epubs.siam.org/doi/10.1137/0209018")
- 12:18, 15 February 2023 AVL Tree ( Self-Balancing Trees Insertion) (hist | edit) [359 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(logn)$ == Space Complexity == $O({1})$ words (Each node being changed requires constant auxiliary space to make changes; can reuse space across nodes being changed) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1962 == Reference ==")
- 12:18, 15 February 2023 Tango Tree ( Self-Balancing Trees Creation) (hist | edit) [363 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (Need to keep track of intermediary stages of tree before outputting) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2004 == Reference == http://erikdemaine.org/papers/Tango_SICOMP/paper.pdf")
- 12:18, 15 February 2023 Treap ( Self-Balancing Trees Creation) (hist | edit) [350 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (Need to keep track of intermediary stages of tree before outputting) == Description == == Approximate? == Exact == Randomized? == Yes, == Model of Computation == Word RAM == Year == 1989 == Reference == http://faculty.washington.edu/aragon/pubs/rst89.pdf")
- 12:18, 15 February 2023 Babai 1980 (Graph Isomporhism, Trivalent Graphs Graph Isomorphism Problem) (hist | edit) [353 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == \exp(cn^{\frac{1}{2}} \log n) == Space Complexity == $O(n^{2})$ words (https://epubs.siam.org/doi/epdf/10.1137/0209018) == Description == == Approximate? == Exact == Randomized? == Yes, Las Vegas == Model of Computation == Word RAM == Year == 1980 == Reference == https://epubs.siam.org/doi/10.1137/0209018")
- 12:18, 15 February 2023 Nesetril, Poljak (k-Clique k-Clique Problem) (hist | edit) [440 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^(k-({3}-\omega)*floor(k/{3}))$ where omega is the exponent on matrix multiplication == Space Complexity == $O(n^({2}k/{3})$) ish words (matrix sizes) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1985 == Reference == https://dml.cz/bitstream/handle/10338.dmlcz/106381/CommentatMathUnivCarol_026-1985-2_22.pdf")
- 12:18, 15 February 2023 APSP algorithm (3-Clique Min-Weight k-Clique Problem) (hist | edit) [256 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3} / {2}^(log n)$^{0.5}) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == - == Reference == -")
- 12:18, 15 February 2023 Brute force enumeration (k-Clique k-Clique Problem) (hist | edit) [298 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^k)$ == Space Complexity == $O(k)$ auxiliary words (keeping track of which vertices we're looking at) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == - == Reference == -")
- 12:18, 15 February 2023 Reduction to Chan, Williams (k-OV Orthogonal Vectors) (hist | edit) [315 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{(k-{1}/O(d/log(n)))})$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2016 == Reference == https://epubs.siam.org/doi/abs/10.1137/1.9781611974331.ch87")
- 12:18, 15 February 2023 Gronlund, Pettie (3-Clique Exact-Weight k-Clique Problem) (hist | edit) [315 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3}*(log log n)$^{2}/(log n)) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2014 == Reference == https://ieeexplore.ieee.org/abstract/document/6979047")
- 12:18, 15 February 2023 Chan, Williams (OV Orthogonal Vectors) (hist | edit) [317 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{({2}-{1}/O(d/log(n)))})$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2016 == Reference == https://epubs.siam.org/doi/abs/10.1137/1.9781611974331.ch87")
- 12:18, 15 February 2023 Reduction to Abboud, Williams, Yu (k-OV Orthogonal Vectors) (hist | edit) [312 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{(k-{1}/O(d/log(n)))})$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == Yes, Monte Carlo == Model of Computation == Word RAM == Year == 2015 == Reference == https://epubs.siam.org/doi/abs/10.1137/1.9781611973730.17")
- 12:18, 15 February 2023 Exhaustive search (k-OV Orthogonal Vectors) (hist | edit) [299 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(d*n^k)$ == Space Complexity == $O(k)$ auxiliary words (keeping track of which vectors we're looking at) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == - == Reference == -")
- 12:18, 15 February 2023 Exhaustive search (Minimum Wiener Connector problem Wiener Index) (hist | edit) [337 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == {2}^($O(n)$) == Space Complexity == $O(n)$ auxiliary words (Keeps track of current subset being checked, minimum subset, and O(1) Wiener indices) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2015 == Reference ==")
- 12:18, 15 February 2023 Abboud, Williams, Yu (OV Orthogonal Vectors) (hist | edit) [314 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{({2}-{1}/O(d/log(n)))})$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == Yes, Monte Carlo == Model of Computation == Word RAM == Year == 2015 == Reference == https://epubs.siam.org/doi/abs/10.1137/1.9781611973730.17")
- 12:18, 15 February 2023 KALYAN PERUMALLA and NARSINGH DEO (2-dimensional Maximum subarray problem) (hist | edit) [322 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(log n)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == CREW PRAM == Year == 1995 == Reference == https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.24.1291&rep=rep1&type=pdf")
- 12:18, 15 February 2023 Wen (2-dimensional Maximum subarray problem) (hist | edit) [309 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(log n)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == EREW PRAM == Year == 1995 == Reference == https://www.sciencedirect.com/science/article/abs/pii/016781919400063G")
- 12:18, 15 February 2023 Tamaki, Tokuyama (approximate) (2-dimensional Maximum subarray problem) (hist | edit) [357 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^(omega)$ * (-log(epsilon))/epsilon) == Space Complexity == words () == Description == == Approximate? == Approximate Approximation Factor: (1-epsilon) == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1998 == Reference == https://dl.acm.org/doi/pdf/10.5555/314613.314823")
- 12:18, 15 February 2023 Takaoka (2-dimensional Maximum subarray problem) (hist | edit) [350 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3} * ((log log n)$/(log n))^({1}/{2})) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2002 == Reference == https://www.sciencedirect.com/science/article/pii/S1571066104003135?via%3Dihub")
- 12:18, 15 February 2023 Tamaki, Tokuyama (exact) (2-dimensional Maximum subarray problem) (hist | edit) [320 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3} * ((log log n)$/(log n))^({1}/{2})) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1998 == Reference == https://dl.acm.org/doi/pdf/10.5555/314613.314823")
- 12:18, 15 February 2023 Smith (2-dimensional Maximum subarray problem) (hist | edit) [326 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(log n)$ auxiliary? words (divide-and-conquer) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1987 == Reference == https://www.sciencedirect.com/science/article/pii/0167642387900347")
- 12:18, 15 February 2023 Brute force (2-dimensional Maximum subarray problem) (hist | edit) [331 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{6})$ == Space Complexity == $O({1})$ auxiliary words (keep track of which subarray is being computed, along with current maximum) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1977 == Reference == -")
- 12:18, 15 February 2023 Bentley (2-dimensional Maximum subarray problem) (hist | edit) [374 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$ auxiliary? words ((i think you need to pre-process to get cumulative sums in each row?)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1984 == Reference == https://dl.acm.org/doi/pdf/10.1145/1968.381154")
- 12:18, 15 February 2023 Stege, Fellows (The Vertex Cover Problem The Vertex Cover Problem) (hist | edit) [442 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(kn+max(({1.25542})$^k k^{2}, ({1.2906})^k 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 == 1999 == Reference == https://www.research-collection.ethz.ch/bitstream/handle/20.500.11850/69332/eth-4359-01.pdf")
- 12:18, 15 February 2023 Stege, Fellows + Interleaving method (Niedermeier, Rossmanith) (The Vertex Cover Problem The Vertex Cover Problem) (hist | edit) [371 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(kn+({1.2906})$^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://mediatum.ub.tum.de/doc/1094228/file.pdf")
- 12:18, 15 February 2023 Papadimitriou and M Yannakakis 1996 + Buss (The Vertex Cover Problem The Vertex Cover Problem) (hist | edit) [453 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({3}^k k^{2}+kn)$ == 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) auxiliary space at most) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1996 == Reference == https://www.sciencedirect.com/science/article/pii/S0022000096900586")
- 12:18, 15 February 2023 Downey, Fellows (The Vertex Cover Problem The Vertex Cover Problem) (hist | edit) [467 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(kn+{2}^k 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) auxiliary space at most) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1995 == Reference == https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.2.7270&rep=rep1&type=pdf")
- 12:18, 15 February 2023 Exhaustive search (The Vertex Cover Problem The Vertex Cover Problem) (hist | edit) [343 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(C(n, k)$) (i.e. (n, k) binomial coefficient) == 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 ==")
- 12:18, 15 February 2023 Chan (Real 3SUM 3SUM) (hist | edit) [315 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2}*(log log n)$^{$O({1})$}/(log n)^{2}) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 2018 == Reference == https://dl.acm.org/doi/abs/10.1145/3363541")
- 12:18, 15 February 2023 Gronlund, Pettie (Real 3SUM 3SUM) (hist | edit) [312 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2}/((log n)$/(log log n))^{2}/{3}) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 2014 == Reference == https://ieeexplore.ieee.org/abstract/document/6979047")
- 12:18, 15 February 2023 Freund (Real 3SUM 3SUM) (hist | edit) [317 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2}*(log log n)$/(log n)) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 2017 == Reference == https://link.springer.com/article/10.1007/s00453-015-0079-6")
- 12:18, 15 February 2023 Baran, Demaine, Patrascu (Integer 3SUM 3SUM) (hist | edit) [311 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2}/max(w/(log w)$^{2}, (log n)^{2}/(log log n)^{2})) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == Yes, Las Vegas == Model of Computation == Word RAM == Year == 2008 == Reference == https://link.springer.com/article/10.1007/s00453-007-9036-3")
- 12:18, 15 February 2023 Textbook Sort-and-Two-Sided-Traversal (Integer 3SUM 3SUM) (hist | edit) [261 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words (Storing sorted list) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == - == Reference == -")
- 12:18, 15 February 2023 Textbook Sort-and-Binary-Search (Integer 3SUM 3SUM) (hist | edit) [267 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} log n)$ == Space Complexity == $O(n)$ words (Storing sorted list) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == - == Reference == -")
- 12:18, 15 February 2023 Kazuhisa Makino, Takeaki Uno; Section 6 (Enumerating Maximal Cliques, arbitrary graph Clique Problems) (hist | edit) [387 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(delta^{4})$ == Space Complexity == $O(n+m)$ auxiliary(?) words (https://link.springer.com/chapter/10.1007/978-3-540-27810-8_23) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2004 == Reference == https://link.springer.com/chapter/10.1007/978-3-540-27810-8_23")
- 12:18, 15 February 2023 Fischer, Heun (Lowest Common Ancestor with Static Trees Lowest Common Ancestor) (hist | edit) [370 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(m+n)$ == Space Complexity == $O(n)$ words (https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.64.5439) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference == https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.64.5439")
- 12:18, 15 February 2023 Kmett (Lowest Common Ancestor with Static Trees Lowest Common Ancestor) (hist | edit) [296 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(m*log(h)$) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2015 == Reference == https://www.schoolofhaskell.com/user/edwardk/online-lca")
- 12:18, 15 February 2023 Harel, Tarjan (Static Trees) (Lowest Common Ancestor with Static Trees Lowest Common Ancestor) (hist | edit) [424 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n+m)$ == Space Complexity == $O(n)$ words (https://www.cs.bgu.ac.il/~segal/PAPERS2/tarj.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1984 == Reference == https://www.semanticscholar.org/paper/Fast-Algorithms-for-Finding-Nearest-Common-Harel-Tarjan/8867d059dda279b1aed4a0301e4e46f9daf65174")
- 12:18, 15 February 2023 Harel, Tarjan (Linking Roots) (Lowest Common Ancestor with Linking Roots Lowest Common Ancestor) (hist | edit) [487 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n+ m*alpha(m + n, n)$) where alpha is the inverse Ackermann function == Space Complexity == $O(n)$ words (https://www.cs.bgu.ac.il/~segal/PAPERS2/tarj.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1984 == Reference == https://www.semanticscholar.org/paper/Fast-Algorithms-for-Finding-Nearest-Common-Harel-Tarjan/8867d059dda279b1aed4a0301e4e...")
- 12:18, 15 February 2023 Schieber; Vishkin (Parallel) (Lowest Common Ancestor with Static Trees Lowest Common Ancestor) (hist | edit) [413 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(m+log(n)$) == Space Complexity == $O(n)$ total (auxiliary?) words (https://www.proquest.com/docview/919780720?pq-origsite=gscholar&fromopenview=true) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == EREW PRAM == Year == 1988 == Reference == https://epubs.siam.org/doi/abs/10.1137/0217079?journalCode=smjcat")
- 12:18, 15 February 2023 Sleator and Tarjan (Linking and Cutting) (Lowest Common Ancestor with Linking and Cutting Lowest Common Ancestor) (hist | edit) [363 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n+m*log(n)$) == Space Complexity == $O(n)$ words (https://www.cs.bgu.ac.il/~segal/PAPERS2/tarj.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1983 == Reference == https://www.sciencedirect.com/science/article/pii/0022000083900065")
- 12:18, 15 February 2023 Sleator and Tarjan (Linking) (Lowest Common Ancestor with Linking Lowest Common Ancestor) (hist | edit) [363 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n+m*log(n)$) == Space Complexity == $O(n)$ words (https://www.cs.bgu.ac.il/~segal/PAPERS2/tarj.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1983 == Reference == https://www.sciencedirect.com/science/article/pii/0022000083900065")
- 12:18, 15 February 2023 Modified van Leeuwen (Linking Roots) (Lowest Common Ancestor with Linking Roots Lowest Common Ancestor) (hist | edit) [322 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n+m*log(log(n)$)) == Space Complexity == $O(n)$ words (https://www.cs.bgu.ac.il/~segal/PAPERS2/tarj.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == (Unpublished report)")
- 12:18, 15 February 2023 Modified van Leeuwen (Static Trees) (Lowest Common Ancestor with Static Trees Lowest Common Ancestor) (hist | edit) [322 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n+m*log(log(n)$)) == Space Complexity == $O(n)$ words (https://www.cs.bgu.ac.il/~segal/PAPERS2/tarj.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == (Unpublished report)")
- 12:18, 15 February 2023 Brent-Dekker Method (General Root Computation Root Computation) (hist | edit) [539 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_max)$ == Space Complexity == $O({1})$ words (Store previous 3 estimates x_i, x_{i-1}, and x_{i-2} along with function values f_i, f_{i-1}, f_{i-2}; 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 ==...")
- 12:18, 15 February 2023 Aho, Hopcroft, and Ullman (Linking) (Lowest Common Ancestor with Linking Lowest Common Ancestor) (hist | edit) [354 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O((m+n)$*log(n)) == Space Complexity == $O(n*log(n)$) words (https://www.cs.bgu.ac.il/~segal/PAPERS2/tarj.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == https://dl.acm.org/doi/pdf/10.1145/800125.804056")
- 12:18, 15 February 2023 Aho, Hopcroft, and Ullman (Offline) (Off-Line Lowest Common Ancestor Lowest Common Ancestor) (hist | edit) [401 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n+ m*alpha(m + n, n)$) where alpha is the inverse Ackermann function == Space Complexity == $O(n)$ words (https://www.cs.bgu.ac.il/~segal/PAPERS2/tarj.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == https://dl.acm.org/doi/pdf/10.1145/800125.804056")
- 12:18, 15 February 2023 Inverse quadratic interpolation (General Root Computation Root Computation) (hist | edit) [490 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_max)$ == Space Complexity == $O({1})$ words (Store previous 3 estimates x_i, x_{i-1}, and x_{i-2} along with function values f_i, f_{i-1}, f_{i-2}; 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(?)...")
- 12:18, 15 February 2023 Aho, Hopcroft, and Ullman (Static Trees) (Lowest Common Ancestor with Static Trees Lowest Common Ancestor) (hist | edit) [364 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O((m+n)$*log(log(n))) == Space Complexity == $O(n*log(log(n)$)) words (https://www.cs.bgu.ac.il/~segal/PAPERS2/tarj.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == https://dl.acm.org/doi/pdf/10.1145/800125.804056")
- 12:18, 15 February 2023 Steffensen's method (General Root Computation Root Computation) (hist | edit) [416 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_max)$ == Space Complexity == $O({1})$ words (Store previous estimate x_i; iterations take O(1) time and thus O(1) space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1940(?) == Reference ==")
- 12:18, 15 February 2023 Anderson–Björck algorithm (General Root Computation Root Computation) (hist | edit) [470 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_max)$ == Space Complexity == $O({1})$ words (Store current endpoint values; iterations take O(1) time and thus O(1) space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1973 == Reference == https://link.springer.com/article/10.1007/BF01951936")
- 12:18, 15 February 2023 Householder's Method (Root Computation with continuous derivatives (up to d) Root Computation) (hist | edit) [497 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(d*n_max)$? == Space Complexity == $O(d)$ words (Store current estimate x_i and the derivatives f' through f^{(d)} (assuming these take O(1) space each); iterations take O(1) time and thus O(1) space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1940(?...")
- 12:18, 15 February 2023 ITP Method (General Root Computation Root Computation) (hist | edit) [437 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_0+log((b-a)$/epsilon)) == Space Complexity == $O({1})$ words (Store current endpoint values; iterations take O(1) time and thus O(1) space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1940? == Reference == -")
- 12:18, 15 February 2023 Illinois Algorithm (General Root Computation Root Computation) (hist | edit) [470 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_max)$ == Space Complexity == $O({1})$ words (Store current endpoint values; iterations take O(1) time and thus O(1) space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1971 == Reference == https://link.springer.com/article/10.1007/BF01934364")
- 12:18, 15 February 2023 Gabow (general Maximum-weight matching) (hist | edit) [341 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1974 == Reference == https://www.proquest.com/docview/287948024?pq-origsite=gscholar&fromopenview=true")
- 12:18, 15 February 2023 Fredman-Tarjan (Edmonds-Karp-based) (bipartite (i.e. assignment), general Maximum-weight matching) (hist | edit) [309 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn+n^{2}log(n)$) == Space Complexity == $O(n^{2})$ words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1984 == Reference == https://dl.acm.org/doi/10.1145/28869.28874")
- 12:18, 15 February 2023 Gabow, Galil, Spencer (general Maximum-weight matching) (hist | edit) [332 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn*log(log(log(n)$/log({2}+m/n))) + n^{2}*log(n)) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1989 == Reference == https://ieeexplore.ieee.org/abstract/document/715935")
- 12:18, 15 February 2023 Johnson (Edmonds-Karp-based) (bipartite (i.e. assignment), general Maximum-weight matching) (hist | edit) [341 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn*log(n)$/log({2}+m/n)) == Space Complexity == $O(n^{2})$ words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1975 == Reference == https://www.sciencedirect.com/science/article/pii/0020019075900010")
- 12:18, 15 February 2023 Edmonds-Karp (bipartite (i.e. assignment), general Maximum-weight matching) (hist | edit) [581 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*(SP+))$ where $(SP+)$ denotes the time for one SSSP computation on a nonnegatively weighted graph. Initially $O(n^{3})$ == Space Complexity == $O(n^{2})$ words (Keeps track of current flow, which is of size O(n^2), and an O(n)-sized labeling function. SSSP computation has time bounded by O(n^2) and thus should use O(n^2) space at most) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Co...")
- 12:18, 15 February 2023 Galil, Micali, Gabow (general Maximum-weight matching) (hist | edit) [323 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn*log(n)$) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1982 == Reference == https://www.proquest.com/docview/919855909?pq-origsite=gscholar&fromopenview=true")
- 12:18, 15 February 2023 Ives' algorithm c ( All permutations) (hist | edit) [392 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({1})$ per permutation == Space Complexity == $O(n)$ auxiliary words (O(n) words needed to keep track of which elements have cycled how many times) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == https://dl.acm.org/doi/abs/10.1145/359997.360002")
- 12:18, 15 February 2023 Zaks' prefix reversal algorithm ( All permutations) (hist | edit) [422 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ on specific permutations == Space Complexity == $O(n)$ auxiliary (see NEXT algorithm in same paper) words (https://link.springer.com/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")
- 12:18, 15 February 2023 Langdon ( All permutations) (hist | edit) [391 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ per permutation == Space Complexity == $O({1})$ auxiliary words (Only need the auxiliary variable N, according to the flowchart in the paper) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1967 == Reference == https://dl.acm.org/doi/pdf/10.1145/363282.363315")
- 12:18, 15 February 2023 Divide and Conquer ( Minimum value in each row of an implicitly-defined totally monotone matrix) (hist | edit) [402 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(m*log(n)$) == Space Complexity == $O(log(n)$) auxiliary? words (Need to keep track of the specific indices where the minimums occur, up to depth log(n)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1987 == Reference == https://link.springer.com/article/10.1007/BF01840359")
- 12:18, 15 February 2023 Wells ( All permutations) (hist | edit) [367 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({1})$ per permutation == Space Complexity == $O(n)$ auxiliary words (O(n)-sized array for t_k's necessary) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1961 == Reference == https://www.jstor.org/stable/2004229#metadata_info_tab_contents")
- 12:18, 15 February 2023 Ord-Smith ( All permutations) (hist | edit) [358 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({1})$ per permutation == Space Complexity == $O(n)$ auxiliary words (O(n)-sized array q (as in paper) necessary) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1967 == Reference == https://dl.acm.org/doi/pdf/10.1145/362896.362913")
- 12:18, 15 February 2023 Blossom Algorithm (general graph Maximum cardinality matching) (hist | edit) [498 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{2}E)$ == Space Complexity == $O(E)$ auxiliary? words (Manipulates a constant number of graphs? Contractions can be kept track of in O(E) space) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM == Year == 1961 == Reference == https://www.cambridge.org/core/journals/canadian-journal-of-mathematics/article/paths-trees-and-flowers/08B492B72...")
- 12:18, 15 February 2023 Micali, Vazirani (general graph Maximum cardinality matching) (hist | edit) [409 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{0.5} E)$ == Space Complexity == $O(E)$ auxiliary? words (Manipulates a constant number of graphs? Contractions can be kept track of in O(E) space) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM == Year == 1980 == Reference == https://ieeexplore.ieee.org/document/4567800")
- 12:18, 15 February 2023 Masek, Paterson (Edit sequence, constant-size alphabet Sequence Alignment) (hist | edit) [410 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn/log(n)$) == Space Complexity == $O(mn/log(n)$) words (https://www.sciencedirect.com/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")
- 12:18, 15 February 2023 Alt, Blum, Mehlhorn, Paul (bipartite graph Maximum cardinality matching) (hist | edit) [433 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{1.5}*(E/logV)$^{0.5}) == Space Complexity == $O(E)$ auxiliary? words (Uses constant number of O(E)-sized data structures in pseudocode of algorithm) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM == Year == 1991 == Reference == https://www.sciencedirect.com/science/article/pii/002001909190195N")
- 12:18, 15 February 2023 Wagner-Fischer algorithm (Edit sequence, constant-size alphabet Sequence Alignment) (hist | edit) [334 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(mn)$ words (https://dl.acm.org/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")
- 12:18, 15 February 2023 Wagner-Fischer algorithm (Edit distance, constant-size alphabet Sequence Alignment) (hist | edit) [303 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(m)$ words (Easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1974 == Reference == https://dl.acm.org/doi/abs/10.1145/321796.321811")
- 12:18, 15 February 2023 Wu and Manber, Fuzzy String Matching ( String Search) (hist | edit) [433 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nk \lceil m/w \rceil)$ == Space Complexity == $O(ms + k \lceil m/w \rceil)$ (https://dl.acm.org/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")
- 12:18, 15 February 2023 D* Lite ( Informed Search) (hist | edit) [308 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(b^d)$ == Space Complexity == $O(b^d)$ (Stores all generated nodes in memory) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2005 == Reference == https://doi.org/10.1109%2Ftro.2004.838026")
- 12:18, 15 February 2023 Focused D* ( Informed Search) (hist | edit) [331 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(b^d)$ == Space Complexity == $O(b^d)$ (Stores all generated nodes in memory) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2005 == Reference == https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.8257")
- 12:18, 15 February 2023 Shi 2009 (NAE 3SAT Boolean Satisfiability) (hist | edit) [480 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({12}m*t_extract + {2}m*t_discard + {2}n*t_append + (n+{2}m)$*t_merge + (n-{1})*t_amplify) == Space Complexity == $O(n)$ tubes or $O({2}^n)$ library strands (https://ieeexplore.ieee.org/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...")
- 12:18, 15 February 2023 Hertli (Modified PPSZ) (4SAT Boolean Satisfiability) (hist | edit) [319 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({1.46899}^n)$ == Space Complexity == $O(kn)$ words (Not sure, please look) == Description == == Approximate? == Exact == Randomized? == Yes, Monte Carlo == Model of Computation == Word RAM == Year == 2014 == Reference == https://epubs.siam.org/doi/abs/10.1137/120868177")
- 12:18, 15 February 2023 Hertli (Modified PPSZ) (3SAT Boolean Satisfiability) (hist | edit) [319 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({1.30704}^n)$ == Space Complexity == $O(kn)$ words (Not sure, please look) == Description == == Approximate? == Exact == Randomized? == Yes, Monte Carlo == Model of Computation == Word RAM == Year == 2014 == Reference == https://epubs.siam.org/doi/abs/10.1137/120868177")
- 12:18, 15 February 2023 Anytime Dynamic A* (ADA*) ( Informed Search) (hist | edit) [353 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(b^d)$ == Space Complexity == $O(b^d)$ (Stores all generated nodes in memory) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2005 == Reference == https://www.ri.cmu.edu/publications/anytime-dynamic-a-an-anytime-replanning-algorithm/")
- 12:18, 15 February 2023 Quantum Adiabatic Algorithm (QAA) (CNF-SAT Boolean Satisfiability) (hist | edit) [310 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O(poly(n)$) qubits () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Quantum == Year == 2001 == Reference == https://arxiv.org/pdf/quant-ph/0001106.pdf")
- 12:18, 15 February 2023 Lewis 1978 (Renamable Horn Boolean Satisfiability) (hist | edit) [270 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn^{2})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1978 == Reference == https://dl.acm.org/doi/10.1145/322047.322059")
- 12:18, 15 February 2023 Paturi, Pudlák, Saks, Zane (PPSZ) 2005 (k-SAT Boolean Satisfiability) (hist | edit) [317 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == O^*({2}^{n-cn/k}) == Space Complexity == $O(kn)$ words (Derived in notes) == Description == == Approximate? == Exact == Randomized? == Yes, Monte Carlo == Model of Computation == Word RAM == Year == 2005 == Reference == https://dl.acm.org/doi/abs/10.1145/1066100.1066101")
- 12:17, 15 February 2023 GSAT (CNF-SAT Boolean Satisfiability) (hist | edit) [327 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*mt*mf)$ == Space Complexity == $O(n)$ (derived in notes) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == == Year == 1992 == Reference == http://www.cs.cornell.edu/selman/papers/pdf/92.aaai.gsat.pdf")
- 12:17, 15 February 2023 WalkSAT (CNF-SAT Boolean Satisfiability) (hist | edit) [316 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*mt*mf)$ == Space Complexity == $O(n)$ (same as above) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == == Year == 1994 == Reference == https://www.aaai.org/Papers/AAAI/1994/AAAI94-051.pdf")
- 12:17, 15 February 2023 Conflict-Driven Clause Learning (CDCL) (CNF-SAT Boolean Satisfiability) (hist | edit) [268 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1999 == Reference == https://ieeexplore.ieee.org/document/769433")
- 12:17, 15 February 2023 Johnson's algorithm (Directed, Weighted (Arbitrary weights) All-Pairs Shortest Paths (APSP)) (hist | edit) [298 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{2} log V + VE)$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == == Year == 1977 == Reference == https://dl.acm.org/doi/10.1145/321992.321993")
- 12:17, 15 February 2023 Davis-Putnam-Logemann-Loveland Algorithm (DPLL) (CNF-SAT Boolean Satisfiability) (hist | edit) [337 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O(n)$ Binary Search Tree (https://en.wikipedia.org/wiki/DPLL_algorithm) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1961 == Reference == https://dl.acm.org/doi/10.1145/368273.368557")
- 12:17, 15 February 2023 Zwick 2002 (Directed, Unweighted All-Pairs Shortest Paths (APSP)) (hist | edit) [277 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{2.575})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2002 == Reference == https://dl.acm.org/doi/abs/10.1145/567112.567114")
- 12:17, 15 February 2023 Binary representation search with matrix multiplication (Unweighted Graph Diameter) (hist | edit) [337 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^omega log(V)$) where omega is the exponent on matrix multiplication == Space Complexity == $O(V^{2} logV)$ words (storing all the matrices) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == - == Reference == -")
- 12:17, 15 February 2023 Dense APSP algorithm (Arbitrary edge weights, Dense graph Graph Diameter) (hist | edit) [255 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{3} / {2}^(logV)$^{0.5}) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == - == Reference == -")
- 12:17, 15 February 2023 Sparse APSP algorithm (Arbitrary edge weights, Sparse graph Graph Diameter) (hist | edit) [243 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{2}logV+VE)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == - == Reference == -")
- 12:17, 15 February 2023 Not frequently used (NFU) (Online Page Replacements) (hist | edit) [292 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nk)$? == Space Complexity == $O(k)$ words (Need to keep track of cache + reference counters only) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 12:17, 15 February 2023 ARIES (Steal, No-Force Recovery) (hist | edit) [470 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$? words (Uses write-ahead logging, so keeps track of transaction log, whose entries may be augmented with O(1) more information each. During recovery, needs to keep track of variable/page states) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1992 == Reference == https://dl.acm.org/doi/10.1145/128765.128770")
- 12:17, 15 February 2023 Aging (Online Page Replacements) (hist | edit) [292 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nk)$? == Space Complexity == $O(k)$ words (Need to keep track of cache + reference counters only) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 12:17, 15 February 2023 Random (Online Page Replacements) (hist | edit) [254 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(k)$? words (Need to keep track of cache?) == Description == == Approximate? == Exact == Randomized? == Yes, == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 12:17, 15 February 2023 Longest distance first (LDF) page replacement algorithm (Online Page Replacements) (hist | edit) [539 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nk)$? == Space Complexity == $O(k)$ words (Need to keep track of cache + information related to position of pages) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2017 == Reference == https://www.researchgate.net/profile/Gyanendra-Kumar-3/publication/319467661_A_Novel_Longest_Distance_First_Page_Replacement_Algorithm/links/59b209f1aca2728472d146...")
- 12:17, 15 February 2023 Second-chance (Online Page Replacements) (hist | edit) [288 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nk)$? == Space Complexity == $O(k)$ words (Need to keep track of cache + reference bits only) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 12:17, 15 February 2023 First-in, first-out (Online Page Replacements) (hist | edit) [288 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nk)$? == Space Complexity == $O(k)$ words (Need to keep track of cache + reference bits only) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 12:17, 15 February 2023 Clock (Online Page Replacements) (hist | edit) [304 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nk)$? == Space Complexity == $O(k)$ words (Need to keep track of cache + reference bits only (plus iterator)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 12:17, 15 February 2023 Least recently used (Online Page Replacements) (hist | edit) [325 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nk)$? == Space Complexity == $O(k)$ words (Need to keep track of cache + info related to time last referenced for each of k pages) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 12:17, 15 February 2023 Not recently used (Online Page Replacements) (hist | edit) [288 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nk)$? == Space Complexity == $O(k)$ words (Need to keep track of cache + reference bits only) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 12:17, 15 February 2023 Work-conserving schedulers (Unweighted Interval Scheduling, Online?? Interval Scheduling) (hist | edit) [231 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 12:17, 15 February 2023 Banker's Algorithm (Deadlock Avoidance Deadlock avoidance) (hist | edit) [444 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn^{2})$ == Space Complexity == $O(mn)$ words (Main space-consuming arrays needed include "Max," "Allocation," and "Need," which are all n*m arrays. Other arrays are either O(n) or O(m)-sized) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1966 == Reference == https://www.cs.utexas.edu/users/EWD/ewd01xx/EWD108.PDF")
- 12:17, 15 February 2023 Round-robin scheduling (Unweighted Interval Scheduling, Online?? Interval Scheduling) (hist | edit) [250 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n+k)$? words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 12:17, 15 February 2023 Multilevel queue scheduling (Unweighted Interval Scheduling, Online?? Interval Scheduling) (hist | edit) [288 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n+k)$? words (^see above; also level information for each task) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 12:17, 15 February 2023 The theoretically optimal page replacement algorithm (Offline Page Replacements) (hist | edit) [370 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(k)$ words (Need to keep track of cache; linear scan for searching for page not being used for the longest only requires O(1) auxiliary space) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 12:17, 15 February 2023 Fixed priority shortest job first (Unweighted Interval Scheduling, Online?? Interval Scheduling) (hist | edit) [391 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n+k)$? words (Keep track of (sorted, based on criteria) list of (unscheduled, running, etc.; just un-done) tasks, along with machine statuses and task priorities) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 12:17, 15 February 2023 Shortest remaining time first (Unweighted Interval Scheduling, Online?? Interval Scheduling) (hist | edit) [250 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n+k)$? words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 12:17, 15 February 2023 $O(n^2)$ Dynamic Programming (Weighted Activity Selection Problem Interval Scheduling) (hist | edit) [320 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words (Keep track of answers to O(n) subproblems (cache), and sorted list of intervals) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1953 == Reference ==")
- 12:17, 15 February 2023 Priority scheduling (Unweighted Interval Scheduling, Online?? Interval Scheduling) (hist | edit) [367 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n+k)$? words (Keep track of (sorted, based on criteria) list of (unscheduled, running, etc.; just un-done) tasks, along with machine statuses) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 12:17, 15 February 2023 First come, first served (Unweighted Interval Scheduling, Online?? Interval Scheduling) (hist | edit) [250 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n+k)$? words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 12:17, 15 February 2023 $O(n\log n)$ Dynamic Programming (Weighted Activity Selection Problem Interval Scheduling) (hist | edit) [323 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (Keep track of answers to O(n) subproblems (cache), and sorted list of intervals) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1953 == Reference ==")
- 12:17, 15 February 2023 Lehmer's GCD algorithm (Greatest Common Divisor Greatest Common Divisor) (hist | edit) [352 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ bits (Store only the current values being iterated on, and an O(1)-sized matrix with O(n)-bit numbers) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? words size O(1) == Year == 1940 == Reference ==")
- 12:17, 15 February 2023 Euclid's algorithm (Greatest Common Divisor Greatest Common Divisor) (hist | edit) [304 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ bits (Store only the current values being iterated on) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? words size O(1) == Year == -300 == Reference ==")
- 12:17, 15 February 2023 Brute force algorithm (Weighted Activity Selection Problem Interval Scheduling) (hist | edit) [292 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O(n)$ words (Need to keep track of which subset is being checked) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 12:17, 15 February 2023 $O(n^3)$ Dynamic Programming (Weighted Activity Selection Problem Interval Scheduling) (hist | edit) [295 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$ words (Keep track of answers to O(n^2) subproblems (i, j)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1953 == Reference ==")
- 12:17, 15 February 2023 Sthele, Zimmermann (Greatest Common Divisor Greatest Common Divisor) (hist | edit) [389 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n log^{2} n log log n)$ == Space Complexity == $O(n)$?? bits (Depends on Schonhage-Strassen multiplication) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? words size O(1) == Year == 2006 == Reference == https://hal.inria.fr/file/index/docid/71533/filename/RR-5050.pdf")
- 12:17, 15 February 2023 Binary GCD algorithm (Greatest Common Divisor Greatest Common Divisor) (hist | edit) [338 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ bits (Store only the current values being iterated on) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? words size O(1) == Year == 1967 == Reference == https://arxiv.org/abs/0910.0095")
- 12:17, 15 February 2023 Bjorck (2-D Polynomial Interpolation Polynomial Interpolation) (hist | edit) [399 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words (https://academic.oup.com/imajna/article/8/4/473/758789?login=true) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1970 == Reference == https://www.jstor.org/stable/2004623?origin=crossref&seq=5#metadata_info_tab_contents")
- 12:17, 15 February 2023 Calvetti, Reichel (2-D Polynomial Interpolation Polynomial Interpolation) (hist | edit) [349 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$? words ((maybe similar to the other O(n^2) algorithms?)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1993 == Reference == https://link.springer.com/article/10.1007/BF01990529")
- 12:17, 15 February 2023 Higham (2-D Polynomial Interpolation Polynomial Interpolation) (hist | edit) [379 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words (https://academic.oup.com/imajna/article/8/4/473/758789?login=true) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1988 == Reference == https://academic.oup.com/imajna/article/8/4/473/758789?login=true")
- 12:17, 15 February 2023 Blowfish (Block Ciphers Block Ciphers) (hist | edit) [416 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$? bits (Network has a constant number of rounds and operates on O(n) bits, thus structure should require O(n) bits to describe) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1993 == Reference == https://link.springer.com/chapter/10.1007/3-540-58108-1_24")
- 12:17, 15 February 2023 Gaussian elimination (2-D Polynomial Interpolation Polynomial Interpolation) (hist | edit) [316 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$ words (Requires computation of inverse of O(n^2)-sized Vandermonde matrix) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == -150 == Reference ==")
- 12:17, 15 February 2023 Rijndael / AES (Block Ciphers Block Ciphers) (hist | edit) [529 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$? bits (Network generally operates on the O(n) bits over O(k) rounds, each round having roughly the same structure (so structure of rounds require O(1) bits to describe)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2001 == Reference == https://csrc.nist.gov/csrc/media/projects/cryptographic-standards-and-guid...")
- 12:17, 15 February 2023 Newton's method (Solutions to Nonlinear Equations Solutions to Nonlinear Equations) (hist | edit) [422 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_max)$ == Space Complexity == $O({1})$ words (Store current estimate x_i and the derivative f' (assuming this takes O(1) space); iterations take O(1) time and thus O(1) space, and space can be re-used across iterations) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1669 == Reference ==")
- 12:17, 15 February 2023 IDEA (Block Ciphers Block Ciphers) (hist | edit) [254 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$? bits ((^see above)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1991 == Reference == NA")
- 12:17, 15 February 2023 Lucifer / DES (Block Ciphers Block Ciphers) (hist | edit) [360 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$? bits (Network has a constant number of rounds and operates on O(n) bits, thus structure should require O(n) bits to describe) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == NA")
- 12:17, 15 February 2023 RC5 (Block Ciphers Block Ciphers) (hist | edit) [465 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(k+rw)$? bits (Requires additional O(k/w)-length array of O(w)-size words (temporary working array) and O(r)-length array of O(w)-size words, as key-independent pseudorandom array.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1994 == Reference == https://link.springer.com/chapter/10.1007/3-540-60590-8_7")
- 12:17, 15 February 2023 Bisection method (Solutions to Nonlinear Equations Solutions to Nonlinear Equations) (hist | edit) [370 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_max)$ == Space Complexity == $O({1})$ words (Store current endpoint values; iterations take O(1) time and thus O(1) space, and space can be re-used across iterations) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == -150 == Reference ==")
- 12:17, 15 February 2023 Secant method (Solutions to Nonlinear Equations Solutions to Nonlinear Equations) (hist | edit) [384 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_max)$ == Space Complexity == $O({1})$ words (Store previous 2 estimates x_i and x_{i-1}; iterations take O(1) time and thus O(1) space, and space can be re-used across iterations) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == -1400 == Reference ==")
- 12:17, 15 February 2023 Regula Falsi method (Solutions to Nonlinear Equations Solutions to Nonlinear Equations) (hist | edit) [370 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_max)$ == Space Complexity == $O({1})$ words (Store current endpoint values; iterations take O(1) time and thus O(1) space, and space can be re-used across iterations) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == -200 == Reference ==")
- 12:17, 15 February 2023 BLAKE2 (Optional Key? One-Way Hash Functions) (hist | edit) [374 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary? bits (Generally processes the message in O(1)-sized chunks; parameters into the "compress" function are also technically O(1)-sized) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2012 == Reference ==")
- 12:17, 15 February 2023 Shamir's scheme ( Secret Sharing) (hist | edit) [481 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(t^{2})$ for secret computation? (requires polynomial interpolation) == Space Complexity == $O({1})$ per person, $O(t^{2})$ to figure out secret? words (Each person only needs to keep track of a single point (O(1) info); figuring out secret depends on polynomial interpolation algorithm) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1979 == Refere...")
- 12:17, 15 February 2023 SHA-3 (Unkeyed Hash Functions One-Way Hash Functions) (hist | edit) [463 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(b+d)$ auxiliary? bits (only need constant padding, O(b)-bit "absorb" state being manipulated, constant-sized non-linear functions (i.e. operating on O(1) bits), and O(d)-sized "squeezed" state being manipulated. In practice b, d are O(1)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2015 == Reference ==")
- 12:17, 15 February 2023 SHA-2 (Unkeyed Hash Functions One-Way Hash Functions) (hist | edit) [299 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary? bits (Based off of Merkel-Damgard construction (see MD5)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2001 == Reference ==")
- 12:17, 15 February 2023 Blakley's scheme ( Secret Sharing) (hist | edit) [466 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(t^{3})$ for secret computation? (requires linear solver) == Space Complexity == $O(t)$ per person, $O(t^{2})$ to figure out secret words (Each person needs to keep track of coefficients of hyperplane; figuring out secret requires O(t) hyperplanes, with O(t) coefficients) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1979 == Reference ==")
- 12:17, 15 February 2023 Whirlpool ( One-Way Hash Functions) (hist | edit) [299 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary? bits (Based off of Merkel-Damgard construction (see MD5)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2000 == Reference ==")
- 12:17, 15 February 2023 RIPEMD-160 (Unkeyed Hash Functions One-Way Hash Functions) (hist | edit) [306 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary? bits (Likely based off of Merkel-Damgard construction (see MD5)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1996 == Reference ==")
- 12:17, 15 February 2023 SHA-1 (Unkeyed Hash Functions One-Way Hash Functions) (hist | edit) [299 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary? bits (Based off of Merkel-Damgard construction (see MD5)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1993 == Reference ==")
- 12:17, 15 February 2023 Bcrypt (Unkeyed Hash Functions One-Way Hash Functions) (hist | edit) [287 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary?? bits (generally operates in the O(1) scheme) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1999 == Reference ==")
- 12:17, 15 February 2023 Naive Implementation ( Integral Equations) (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 == 1800 == Reference ==")
- 12:17, 15 February 2023 MD5 (Unkeyed Hash Functions One-Way Hash Functions) (hist | edit) [426 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary? bits (only need constant padding, 128-bit state being manipulated, and constant-sized non-linear functions (i.e. operating on O(1) bits). Also based off of Merkle-Damgard construction) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1991 == Reference ==")
- 12:17, 15 February 2023 Naive solution (The Frequent Words Problem The Frequent Words Problem) (hist | edit) [311 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(max(n, sigma^k)$) auxiliary words (Keep track of counts on at most n-k+1 or sigma^k words) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 12:17, 15 February 2023 Rabin Karp (The Frequent Words Problem The Frequent Words Problem) (hist | edit) [312 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(max(n, sigma^k)$) auxiliary? words (Keep track of counts on at most n-k+1 or sigma^k words) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1987 == Reference ==")
- 12:17, 15 February 2023 Gray-code based (Tower of Hanoi Tower of Hanoi) (hist | edit) [298 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O(n)$ auxiliary bits (Need to keep track of an n-bit counter for Gray codes) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == NA")
- 12:17, 15 February 2023 Hanoi graph (Tower of Hanoi Tower of Hanoi) (hist | edit) [317 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == bits () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2008 == Reference == https://books.google.com/books/about/Topics_in_Graph_Theory.html?id=pSv3XotPCQgC")
- 12:17, 15 February 2023 Recursion based (Tower of Hanoi Tower of Hanoi) (hist | edit) [378 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O(n*log n)$ auxiliary bits (Need to keep track of an O(n)-sized recursive stack, each entry requiring O(log n) space (i.e. which tower size to manipulate)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == NA")
- 12:17, 15 February 2023 Non-recursion based (Tower of Hanoi Tower of Hanoi) (hist | edit) [293 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O(n)$ auxiliary bits (Only need to keep track of current configuration) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == NA")
- 12:17, 15 February 2023 Naive Solution (Median String Problem with Unbounded Alphabets Median String Problem) (hist | edit) [384 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == {2}^$O(n)$ == Space Complexity == $O(n)$ auxiliary words (Keep track of current string being checked, current best string, and Levenshtein distances (which can be computed recursively using O(n) space)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1965 == Reference ==")
- 12:17, 15 February 2023 Iteration based (Tower of Hanoi Tower of Hanoi) (hist | edit) [293 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O(n)$ auxiliary bits (Only need to keep track of current configuration) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1883 == Reference == NA")
- 12:17, 15 February 2023 Gunther Determinants solution (Counting Solutions; Constructing solutions n-Queens Problem) (hist | edit) [381 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n!)$ == Space Complexity == $O(n!)$ ? words (Seems like this one lists out all of the terms in the discriminant; presumably there is a better way but that amounts to the naive algorithm) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1874 == Reference ==")
- 12:17, 15 February 2023 Naive solution ( Frequent Words with Mismatches Problem) (hist | edit) [456 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*f_{bin}(sigma-{1}, k, d)$) where f_{bin}(x, y, z) = sum_{i=0}^z C(y, i)*x^i == Space Complexity == $O(max(n*f_{bin}(sigma-{1}, k, d)$, sigma^k)) auxiliary where f_{bin}(x, y, z) = sum_{i=0}^z C(y, i)*x^i words (Keep track of counts on at most that many words) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 12:17, 15 February 2023 Rivin, Zabih (Counting Solutions n-Queens Problem) (hist | edit) [362 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({8}^n*poly(n)$) == Space Complexity == $O({8}^n*n^{2})$ words (http://www.cs.cornell.edu/~rdz/Papers/RZ-IPL92.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1992 == Reference == http://www.cs.cornell.edu/~rdz/Papers/RZ-IPL92.pdf")
- 12:17, 15 February 2023 Dijkstra (Counting Solutions; Constructing solutions n-Queens Problem) (hist | edit) [408 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n!)$ == Space Complexity == $O(n)$ words (Keep track of current configuration being tested and restrictions on where next queen can be placed, along with current count) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1972 == Reference == https://dl.acm.org/citation.cfm?id=1243380")
- 12:17, 15 February 2023 Naive Algorithm (Counting Solutions; Constructing solutions n-Queens Problem) (hist | edit) [313 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^n)$ == Space Complexity == $O(n)$ words (Keep track of current configuration being tested, along with current count) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1848 == Reference ==")
- 12:17, 15 February 2023 Outside-In algorithm (Turnpike Problem Turnpike Problem) (hist | edit) [330 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n nlogn)$ == Space Complexity == $O(n)$ words (Seems like this just needs to keep track of current configuration being tested) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1991 == Reference == NA")
- 12:17, 15 February 2023 Naive + 1 queen per row restriction (Counting Solutions; Constructing solutions n-Queens Problem) (hist | edit) [312 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n!)$ == Space Complexity == $O(n)$ words (Keep track of current configuration being tested, along with current count) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1850 == Reference ==")
- 12:17, 15 February 2023 Nauck (Counting Solutions; Constructing solutions n-Queens Problem) (hist | edit) [232 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n!)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1850 == Reference ==")
- 12:17, 15 February 2023 Gries, Martin (Transitive Reduction Problem of Directed Graphs Transitive Reduction Problem) (hist | edit) [433 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$ words (Generally keeps track of O(1) information for every pair (u, v) of vertices? and not much additional information needed) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1989 == Reference == https://www.sciencedirect.com/science/article/pii/0167642389900397")
- 12:17, 15 February 2023 Aho, Garey & Ullman (Transitive Reduction Problem of Directed Graphs Transitive Reduction Problem) (hist | edit) [333 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^omega)$ where omega is the exponent on boolean matrix multiplication == Space Complexity == $O(n^{2})$ words (see (boolean) matrix multiplication) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1972 == Reference == https://epubs.siam.org/doi/pdf/10.1137/0201008")
- 12:17, 15 February 2023 Guibas, Sedgewick Red-Black Tree ( Self-Balancing Trees Search) (hist | edit) [402 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(logn)$ == Space Complexity == $O({1})$ words (Need to keep track of constant amount of info during search (i.e. which node we're on and what direction to go)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1972 == Reference == https://ieeexplore.ieee.org/document/4567957")
- 12:17, 15 February 2023 Hopcroft 2-3 Tree ( Self-Balancing Trees Deletion) (hist | edit) [254 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(logn)$ == Space Complexity == $O({1})$ words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1970 == Reference ==")
- 12:17, 15 February 2023 Guibas, Sedgewick Red-Black Tree ( Self-Balancing Trees Deletion) (hist | edit) [301 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(logn)$ == Space Complexity == $O({1})$ words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1972 == Reference == https://ieeexplore.ieee.org/document/4567957")
- 12:17, 15 February 2023 Hopcroft 2-3 Tree ( Self-Balancing Trees Search) (hist | edit) [355 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(logn)$ == Space Complexity == $O({1})$ words (Need to keep track of constant amount of info during search (i.e. which node we're on and what direction to go)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1970 == Reference ==")
- 12:17, 15 February 2023 Bayer, McCreight B-Tree ( Self-Balancing Trees Creation) (hist | edit) [323 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*b*log(n)$/log(b))? == Space Complexity == $O(n)$ words (Need to keep track of intermediary stages of tree before outputting) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1970 == Reference ==")
- 12:17, 15 February 2023 Guibas, Sedgewick Red-Black Tree ( Self-Balancing Trees Insertion) (hist | edit) [301 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(logn)$ == Space Complexity == $O({1})$ words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1972 == Reference == https://ieeexplore.ieee.org/document/4567957")
- 12:17, 15 February 2023 Hopcroft 2-3 Tree ( Self-Balancing Trees Insertion) (hist | edit) [361 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(logn)$ == Space Complexity == $O({1})$ words (Each node being changed requires constant auxiliary space to make changes; can reuse space across nodes being changed) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1970 == Reference ==")
- 12:17, 15 February 2023 Hopcroft 2-3 Tree ( Self-Balancing Trees Creation) (hist | edit) [311 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (Need to keep track of intermediary stages of tree before outputting) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1970 == Reference ==")
- 12:17, 15 February 2023 Tarjan Splay Tree ( Self-Balancing Trees Creation) (hist | edit) [311 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (Need to keep track of intermediary stages of tree before outputting) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1985 == Reference ==")
- 12:17, 15 February 2023 Guibas, Sedgewick Red-Black Tree ( Self-Balancing Trees Creation) (hist | edit) [358 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (Need to keep track of intermediary stages of tree before outputting) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1972 == Reference == https://ieeexplore.ieee.org/document/4567957")
- 12:17, 15 February 2023 AVL Tree ( Self-Balancing Trees Creation) (hist | edit) [311 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (Need to keep track of intermediary stages of tree before outputting) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1962 == Reference ==")
- 12:17, 15 February 2023 Pollard's kangaroo algorithm (Discrete Logarithm Over Finite Fields Logarithm Calculations) (hist | edit) [481 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O({1})$ words (Stores a constant number of O(n)-bit values (a, b, x_i, d, x_N, y_i, d_i) per iteration; assumes that the pseudorandom map is part of the input) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1978 == Reference == https://www.ams.org/mcom/1978-32-143/S0025-5718-1978-0491431-9/S0025-5718-1978-0491431...")
- 12:17, 15 February 2023 Pollard's rho algorithm (Discrete Logarithm Over Finite Fields Logarithm Calculations) (hist | edit) [403 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^{(n/{2})})$ == Space Complexity == $O({1})$ words (Stores a constant number of O(n)-bit values per iteration) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1978 == Reference == https://www.ams.org/mcom/1978-32-143/S0025-5718-1978-0491431-9/S0025-5718-1978-0491431-9.pdf")
- 12:17, 15 February 2023 Pohlig-Hellman (Discrete Logarithm Over Finite Fields Logarithm Calculations) (hist | edit) [551 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^{\sqrt{n}})$, only for primes; does much better for composites == Space Complexity == $O({2}^{\sqrt{n}})$ (though only for primes) words (A step in the algorithm involves using baby-steps giant-steps to compute discrete logs; the rest of the algorithm (including CRT and repeated powers) isn't as intensive) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM ==...")
- 12:17, 15 February 2023 Number Field Sieve (NFS) (Discrete Logarithm Over Finite Fields Logarithm Calculations) (hist | edit) [335 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O(n^{2/3})$ bits (http://www.ams.org/notices/199612/pomerance.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1990 == Reference == http://www.ams.org/notices/199612/pomerance.pdf")
- 12:17, 15 February 2023 Index calculus algorithm (Discrete Logarithm Over Finite Fields, F q Logarithm Calculations) (hist | edit) [414 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(e^{(\sqrt({2}) \sqrt(n*logn))})$ == Space Complexity == $O(n+r^{2})$? bits (See Dixon's algorithm for factoring integers; also works with an O(r)-by-O(r) sized matrix (to obtain discrete logs of primes in factor base)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == RAM? == Year == 1922 == Reference == NA")
- 12:17, 15 February 2023 Baby-step Giant-step (Discrete Logarithm Over Finite Fields Logarithm Calculations) (hist | edit) [338 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^{\sqrt{n}})$ == Space Complexity == $O({2}^{\sqrt{n}})$ words (Derived: Uses a hash table of this size) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1971 == Reference == https://doi.org/10.1090/pspum/020")
- 12:17, 15 February 2023 Function Field Sieve (FFS) (Discrete Logarithm Over Finite Fields Logarithm Calculations) (hist | edit) [342 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O(n^{2/3})$? bits (Derived: same space as Number Field Sieve?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1999 == Reference == https://www.sciencedirect.com/science/article/pii/S0890540198927614")
- 12:17, 15 February 2023 Jain, Chang (Sequence-to-Graph Alignment Sequence-to-Graph Alignment) (hist | edit) [358 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(|V | + m|E|)$ == Space Complexity == $O(V)$ words (https://www.biorxiv.org/content/10.1101/522912v1.full.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2019 == Reference == https://www.biorxiv.org/content/10.1101/522912v1.full.pdf")
- 12:17, 15 February 2023 Trial Multiplication (Discrete Logarithm Over Finite Fields Logarithm Calculations) (hist | edit) [430 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O({1})$ words (Derived: Each power $k$ that you try in the brute force search is size $O(\log n)$, which is $O(1)$ when considering $O(\log n)$ size words. Only need to keep track of one at a time.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == NA")
- 12:17, 15 February 2023 Rautiainen, Marschall (Sequence-to-Graph Alignment Sequence-to-Graph Alignment) (hist | edit) [499 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(|V | + m|E|)$ == Space Complexity == $O(mV)$ words (Derived: algorithm uses a V-sized array of bitvectors each of which is of length m, and also uses a priority queue which has at most V elements. The precomputed pattern bitvectors also takes up O(V * m) space.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2019 == Reference == https://www.ncb...")
- 12:17, 15 February 2023 V-ALIGN (Sequence-to-Graph Alignment Sequence-to-Graph Alignment) (hist | edit) [369 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(m|V |E|)$ == Space Complexity == $O(mV)$ words (https://www.biorxiv.org/content/10.1101/124941v1.full) == Description == Dynamic Programming == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2018 == Reference == https://www.biorxiv.org/content/10.1101/124941v1.full")
- 12:17, 15 February 2023 Rautiainen and Marschall (Sequence-to-Graph Alignment Sequence-to-Graph Alignment) (hist | edit) [348 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(|V | + m|E|)$ == Space Complexity == $O(\sqrt(m)|V|)$ words (same paper) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2017 == Reference == https://www.biorxiv.org/content/10.1101/216127v1")
- 12:17, 15 February 2023 HybridSpades (Sequence-to-Graph Alignment Sequence-to-Graph Alignment) (hist | edit) [306 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(m(|V | log(m|V |)$ + |E|)) == Space Complexity == $O(m*(V+E)$) words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2015 == Reference == https://www.ncbi.nlm.nih.gov/pubmed/26589280")
- 12:17, 15 February 2023 Navarro (Sequence-to-Graph Alignment Sequence-to-Graph Alignment) (hist | edit) [382 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n(|V | + |E|)$) == Space Complexity == $O(V)$ words (same paper) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2000 == Reference == https://www.sciencedirect.com/science/article/pii/S0304397599003333")
- 12:17, 15 February 2023 Amir et al. (Sequence-to-Graph Alignment Sequence-to-Graph Alignment) (hist | edit) [380 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(m(|n | log |m | + |E|)$) == Space Complexity == $O(mn)$ words (https://reader.elsevier.com/reader/sd/pii/S0304397599003333?token=C0E6BDF7BA98CD5C338EDB86675CB3A29AF44F5B046E169EE0F115788255757C815F0F0307EAF080CDF9A9DE7AA37764) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1997 == Reference == https://link.springer.com/chapter/10.1007/3-540-633...")
- 12:17, 15 February 2023 PSLQ algorithm (Integer Relation Integer Relation) (hist | edit) [431 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$ words (Derived: Uses multiple nxn auxiliary matrices) == Description == Partial Sum of Squares using QR decomposition == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1992 == Reference == https://www.ams.org/journals/mcom/1999-68-225/S0025-5718-99-00995-3/S0025-5718-99-00995-3.pdf")
- 12:17, 15 February 2023 PSOS algorithm (Integer Relation Integer Relation) (hist | edit) [416 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$ words (Derived: Uses multiple nxn auxiliary matrices) == Description == Partial Sum of Squares == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1988 == Reference == https://www.ams.org/journals/mcom/1989-53-188/S0025-5718-1989-0979934-9/S0025-5718-1989-0979934-9.pdf")
- 12:17, 15 February 2023 LLL algorithm (Integer Relation Integer Relation) (hist | edit) [399 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{4})$ == Space Complexity == $O(n^{2})$ words (Derived: Uses n auxiliary vectors each of length n, as well as an nxn matrix) == Description == Lattice-based == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1982 == Reference == https://www.math.leidenuniv.nl/~hwl/PUBLICATIONS/1982f/art.pdf")
- 12:17, 15 February 2023 Ferguson–Forcade algorithm (Integer Relation Integer Relation) (hist | edit) [388 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$ words (Derived: Uses auxiliary $n\times n$ matrices) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1979 == Reference == https://www.ams.org/journals/bull/1979-01-06/S0273-0979-1979-14691-3/S0273-0979-1979-14691-3.pdf")
- 12:17, 15 February 2023 Bareiss algorithm (Determinant of Matrices with Integer Entries Determinant of Matrices with Integer Entries) (hist | edit) [507 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{5}L^{2} (log(n)$^{2} + L^{2})) == Space Complexity == $O(n^{2}(n*log(n)$+nL)) bits (Keeps track of $O(n^2)$ entries that have absolute value at most $O(n^{(n/2)}2^{(nL)})$) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? (without O(1) multiplication) == Year == 1968 == Reference == https://www.ams.org/journals/mcom/1968-22-103/S0025-5718-1968-0226829-0...")
- 12:17, 15 February 2023 Bareiss algorithm with fast multiplication (Determinant of Matrices with Integer Entries Determinant of Matrices with Integer Entries) (hist | edit) [413 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{4}L(log(n)$ + L)log(log(n) + L)) == Space Complexity == $O(n^{2}(n*log(n)$+nL)) bits (Keeps track of $O(n^2)$ entries that have absolute value at most $O(n^{(n/2)}2^{(nL)})$) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? (without O(1) multiplication) == Year == 1968 == Reference == -")
- 12:16, 15 February 2023 Ruchansky (Minimum Wiener Connector problem Wiener Index) (hist | edit) [452 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(q(m*log(n)$+n*log^{2}(n))) == Space Complexity == $O(q(m+n*log(n)$)? words (Keeps track of $O(qm)$ shortest-path distances and $O(q*log(n))$ approximate Steiner trees, each of size $O(n)$) == Description == == Approximate? == Approximate Approximation Factor: O(1) == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2015 == Reference == https://arxiv.org/abs/1504.00513")
- 12:16, 15 February 2023 Dunning; Gupta & Silberholz (Maximum Cut, Approximate Maximum Cut) (hist | edit) [297 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(VE)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2018 == Reference == https://pubsonline.informs.org/doi/epdf/10.1287/ijoc.2017.0798")
- 12:16, 15 February 2023 PINKALL U.; POLTHIER K 1993 (Mesh Parameterization Mesh Parameterization) (hist | edit) [274 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1993 == Reference == http://www.cs.jhu.edu/~misha/Fall09/Pinkall93.pdf")
- 12:16, 15 February 2023 LEE Y.; KIM H. S.; LEE S 2002 (Mesh Parameterization Mesh Parameterization) (hist | edit) [302 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n log^{3}n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2002 == Reference == https://www.sciencedirect.com/science/article/abs/pii/S0097849302001231")
- 12:16, 15 February 2023 ECK M.; DEROSE T.; DUCHAMP T.; 1995 (Mesh Parameterization Mesh Parameterization) (hist | edit) [269 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1995 == Reference == https://dl.acm.org/doi/10.1145/218380.218440")
- 12:16, 15 February 2023 FLOATER 1997 (Mesh Parameterization Mesh Parameterization) (hist | edit) [274 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1997 == Reference == http://www.cs.jhu.edu/~misha/Fall09/Floater97.pdf")
- 12:16, 15 February 2023 P. Costantini; B. I. Kvasov; and C. Manni 1999 (Hyperbolic Spline Interpolation Hyperbolic Spline Interpolation) (hist | edit) [409 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{5} logK)$ == Space Complexity == $O(n)$? words (Derived: Pentadiagonal matrix in the linear system only requires O(n) space) == Description == Pentadiagonal linear system == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1999 == Reference == https://link.springer.com/article/10.1023/A:1018988312596")
- 12:16, 15 February 2023 B. I. Kvasov 2000 (Hyperbolic Spline Interpolation Hyperbolic Spline Interpolation) (hist | edit) [222 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{4})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2000 == Reference ==")
- 12:16, 15 February 2023 V. A. Lyul’ka and I. E. Mikhailov 2003 (Hyperbolic Spline Interpolation Hyperbolic Spline Interpolation) (hist | edit) [316 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{4})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2003 == Reference == http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=zvmmf&paperid=943&option_lang=eng")
- 12:16, 15 February 2023 V. I. Paasonen 1968 (Hyperbolic Spline Interpolation Hyperbolic Spline Interpolation) (hist | edit) [227 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{5} logK)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1968 == Reference ==")
- 12:16, 15 February 2023 Duplicate Elimination Sorted Neighborhood Algorithm (DE-SNA) (Duplicate Elimination Duplicate Elimination) (hist | edit) [225 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2002 == Reference ==")
- 12:16, 15 February 2023 V. A. Lyul’ka and A. V. Romanenko 1994 (Hyperbolic Spline Interpolation Hyperbolic Spline Interpolation) (hist | edit) [261 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{5})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1994 == Reference == https://www.mathnet.ru/eng/zvmmf2544")
- 12:16, 15 February 2023 Adaptive Duplicate Detection Algorithm (ADD) (Duplicate Elimination Duplicate Elimination) (hist | edit) [384 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O({1})$ words (Derived: For SVM, only need to store a constant number of support vectors) == Description == SVM string similarity == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2003 == Reference == https://dl.acm.org/doi/10.1145/956750.956759")
- 12:16, 15 February 2023 Kvasov 2006 (Hyperbolic Spline Interpolation Hyperbolic Spline Interpolation) (hist | edit) [293 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3} log^{2}K)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2008 == Reference == https://link.springer.com/article/10.1134/S0965542508040039")
- 12:16, 15 February 2023 Sorted Neighborhood Algorithm (SNA) (Duplicate Elimination Duplicate Elimination) (hist | edit) [362 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words (Derived: store a key for each entry in the "Create Key" phase) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1998 == Reference == https://link.springer.com/article/10.1023/A:1009761603038")
- 12:16, 15 February 2023 Priority Queue Algorithm (Duplicate Elimination Duplicate Elimination) (hist | edit) [331 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words (Derived: Auxiliary space needed for the priority queue) == Description == Selection sort using priority queue? == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference ==")
- 12:16, 15 February 2023 Sorting based (Merge Sort) + real-time elimination (Duplicate Elimination Duplicate Elimination) (hist | edit) [225 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1964 == Reference ==")
- 12:16, 15 February 2023 BST Algorithm (Duplicate Elimination Duplicate Elimination) (hist | edit) [302 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(\log n)$ words (Derived: Space required for the recursion stack space) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1999 == Reference ==")
- 12:16, 15 February 2023 Berger & Müller-Hannemann (DAG Realization Problem Graph Realization Problems) (hist | edit) [272 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(\exp(n)$) == Space Complexity == ? words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2011 == Reference == https://arxiv.org/abs/1203.3636")
- 12:16, 15 February 2023 Sorting based (Merge Sort) (Duplicate Elimination Duplicate Elimination) (hist | edit) [279 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (Derived: linear space for mergesort) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1964 == Reference ==")
- 12:16, 15 February 2023 Fulkerson–Chen–Anstee (Digraph Realization Problem Graph Realization Problems) (hist | edit) [841 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ words (Derived: Checking an inequality that involves 3 summations, of max value $O(n^2)$ each (assuming max degree $\leq n$) which is $O(1)$ words in our Word RAM. We check this inequality for each $k = 1, \ldots, n$, but you can store the summations dynamically, so you only need to run $O(1)$ operations per iteration) == Description == Makes use of (0,1) matrix properties, checks a property of the inp...")
- 12:16, 15 February 2023 Muzychuk (Circulant graphs Graph Isomorphism Problem) (hist | edit) [341 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (derived in notes) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2004 == Reference == https://londmathsoc.onlinelibrary.wiley.com/doi/abs/10.1112/S0024611503014412")
- 12:16, 15 February 2023 Kleitman–Wang Algorithm (Digraph Realization Problem Graph Realization Problems) (hist | edit) [425 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ words (Derived: Space complexity bounded by time complexity; keep track of a constant number of sets of size $O(n)$) == Description == Constructs graph == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1973 == Reference == https://linkinghub.elsevier.com/retrieve/pii/0012365X7390037X")
- 12:16, 15 February 2023 Bodlaender (Partial k-trees Graph Isomorphism Problem) (hist | edit) [317 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{(k+{4.5})})$ == Space Complexity == check words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1990 == Reference == https://www.sciencedirect.com/science/article/pii/0196677490900135")
- 12:16, 15 February 2023 Babai & Codenotti (Hypergraphs isomorphism Graph Isomorphism Problem) (hist | edit) [295 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $exp(O(k^{2} \sqrt{n})$ == Space Complexity == check words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2008 == Reference == https://oa.mg/work/10.1109/focs.2008.80")
- 12:16, 15 February 2023 Schmidt & Druffel ( Graph Isomorphism Problem) (hist | edit) [307 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*n!)$ == Space Complexity == $O(n^{2})$ words (derived in sheet) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == https://dl.acm.org/doi/10.1145/321958.321963")
- 12:16, 15 February 2023 Ullman (Subgraph Isomorphism Graph Isomorphism Problem) (hist | edit) [259 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1976 == Reference == https://dl.acm.org/doi/10.1145/321921.321925")
- 12:16, 15 February 2023 Babai ( Graph Isomorphism Problem) (hist | edit) [342 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == {2}^{$O(\log n)$^3} == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2017 == Reference == http://people.cs.uchicago.edu/~laci/update.html, http://people.cs.uchicago.edu/~laci/17groups/version2.1.pdf")
- 12:16, 15 February 2023 Babai (Graph Isomorphism, Bounded Number of Vertices of Each Color Graph Isomorphism Problem) (hist | edit) [364 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == o(\exp({2}n^{1/2}\log^{2}n)) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1980 == Reference == https://epubs.siam.org/doi/10.1137/0209018")
- 12:16, 15 February 2023 Spielman (Isomorphism of strongly regular graphs Graph Isomorphism Problem) (hist | edit) [315 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $n^{O(n^{({1}/{3})} log n)}$ == Space Complexity == check words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1996 == Reference == https://www.cs.yale.edu/homes/spielman/PAPERS/srg.pdf")
- 12:16, 15 February 2023 McKay ( Graph Isomorphism Problem) (hist | edit) [338 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O((m1 + m2)n^{3} + m2 n^{2} L)$ == Space Complexity == ${2}mn+{10}n+m+(m+{4})K+{2}mL$ words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1981 == Reference == http://users.cecs.anu.edu.au/~bdm/papers/pgi.pdf")
- 12:16, 15 February 2023 Demand-Driven Register Allocation (Global Register Allocation Register Allocation) (hist | edit) [401 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (Derived: Requires storing a so-called $\Delta$-table of size $n \times n$ to keep track of $\Delta$-estimates) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1996 == Reference == https://dl.acm.org/doi/10.1145/236114.236117")
- 12:16, 15 February 2023 Babai and Luks (Graph Isomorphism, General Graphs Graph Isomorphism Problem) (hist | edit) [349 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == \exp(n^{\frac{1}{2} + o({1})}) == Space Complexity == words () == Description == Construct canonical forms of graphs and compare == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1983 == Reference == https://dl.acm.org/doi/10.1145/800061.808746")
- 12:16, 15 February 2023 Sethi–Ullman Algorithm (Arithmetic Expression Binary Tree AST to Code Translation) (hist | edit) [368 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ words (Derived: Only uses in-situ updates to the input tree, no auxiliary data structures) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1970 == Reference == https://dl.acm.org/doi/10.1145/321607.321620")
- 12:16, 15 February 2023 Jeuring (Longest Palindromic Substring Longest Palindromic Substring) (hist | edit) [377 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ auxiliary? words (Stores (and uses) previously computed palindrome information; unclear if O(n) is best bound possible) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1994 == Reference == https://doi.org/10.1007%2FBF01182773")
- 12:16, 15 February 2023 Gusfield (Longest Palindromic Substring Longest Palindromic Substring) (hist | edit) [537 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ auxiliary words (At the very least it pre-processes and stores the string and the reverse of the string, requiring O(n) space. Space usage is bounded from above by runtime, so at most O(n) space is used.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1997 == Reference == https://www.cambridge.org/core/books/al...")
- 12:16, 15 February 2023 Manacher (Longest Palindromic Substring Longest Palindromic Substring) (hist | edit) [432 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ auxiliary words (At the very least it stores the radii for each center, requiring O(n) space. Space usage is bounded from above by runtime, so at most O(n) space is used.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1975 == Reference == https://doi.org/10.1145%2F321892.321896")
- 12:16, 15 February 2023 Dynamic Programming (Longest Palindromic Substring Longest Palindromic Substring) (hist | edit) [314 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (https://www.geeksforgeeks.org/longest-palindrome-substring-set-1/) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1953 == Reference == -")
- 12:16, 15 February 2023 Record linking (Entity Resolution Entity Resolution) (hist | edit) [223 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2}k)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1993 == Reference ==")
- 12:16, 15 February 2023 Naive (Longest Palindromic Substring Longest Palindromic Substring) (hist | edit) [312 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O({1})$ auxiliary words (https://www.geeksforgeeks.org/longest-palindrome-substring-set-1/) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == -")
- 12:16, 15 February 2023 Bellare Active Learning (Entity Resolution Entity Resolution) (hist | edit) [327 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} logn clogc)$ == Space Complexity == () == Description == Pairwise ER Active Learning == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2012 == Reference == https://dl.acm.org/doi/10.1145/2339530.2339707")
- 12:16, 15 February 2023 Chen Ensembles of classifiers (Entity Resolution Entity Resolution) (hist | edit) [242 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} logn)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1989 == Reference ==")
- 12:16, 15 February 2023 Ravikumar & Cohen Generative Models (Entity Resolution Entity Resolution) (hist | edit) [333 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} k)$ == Space Complexity == $O(k)$ words (Derived: One value per feature in the discretized vector) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2004 == Reference == https://arxiv.org/abs/1207.4180")
- 12:16, 15 February 2023 Ananthakrishna (Entity Resolution Entity Resolution) (hist | edit) [426 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} k)$ == Space Complexity == $O(n)$ words (Derived: the token table, the children table, and the tuples in G are stored in main memory, each are of size $O(n)$) == Description == Delphi algorithm == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2002 == Reference == https://doi.org/10.1016/B978-155860869-6/50058-5")
- 12:16, 15 February 2023 EM Based Winkler (Entity Resolution Entity Resolution) (hist | edit) [376 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3}k)$ == Space Complexity == $O(k)$ words (Derived: One value per feature in the discretized vector) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2000 == Reference == https://courses.cs.washington.edu/courses/cse590q/04au/papers/WinklerEM.pdf")
- 12:16, 15 February 2023 Fellegi & Sunter Model (Entity Resolution Entity Resolution) (hist | edit) [450 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3}k)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1969 == Reference == https://www.tandfonline.com/doi/abs/10.1080/01621459.1969.10501049")
- 12:16, 15 February 2023 McCreight (Constructing Suffix Trees Constructing Suffix Trees) (hist | edit) [376 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ words (Needs to store the intermediate steps of constructing a suffix tree, which can reach size O(n)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == http://libeccio.di.unisa.it/TdP/suffix.pdf")
- 12:16, 15 February 2023 Rytter (Constructing Suffix Trees Constructing Suffix Trees) (hist | edit) [472 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(logn)$ == Space Complexity == $O(n)$ words (https://www.researchgate.net/publication/228945502_On_parallel_transformations_of_suffix_arrays_into_suffix_trees) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == CREW PRAM == Year == 2004 == Reference == https://www.researchgate.net/publication/228945502_On_parallel_transformations_of_suffix_arrays_into_suffix_trees")
- 12:16, 15 February 2023 Farach (Constructing Suffix Trees Constructing Suffix Trees) (hist | edit) [361 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(log n)$ == Space Complexity == $O(n)$ words (https://www.cs.rutgers.edu/~farach/pubs/PRAMSuffixICALP.pdf) == Description == == Approximate? == Exact == Randomized? == Yes, Las Vegas == Model of Computation == CRCW PRAM == Year == 1997 == Reference == https://www.cs.rutgers.edu/~farach/pubs/PRAMSuffixICALP.pdf")
- 12:16, 15 February 2023 Gupta & Sarawagi CRF (Entity Resolution Entity Resolution) (hist | edit) [428 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3}k)$ == Space Complexity == () == Description == Bipartite method to compute pairwise ER == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2009 == Reference == https://doi.org/10.14778/1687627.1687661")
- 12:16, 15 February 2023 Süleyman Cenk Sahinalp ; Uzi Vishkin (Constructing Suffix Trees Constructing Suffix Trees) (hist | edit) [415 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(log^{2}(n)$) == Space Complexity == $O(n^{({1}+\eps)})$ for any fixed eps>{0} words (https://link.springer.com/content/pdf/10.1007/3-540-57811-0_3.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == CRCW PRAM == Year == 1994 == Reference == https://link.springer.com/content/pdf/10.1007/3-540-57811-0_3.pdf")
- 12:16, 15 February 2023 Hariharan (Constructing Suffix Trees Constructing Suffix Trees) (hist | edit) [384 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(log^{4}(n)$) == Space Complexity == $O(n)$ words (https://www.sciencedirect.com/science/article/pii/S0022000097914963) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == CREW PRAM == Year == 1997 == Reference == https://www.sciencedirect.com/science/article/pii/S0022000097914963")
- 12:16, 15 February 2023 Ukkonen and D. Wood (Constructing Suffix Trees Constructing Suffix Trees) (hist | edit) [352 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (https://link.springer.com/article/10.1007/BF01769703) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1993 == Reference == https://link.springer.com/article/10.1007/BF01769703")
- 12:16, 15 February 2023 Pratt (Constructing Suffix Trees Constructing Suffix Trees) (hist | edit) [235 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1973 == Reference == -")
- 12:16, 15 February 2023 Ukkonen (Constructing Suffix Trees Constructing Suffix Trees) (hist | edit) [391 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ words (Needs to store the intermediate steps of constructing a suffix tree, which can reach size O(n)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1995 == Reference == https://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf")
- 12:16, 15 February 2023 Weiner's algorithm (Constructing Suffix Trees Constructing Suffix Trees) (hist | edit) [376 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ words (Needs to store the intermediate steps of constructing a suffix tree, which can reach size O(n)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1973 == Reference == https://dl.acm.org/citation.cfm?id=1441766")
- 12:16, 15 February 2023 Naive (Constructing Suffix Trees Constructing Suffix Trees) (hist | edit) [339 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words (Needs to store the intermediate steps of constructing a suffix tree, which can reach size O(n)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1973 == Reference == -")
- 12:16, 15 February 2023 Ioannidou; Kyriaki; Mertzios; George B.; Nikolopoulos; Stavros D. (Longest Path on Interval Graphs Longest Path Problem) (hist | edit) [382 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{4})$ == Space Complexity == $O(n^{3})$ words (https://link.springer.com/content/pdf/10.1007/s00453-010-9411-3.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2011 == Reference == https://community.dur.ac.uk/george.mertzios/papers/Conf/Conf_Longest-Interval.pdf")
- 12:16, 15 February 2023 Unsworth; C.; Prosser; P (Stable Marriage Problem Stable Matching Problem) (hist | edit) [409 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? (see original reference)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2005 == Reference == http://www.dcs.gla.ac.uk/~pat/roommates/distribution/papers/SM2N.pdf")
- 12:16, 15 February 2023 Patrick Posser (Stable Roommates Problem Stable Matching Problem) (hist | edit) [370 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n)$ words (https://link.springer.com/chapter/10.1007%2F978-3-319-07046-9_2) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2014 == Reference == https://link.springer.com/chapter/10.1007%2F978-3-319-07046-9_2")
- 12:16, 15 February 2023 S. S. TSENG and R. C. T. LEE (Stable Marriage Problem Stable Matching Problem) (hist | edit) [377 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ per processor? words (Only need to keep track of current (provisional) matchings) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1984 == Reference == https://link.springer.com/content/pdf/10.1007/BF02136029.pdf")
- 12:16, 15 February 2023 Gent; I.P.; Irving; R.W.; Manlove; D.F.; Prosser; P.; Smith; B.M. (Stable Marriage Problem Stable Matching Problem) (hist | edit) [372 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 == 2001 == Reference == https://link.springer.com/chapter/10.1007/3-540-45578-7_16")
- 12:16, 15 February 2023 Gaussian Elimination (Exact Laplacian Solver SDD Systems Solvers) (hist | edit) [373 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$ words (Derived: Storing the inverse of the Laplacian) == Description == Use Gaussian elimination to compute the inverse of the Laplacian to solve for x == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == -150 == Reference == -")
- 12:15, 15 February 2023 5-point cyclic reduction (2-Dimensional Poisson Problem Poisson Problem) (hist | edit) [340 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} logn)$ == Space Complexity == $O(n^{2})$? words (Generally uses a constant number of n^2*n^2 matrices where O(n^2) entries are nonempty) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1970 == Reference ==")
- 12:15, 15 February 2023 9-point ADI iteration + smooth guess (2-Dimensional Poisson Problem Poisson Problem) (hist | edit) [340 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} logn)$ == Space Complexity == $O(n^{2})$? words (Generally uses a constant number of n^2*n^2 matrices where O(n^2) entries are nonempty) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1969 == Reference ==")
- 12:15, 15 February 2023 9-point FFT (2-Dimensional Poisson Problem Poisson Problem) (hist | edit) [317 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} logn)$ == Space Complexity == $O(n^{2})$? words (FFT generally requires aux. space equal to dimension of vector?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1978 == Reference ==")
- 12:15, 15 February 2023 5-point FFT (2-Dimensional Poisson Problem Poisson Problem) (hist | edit) [317 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} logn)$ == Space Complexity == $O(n^{2})$? words (FFT generally requires aux. space equal to dimension of vector?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1965 == Reference ==")
- 12:15, 15 February 2023 9-point ADI iteration (2-Dimensional Poisson Problem Poisson Problem) (hist | edit) [340 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} logn)$ == Space Complexity == $O(n^{2})$? words (Generally uses a constant number of n^2*n^2 matrices where O(n^2) entries are nonempty) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1965 == Reference ==")
- 12:15, 15 February 2023 5-point ADI iteration (2-Dimensional Poisson Problem Poisson Problem) (hist | edit) [344 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} log^{2}n)$ == Space Complexity == $O(n^{2})$? words (Generally uses a constant number of n^2*n^2 matrices where O(n^2) entries are nonempty) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1955 == Reference ==")
- 12:15, 15 February 2023 9-point Tensor product (2-Dimensional Poisson Problem Poisson Problem) (hist | edit) [382 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$? words (Generally uses a constant number of n^2*n^2 matrices where O(n^2) entries are nonempty) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1964 == Reference == https://epubs.siam.org/doi/pdf/10.1137/0113067")
- 12:15, 15 February 2023 9-point SOR iteration (2-Dimensional Poisson Problem Poisson Problem) (hist | edit) [322 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$? words (Need one auxiliary O(n^2)-sized vector to store guess, and the scalar sigma) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1956 == Reference ==")
- 12:15, 15 February 2023 5-point Gauss Seidel iteration (2-Dimensional Poisson Problem Poisson Problem) (hist | edit) [340 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{4} logn)$ == Space Complexity == $O(n^{2})$? words (Generally uses a constant number of n^2*n^2 matrices where O(n^2) entries are nonempty) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1945 == Reference ==")
- 12:15, 15 February 2023 5-point star Cramer's rule (2-Dimensional Poisson Problem Poisson Problem) (hist | edit) [463 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({4}^{(n^{2})})$ == Space Complexity == $O({4}^{(n^{2})})$ for sure, $O(n^{2})$ possibly??? (if super conservative) words (For expansion by minors, each "level" of expansion requires computing and storing O(1) smaller determinants, and there are O(n^2) levels overall) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1945 == Reference ==")
- 12:15, 15 February 2023 5-point SOR iteration (2-Dimensional Poisson Problem Poisson Problem) (hist | edit) [329 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3} logn)$ == Space Complexity == $O(n^{2})$? words (Need one auxiliary O(n^2)-sized vector to store guess, and the scalar sigma) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1954 == Reference ==")
- 12:15, 15 February 2023 5-point Gauss elimination (2-Dimensional Poisson Problem Poisson Problem) (hist | edit) [305 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{4})$ == Space Complexity == $O(n^{4})$ words (See Gauss-Jordan elimination, but matrix is of size n^2*n^2) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1945 == Reference ==")
- 12:15, 15 February 2023 TSPLIB (Minimum TSP The Traveling-Salesman Problem) (hist | edit) [304 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^V logE)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1991 == Reference == https://pubsonline.informs.org/doi/abs/10.1287/ijoc.3.4.376")
- 12:15, 15 February 2023 Lawler; E. L. (Minimum TSP The Traveling-Salesman Problem) (hist | edit) [306 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({1.674}^V E^{2})$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1985 == Reference == https://onlinelibrary.wiley.com/doi/10.1002/net.3230180309")
- 12:15, 15 February 2023 Christofides algorithm (Approximate TSP The Traveling-Salesman Problem) (hist | edit) [458 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{3})$ == Space Complexity == $O(V^{2})$??? words (Depends on best space complexity for O(V^3) min-weight matching (the rest of the algorithm requires O(V) auxiliary space)) == Description == == Approximate? == Approximate Approximation Factor: 1.5 == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == https://apps.dtic.mil/dtic/tr/fulltext/u2/a025602.pdf")
- 12:15, 15 February 2023 Kazuhisa Makino, Takeaki Uno; Section 5 (Enumerating Maximal Cliques, arbitrary graph Clique Problems) (hist | edit) [441 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{\omega})$ per clique where omega is the exponent on matrix multiplication == Space Complexity == $O(n^{2})$ auxiliary words (https://link.springer.com/chapter/10.1007/978-3-540-27810-8_23) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2004 == Reference == https://link.springer.com/chapter/10.1007/978-3-540-27810-8_23")
- 12:15, 15 February 2023 Shuji Tsukiyama, Mikio Ide, Hiromu Ariyoshi, and Isao Shirakawa (Enumerating Maximal Cliques, arbitrary graph Clique Problems) (hist | edit) [473 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nm)$ per clique == Space Complexity == $O(m)$ auxiliary words (See original reference, but also note that we'd have to construct and store the complementary graph (as this is originally an algo for MISs)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1977 == Reference == https://www.proquest.com/docview/918487776?pq-origsite=gscholar&fromopenv...")
- 12:15, 15 February 2023 Held–Karp algorithm (Minimum TSP The Traveling-Salesman Problem) (hist | edit) [368 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{2} {2}^V)$ == Space Complexity == $O(V*{2}^V)$ words (Need to store all C(S, l) for all subsets $S \subseteq V$ and all vertices l) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1962 == Reference == https://www.jstor.org/stable/2098806")
- 12:15, 15 February 2023 David Eppstein, Maarten Löffler, Darren Strash (Enumerating Maximal Cliques, arbitrary graph Clique Problems) (hist | edit) [368 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(dn {3}^{(d/{3})})$ == Space Complexity == $O(n^{2})$ auxiliary? words (See Bron-Kerbosch, but also keeps track of O(n)-sized degeneracy ordering) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2010 == Reference == https://arxiv.org/pdf/1006.5440.pdf")
- 12:15, 15 February 2023 Chiba and Nishizeki (Enumerating Maximal Cliques, arbitrary graph Clique Problems) (hist | edit) [412 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(a(G)*m)$ per clique == Space Complexity == $O(m)$ auxiliary words (https://pdfs.semanticscholar.org/0d19/245a27bc65a87a8014d5b8a66fb514c8ff0b.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1985 == Reference == https://pdfs.semanticscholar.org/0d19/245a27bc65a87a8014d5b8a66fb514c8ff0b.pdf")
- 12:15, 15 February 2023 M. Chrobak and D. Eppstein (Enumerating Maximal Cliques, arbitrary graph Clique Problems) (hist | edit) [432 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n d^{2} {2}^d)$ == Space Complexity == $O(n)$ auxiliary? words (Keeps track of degeneracy ordering along with vertex and subset being tested (here the subset size is bounded by O(d)=O(n))) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1989 == Reference == https://www.ics.uci.edu/~eppstein/pubs/ChrEpp-TCS-91.pdf")
- 12:15, 15 February 2023 Akkoyunlu; E. A. (Enumerating Maximal Cliques, arbitrary graph Clique Problems) (hist | edit) [390 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({3}^{(n/{3})$}) == Space Complexity == $O(n^{2})$ auxiliary?? words (See Bron-Kerbosch (seems like a similar approach?)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1973 == Reference == http://www.dcs.gla.ac.uk/~pat/jchoco/clique/enumeration/papers/SMJ000001%5B1%5D.pdf")
- 12:15, 15 February 2023 Segundo; Artieda; Strash Parallel (Enumerating Maximal Cliques, arbitrary graph Clique Problems) (hist | edit) [473 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({3}^{(n/{3})})$ total work? (previously this cell said $O(n^{4})$) == Space Complexity == $O(n^{2})$ auxiliary?? words (Keep track of an O(n)-sized recursive stack with O(n)-sized lists as elements? (this algo builds off of Bron-Kerbosch)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2011 == Reference == https://arxiv.org/pdf/1801.00202.pdf")
- 12:15, 15 February 2023 Tomita; Tanaka & Takahashi (Enumerating Maximal Cliques, arbitrary graph Clique Problems) (hist | edit) [374 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({3}^{(n/{3})$}) == Space Complexity == $O(n^{2})$ auxiliary? words (See Bron-Kerbosch (seems like a similar approach?)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference == https://snap.stanford.edu/class/cs224w-readings/tomita06cliques.pdf")
- 12:15, 15 February 2023 Finch (Inexact GED Graph Edit Distance Computation) (hist | edit) [531 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{2} E)$ == Space Complexity == $O(V^{2})$? words (Seems to store/update a constant number of values per pair of nodes (one from each graph)) == Description == energy-based == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1998 == Reference == https://direct.mit.edu/neco/article-pdf/10/7/1873/813998/089976698300017188.pdf?casa_token=nCYv9xO_Cc4AAAAA:EHiG4v8QmQju6u9...")
- 12:15, 15 February 2023 Bron–Kerbosch algorithm (Enumerating Maximal Cliques, arbitrary graph Clique Problems) (hist | edit) [379 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({3}^{(n/{3})})$ == Space Complexity == $O(n^{2})$ auxiliary? words (Keep track of an O(n)-sized recursive stack with O(n)-sized lists as elements?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1973 == Reference == https://dl.acm.org/doi/10.1145/362342.362367")
- 12:15, 15 February 2023 K Riesen (Inexact GED Graph Edit Distance Computation) (hist | edit) [337 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{2})$ == Space Complexity == $O(V)$ words (Space complexity of A*) == Description == A* with bipartite heuristic == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2013 == Reference == https://doi.org/10.1007/978-3-642-38221-5_15")
- 12:15, 15 February 2023 Neuhaus, Riesen, Bunke (Inexact GED Graph Edit Distance Computation) (hist | edit) [363 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{2})$ == Space Complexity == $O(wV)$ words (Derived: number of nodes under consideration at once) == Description == A*-Beamsearch == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference == https://link.springer.com/chapter/10.1007/11815921_17")
- 12:15, 15 February 2023 Tao D; Tang X; Li X et al ( Graph Edit Distance Computation) (hist | edit) [281 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{2})$ == Space Complexity == () == Description == EDH == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2006 == Reference == https://eprints.bbk.ac.uk/id/eprint/443/1/Binder1.pdf")
- 12:15, 15 February 2023 Alberto Sanfeliu and King-Sun Fu ( Graph Edit Distance Computation) (hist | edit) [272 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{3} E^{2})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1983 == Reference == https://doi.org/10.1109/TSMC.1983.6313167")
- 12:15, 15 February 2023 Wang Y-K; Fan K-C; Horng J-T ( Graph Edit Distance Computation) (hist | edit) [288 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V E^{2} loglogE)$ == Space Complexity == () == Description == Genetics-based == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1997 == Reference == https://doi.org/10.1109/3477.604100")
- 12:15, 15 February 2023 Y Bai (Inexact GED Graph Edit Distance Computation) (hist | edit) [417 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{2})$ == Space Complexity == $O(V^{2})$ words (Derived: Auxiliary matrices for the neural network of size VxV) == Description == SimGNN == Approximate? == Approximate Approximation Factor: none stated == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2018 == Reference == https://asset-pdf.scinapse.io/prod/2886034153/2886034153.pdf")
- 12:15, 15 February 2023 L Chang (Inexact GED Graph Edit Distance Computation) (hist | edit) [400 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V E^{2} logV)$ == Space Complexity == $O(V)$ words (Theorem 5.1, and the bound on T_{\leq \delta ...} is V\log V https://doi.org/10.48550/arXiv.1709.06810) == Description == AStar+ == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2017 == Reference == https://doi.org/10.48550/arXiv.1709.06810")
- 12:15, 15 February 2023 Stephen Alstrup, Cyril Gavoille, Haim Kaplan & Theis Rauhe (Lowest Common Ancestor with Static Trees Lowest Common Ancestor) (hist | edit) [362 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n+m)$ == Space Complexity == $O(n)$ words ((see original reference, noting that a word is O(log n) bits)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2004 == Reference == https://link.springer.com/article/10.1007/s00224-004-1155-5")
- 12:15, 15 February 2023 X Chen (Exact GED Graph Edit Distance Computation) (hist | edit) [362 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(VS)$ == Space Complexity == $O(wV^{2})$ words (Theorem 5, https://doi.org/10.1016/j.knosys.2018.10.002) == Description == Beam Stack Search == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2019 == Reference == https://doi.org/10.1016/j.knosys.2018.10.002")
- 12:15, 15 February 2023 Berkman; Vishkin (Lowest Common Ancestor with Static Trees Lowest Common Ancestor) (hist | edit) [333 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n+m)$ ? == Space Complexity == $O(n)$ words (space bounded by pre-processing time) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1993 == Reference == https://apps.dtic.mil/dtic/tr/fulltext/u2/a227803.pdf")
- 12:15, 15 February 2023 Schieber; Vishkin (Lowest Common Ancestor with Static Trees Lowest Common Ancestor) (hist | edit) [372 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n+m)$ == Space Complexity == $O(n)$ words (https://www.proquest.com/docview/919780720?pq-origsite=gscholar&fromopenview=true) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1988 == Reference == https://epubs.siam.org/doi/abs/10.1137/0217079?journalCode=smjcat")
- 12:15, 15 February 2023 Tarjan's off-line lowest common ancestors algorithm (Off-Line Lowest Common Ancestor Lowest Common Ancestor) (hist | edit) [510 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n+m)$ == Space Complexity == $O(n)$ words (https://www.cs.bgu.ac.il/~segal/PAPERS2/tarj.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1984 == Reference == https://www.semanticscholar.org/paper/Fast-Algorithms-for-Finding-Nearest-Common-Harel-Tarjan/8867d059dda279b1aed4a0301e4e46f9daf65174")
- 12:15, 15 February 2023 Brzozowski's algorithm (DFA Minimization DFA Minimization) (hist | edit) [526 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O({2}^n)$ words (http://www.cs.ru.nl/bachelors-theses/2017/Erin_van_der_Veen___4431200___The_Practical_Performance_of_Automata_Minimization_Algorithms.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1963 == Reference == https://www.semanticscholar.org/paper/Canonical-regular-expressions-and-minimal-state-for-...")
- 12:15, 15 February 2023 Almeida & Zeitoun (Cyclic Nontrivial SCCs DFA Minimization DFA Minimization) (hist | edit) [390 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ words (https://www.labri.fr/perso/zeitoun/research/pdf/Almeida-Zeitoun-IPL2008.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2008 == Reference == https://www.labri.fr/perso/zeitoun/research/pdf/Almeida-Zeitoun-IPL2008.pdf")
- 12:15, 15 February 2023 Revuz's algorithm (Acyclic DFA Minimization DFA Minimization) (hist | edit) [381 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ words (https://www.labri.fr/perso/zeitoun/research/pdf/Almeida-Zeitoun-IPL2008.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1992 == Reference == https://www.sciencedirect.com/science/article/pii/0304397592901423")
- 12:15, 15 February 2023 Moore's algorithm (DFA Minimization DFA Minimization) (hist | edit) [371 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} k)$ == Space Complexity == $O(n)$ words (Derived: Auxiliary data structure that keeps track of a 'block' binary variable for each state) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1956 == Reference == https://doi.org/10.2307/2964500")
- 12:15, 15 February 2023 Dekel; Nassimi & Sahni Parallel Implementation (Topological Sorting Topological Sorting) (hist | edit) [652 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O( log² V)$ == Space Complexity == $O(V^{2})$?? words (Their n*n*n cube setup seems to only require each processor to keep track of one entry A(i, j), B(i, j) and propagates the results across the structure, only requiring O(1) auxiliary space per processor. Comparison sorting can be done easily with O(1) auxiliary space per processor.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Comp...")
- 12:15, 15 February 2023 Hopcroft's algorithm (DFA Minimization DFA Minimization) (hist | edit) [374 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(kn \log n)$ == Space Complexity == $O(kn)$ words (https://link.springer.com/content/pdf/10.1007/3-540-54430-5_107.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1971 == Reference == https://www.cs.cmu.edu/~./sutner/CDM/papers/Hopcroft71.pdf")
- 12:15, 15 February 2023 Tarjan's DFS based algorithm (Topological Sorting Topological Sorting) (hist | edit) [353 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V+E)$ == Space Complexity == $O(V)$ auxiliary? words (maintain O(V)-sized recursion stack, along with O(V) marks) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == https://link.springer.com/article/10.1007/BF00268499")
- 12:15, 15 February 2023 Kahn's algorithm (Topological Sorting Topological Sorting) (hist | edit) [332 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V+E)$ == Space Complexity == $O(V)$ auxiliary words (maintain stack of nodes with no incoming edges) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1962 == Reference == https://dl.acm.org/doi/10.1145/368996.369025")
- 12:15, 15 February 2023 Chan's algorithm Parallel Implementation ( Variance Calculations) (hist | edit) [402 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(log n)$ == Space Complexity == $O({1})$ per processor words (Each processor maintains O(1) information related to count, mean, M2) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == EREW(??) PRAM == Year == 1979 == Reference == http://i.stanford.edu/pub/cstr/reports/cs/tr/79/773/CS-TR-79-773.pdf")
- 12:15, 15 February 2023 Two-pass algorithm ( Variance Calculations) (hist | edit) [336 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary words (Maintain number of values, sum of values, and sum of squares of (value minus mean) terms) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1940 == Reference == -")
- 12:15, 15 February 2023 Weighted incremental algorithm ( Variance Calculations) (hist | edit) [460 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary words (Maintains O(1) information (sum of weights, sum of squared weights, weighted sum of values, weighted sum of values squared) that is constantly updated as values are read) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1979 == Reference == https://dl.acm.org/doi/10.1145/359146.359153")
- 12:15, 15 February 2023 Naïve algorithm ( Variance Calculations) (hist | edit) [318 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary words (Maintain number of values, sum of values, and sum of squares of values) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1940 == Reference == -")
- 12:15, 15 February 2023 Welford's Online algorithm ( Variance Calculations) (hist | edit) [420 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary words (Maintains O(1) information (count, mean, M2) that is constantly updated as values are read) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1962 == Reference == http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.302.7503&rep=rep1&type=pdf")
- 12:15, 15 February 2023 Bowyer–Watson algorithm (Voronoi Diagrams Voronoi Diagrams) (hist | edit) [409 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ auxiliary words (Computes the Delaunay triangulation first (O(n) space), then uses that to generate the Voronoi diagram) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1981 == Reference == https://academic.oup.com/comjnl/article/24/2/167/338200")
- 12:15, 15 February 2023 Linde–Buzo–Gray algorithm ( Voronoi Diagrams) (hist | edit) [291 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1980 == Reference == https://ieeexplore.ieee.org/document/1094577/")
- 12:15, 15 February 2023 Kong and Wilken Algorithm (Global Register Allocation Register Allocation) (hist | edit) [368 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == ? Probably also dependent on the ILP solver () == Description == Integer programming for irregular register architectures == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1998 == Reference == https://dl.acm.org/doi/10.5555/290940.291002")
- 12:15, 15 February 2023 Optimal Register Allocation (ORA), Goodwin & Wilken Algorithm (Global Register Allocation Register Allocation) (hist | edit) [478 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == Depends on the choice of {0}-{1} ILP solver ("Memory usage is dominated by the usage of the integer program solver.") == Description == 0-1 integer linear programming problem == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1996 == Reference == https://onlinelibrary.wiley.com/doi/abs/10.1002/%28SICI%291097-024X%28199608%2926%3A8%3C929%3A%3AA...")
- 12:15, 15 February 2023 Fortune's algorithm (Voronoi Diagrams Voronoi Diagrams) (hist | edit) [413 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ auxiliary words (https://www.wias-berlin.de/people/si/course/files/Fortune87-SweepLine-Voronoi.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1986 == Reference == http://www.wias-berlin.de/people/si/course/files/Fortune87-SweepLine-Voronoi.pdf")
- 12:15, 15 February 2023 Linear Scan, Poletto & Sarkar (Global Register Allocation Register Allocation) (hist | edit) [471 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(r)$ words (Derived: given the live ranges, the only auxiliary data structure is an "active" list that contains the active live ranges and this has length at most $r$) == Description == Greedy assignment == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1999 == Reference == http://web.cs.ucla.edu/~palsberg/course/cs132/linearscan.pdf")
- 12:15, 15 February 2023 Bottom-m sketches streaming algorithm (streaming Cardinality Estimation) (hist | edit) [339 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(N)$ == Space Complexity == $O(m)$ words (only keep track of m minimum values. also assuming hash function requires O(1) space) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM == Year == 1980 == Reference ==")
- 12:15, 15 February 2023 Cooper and Dasgupta algorithm ( Register Allocation) (hist | edit) [222 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1983 == Reference ==")
- 12:15, 15 February 2023 Chow's Algorithm (Global Register Allocation Register Allocation) (hist | edit) [479 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (Derived: this algorithm also uses a register interference graph (RIG)) == Description == Assumes all variables allocated in main memory (i.e. assumes no spill handling required). Priority-based RIG coloring == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1984 == Reference == https://dl.acm.org/doi/10.1145/502874.50...")
- 12:15, 15 February 2023 Chaitin's Algorithm (Global Register Allocation Register Allocation) (hist | edit) [432 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (Derived: this algorithm uses both an adjacency matrix (called the bit matrix) and adjacency lists (called the adjacency vectors)) == Description == RIG coloring == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1981 == Reference == https://dl.acm.org/doi/10.1145/872726.806984")
- 12:15, 15 February 2023 Min/max sketches streaming algorithm (streaming Cardinality Estimation) (hist | edit) [338 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(N)$ == Space Complexity == $O({1})$ words (only keep track of minimum value. also assuming hash function requires O(1) space) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM == Year == 1980 == Reference ==")
- 12:15, 15 February 2023 LogLog algorithm ( Cardinality Estimation) (hist | edit) [384 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(N)$ == Space Complexity == $O(log(log(n)$)) words (http://algo.inria.fr/flajolet/Publications/DuFl03-LNCS.pdf) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM == Year == 2003 == Reference == http://algo.inria.fr/flajolet/Publications/DuFl03-LNCS.pdf")
- 12:15, 15 February 2023 HyperLogLog++ ( Cardinality Estimation) (hist | edit) [392 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(N)$ == Space Complexity == $O(eps^{-2}*log(log(n)$))+log(n)) words ((see hyperloglog?)) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM == Year == 2014 == Reference == https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/40671.pdf")
- 12:15, 15 February 2023 HyperLogLog algorithm ( Cardinality Estimation) (hist | edit) [417 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(N)$ == Space Complexity == $O(eps^{-2}*log(log(n)$))+log(n)) words (https://oertl.github.io/hyperloglog-sketch-estimation-paper/paper/paper.pdf) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM == Year == 2007 == Reference == http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf")
- 12:15, 15 February 2023 Flajolet–Martin algorithm ( Cardinality Estimation) (hist | edit) [386 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(N)$ == Space Complexity == $O(log n)$ words (https://www.sciencedirect.com/science/article/pii/S0022000097915452) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM == Year == 1984 == Reference == http://algo.inria.fr/flajolet/Publications/src/FlMa85.pdf")
- 12:15, 15 February 2023 Α-EM algorithm ( Maximum Likelihood Parameters) (hist | edit) [440 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n+r)$? words (Stores current theta and Z guesses, which is updated each iteration. Also assumes description of alpha-log-likelihood takes O(n+r) auxiliary space.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 2003 == Reference == https://dl.acm.org/doi/10.1109/TIT.2002.808105")
- 12:15, 15 February 2023 Naive solution ( Cardinality Estimation) (hist | edit) [302 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(N)$ == Space Complexity == $O(n)$ words (keep track of exact histogram, may require storing all values) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == -")
- 12:15, 15 February 2023 Generalized expectation maximization (GEM) algorithm ( Maximum Likelihood Parameters) (hist | edit) [485 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{4} log^{0.{1}.5}n)$ == Space Complexity == $O(n+r)$? words (Stores current theta and Z guesses, which is updated each iteration. Also assumes description of log-likelihood takes O(n+r) auxiliary space.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1994 == Reference == https://web.eecs.umich.edu/~fessler/papers/files/jour/94/web/fessler-94-...")
- 12:15, 15 February 2023 Parameter-expanded expectation maximization (PX-EM) algorithm ( Maximum Likelihood Parameters) (hist | edit) [434 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n+r)$? words (Stores current theta (+ alpha) and Z guesses, which is updated each iteration. Also assumes description of log-likelihood takes O(n+r) auxiliary space.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1998 == Reference == https://www.jstor.org/stable/2337481")
- 12:15, 15 February 2023 Expectation conditional maximization (ECM) ( Maximum Likelihood Parameters) (hist | edit) [427 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} logn)$ == Space Complexity == $O(n+r)$? words (Stores current theta and Z guesses, which is updated each iteration. Also assumes description of log-likelihood takes O(n+r) auxiliary space.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 2017 == Reference == https://arxiv.org/abs/1709.06970")
- 12:15, 15 February 2023 Newton–Raphson algorithm ( Maximum Likelihood Parameters) (hist | edit) [450 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n+r^{2})$? words (Stores current theta guess, which is updated each iteration, and requires computation of the (inverse of the) Hessian matrix. Also assumes description of log-likelihood takes O(n+r) auxiliary space.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1685 == Reference == -")
- 12:15, 15 February 2023 Haselgrove; Leech and Trotter (Bounded Subgroup Index Coset Enumeration) (hist | edit) [387 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O(ng)$? words (Implementation stores a table whose number of required registers is the product of the number of generators (n) and the number of cosets (O(g))) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1940 == Reference ==")
- 12:15, 15 February 2023 Todd–Coxeter algorithm (Bounded Subgroup Index Coset Enumeration) (hist | edit) [501 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O(gkc)$ words (Defines O(k) tables, each with O(g) columns and O(c) rows) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1936 == Reference == https://www.cambridge.org/core/journals/proceedings-of-the-edinburgh-mathematical-society/article/practical-method-for-enumerating-cosets-of-a-finite-abstract-group/030657...")
- 12:15, 15 February 2023 Expectation–maximization (EM) algorithm ( Maximum Likelihood Parameters) (hist | edit) [424 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n+r)$? words (Stores current theta and Z guesses, which is updated each iteration. Also assumes description of log-likelihood takes O(n+r) auxiliary space.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1977 == Reference == https://www.jstor.org/stable/2984875")
- 12:15, 15 February 2023 Knuth–Bendix algorithm (General Groups (uncompleted?) Coset Enumeration) (hist | edit) [462 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({1.5}^n n^{2} logn)$ == Space Complexity == $O(ng)$??? words (Can store a table whose number of required registers is the product of the number of generators (n) and the number of cosets (O(g))) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1970 == Reference == https://www.cs.tufts.edu/~nr/cs257/archive/don-knuth/knuth-bendix.pdf")
- 12:15, 15 February 2023 Muller's method (General Root Computation Root Computation) (hist | edit) [479 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_{max})$ == Space Complexity == $O({1})$ words (Store previous 3 estimates x_i, x_{i-1}, and x_{i-2}; 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 == 1956 == Reference == https://www.jstor.org/stable/200...")
- 12:15, 15 February 2023 Halley's method (Root Computation with continuous second derivative Root Computation) (hist | edit) [482 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_{max})$ == Space Complexity == $O({1})$ words (Store current estimate x_i and the derivatives f' and f'' (assuming this takes O(1) space); 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...")
- 12:15, 15 February 2023 Ridder's method (General Root Computation Root Computation) (hist | edit) [478 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_{max})$ == Space Complexity == $O({1})$ words (Store previous 2 estimates x_i and x_{i-1}; 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 == 1979 == Reference == https://ieeexplore.ieee.org/document/1084580/")
- 12:15, 15 February 2023 Newton's method (Root Computation with continuous first derivative Root Computation) (hist | edit) [479 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_{max})$ == Space Complexity == $O({1})$ words (Store current estimate $x_i$ and the derivative $f'$ (assuming this takes $O(1)$ space); 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 == Referenc...")
- 12:15, 15 February 2023 Secant method (General Root Computation Root Computation) (hist | edit) [434 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_{max})$ == Space Complexity == $O({1})$ words (Store previous 2 estimates x_i and x_{i-1}; 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 == -")
- 12:15, 15 February 2023 False position method (General Root Computation Root Computation) (hist | edit) [425 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_{max})$ == Space Complexity == $O({1})$ words (Store current endpoint values; iterations take $O(1)$ time and thus $O(1)$ space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1690 == Reference == -")
- 12:15, 15 February 2023 MRRR algorithm (Any eigenpair; Any eigenvalue Eigenvalues (Iterative Methods)) (hist | edit) [426 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n^{2})$ words (Need to compute and store some matrix of the form $(A-mu*I)^{(-1)}$ (for inverse iteration-like uses)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1999 == Reference == https://www.cs.utexas.edu/users/inderjit/public_papers/DesignMRRR_toms06.pdf")
- 12:15, 15 February 2023 Bisection method (General Root Computation Root Computation) (hist | edit) [425 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_{max})$ == Space Complexity == $O({1})$ words (Store current endpoint values; iterations take $O(1)$ time and thus $O(1)$ space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1820 == Reference == -")
- 12:15, 15 February 2023 Divide-and-conquer (All eigenvalues; Any eigenvalue Eigenvalues (Iterative Methods)) (hist | edit) [411 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n^{2})$ words (Stores reduction to tridiagonal form; recursion (S(n)=2S(n/2)+O(n^2)) should work out to O(n^2)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1986 == Reference == https://link.springer.com/content/pdf/10.1007/BF01389480.pdf")
- 12:15, 15 February 2023 Homotopy method (All eigenpairs; Eigenpair closest to mu; Any eigenpair; Any eigenvalue; All eigenvalues Eigenvalues (Iterative Methods)) (hist | edit) [403 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$?? words (Conservative bound on space used per iteration) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1992 == Reference == https://www.scirp.org/(S(czeh2tfqyw2orz553k1w0r45))/reference/ReferencesPapers.aspx?ReferenceID=530065")
- 12:15, 15 February 2023 Folded spectrum method (Eigenpair closest to mu; Any eigenpair; Any eigenvalue Eigenvalues (Iterative Methods)) (hist | edit) [438 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$? words (Requires only a constant number of O(n)-sized vectors per iteration; matrix-to-vector multiplication only requires O(n) aux space) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1934 == Reference == https://journals.aps.org/pr/abstract/10.1103/PhysRev.46.828")
- 12:15, 15 February 2023 Jacobi eigenvalue algorithm (All eigenvalues; Any eigenvalue Eigenvalues (Iterative Methods)) (hist | edit) [355 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$? words (Computes and stores results of GSG^T iterations) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1846 == Reference == https://gdz.sub.uni-goettingen.de/id/PPN243919689_0030")
- 12:15, 15 February 2023 Bisection method (Any eigenvalue Eigenvalues (Iterative Methods)) (hist | edit) [424 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$? words (Computing characteristic polynomial takes $O(n^2)$ space (via e.g. Faddeev–LeVerrier algorithm); rest of algo can be done in $O(n)$ space (related to root computation)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1985 == Reference == -")
- 12:15, 15 February 2023 Laguerre iteration (Any eigenvalue Eigenvalues (Iterative Methods)) (hist | edit) [266 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$? words (^ see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1940 == Reference == -")
- 12:15, 15 February 2023 QR algorithm (All eigenvalues; Any eigenvalue Eigenvalues (Iterative Methods)) (hist | edit) [361 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (Computes and stores QR factorization at each iteration) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1962 == Reference == https://academic.oup.com/comjnl/article/4/4/332/432033")