New pages
Jump to navigation
Jump to search
(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)
- 11: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")
- 09: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 ==")
- 09: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")
- 09: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")
- 09: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 ==...")
- 09: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...")
- 08: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")
- 08: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")
- 08: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")
- 08: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")
- 08: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")
- 08: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")
- 08: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")
- 08: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")
- 08: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")
- 08: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")
- 08: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/")
- 08: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")
- 08: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")