User contributions for Admin
Jump to navigation
Jump to search
15 February 2023
- 10:3310:33, 15 February 2023 diff hist +381 N Cyrus–Beck (Convex Polygonal Window; Convex Polyhedral window Line Clipping) Created page with "== Time Complexity == $O(np)$ == Space Complexity == $O({1})$ auxiliary? words (Easily derived? (O(1) per segment, space can be re-used)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1978 == Reference == https://www.sciencedirect.com/science/article/pii/0097849378900213"
- 10:3310:33, 15 February 2023 diff hist +356 N Liang–Barsky (Rectangular Window Line Clipping) Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary words (Easily derived (O(1) per segment, space can be re-used)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1984 == Reference == https://dl.acm.org/doi/10.1145/357332.357333"
- 10:3310:33, 15 February 2023 diff hist +410 N Cohen–Sutherland (Rectangular Window Line Clipping) Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary words (Easily derived (O(1) per segment, space can be re-used)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1967 == Reference == https://books.google.com/books/about/Principles_of_interactive_computer_graph.html?id=inJ8AAAAIAAJ"
- 10:3310:33, 15 February 2023 diff hist +363 N David Sankoff (Edit sequence, global alignment Sequence Alignment) Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(mn)$ words (Uses a constant number of m*n arrays, whose contents are of size O(1)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1972 == Reference == https://www.ncbi.nlm.nih.gov/pmc/articles/PMC427531/" current
- 10:3310:33, 15 February 2023 diff hist +392 N Myers and Miller (Edit sequence, local alignment Sequence Alignment) Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(n+log(m)$) words (https://academic.oup.com/bioinformatics/article/4/1/11/205106?login=true) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1988 == Reference == https://academic.oup.com/bioinformatics/article/4/1/11/205106?login=true" current
- 10:3310:33, 15 February 2023 diff hist +363 N Altschul and Erickson (Edit sequence, local alignment Sequence Alignment) Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(mn)$ words (Uses a constant number of m*n arrays, whose contents are of size O(1)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1986 == Reference == https://link.springer.com/article/10.1007/BF02462326" current
- 10:3310:33, 15 February 2023 diff hist +377 N Gotoh (Edit sequence, local alignment Sequence Alignment) Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(mn)$ words (Uses a constant number of m*n arrays, whose contents are of size O(1)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1982 == Reference == https://www.sciencedirect.com/science/article/pii/0022283682903989" current
- 10:3310:33, 15 February 2023 diff hist +335 N FASTA (Edit sequence, local alignment Sequence Alignment) Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(mn)$ words (Uses an m*n array, whose contents are of size O(1)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1985 == Reference == https://www.ncbi.nlm.nih.gov/pubmed/2983426" current
- 10:3310:33, 15 February 2023 diff hist +378 N Hirschberg's algorithm (Edit sequence, constant-size alphabet Sequence Alignment) 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 == http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/DynProg/Docs/Hirschberg-LCS-1975.pdf" current
- 10:3310:33, 15 February 2023 diff hist +393 N Masek; Patterson (Edit distance, constant-size alphabet Sequence Alignment) Created page with "== Time Complexity == $O(mn / log(n))$ == Space Complexity == $O(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" current
- 10:3310:33, 15 February 2023 diff hist +362 N Smith–Waterman algorithm (Edit sequence, local alignment Sequence Alignment) Created page with "== Time Complexity == $O(mn^{2})$ == Space Complexity == $O(mn)$ words (Uses an m*n array, whose contents are of size O(1)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1981 == Reference == https://www.sciencedirect.com/science/article/pii/0022283681900875" current
- 10:3310:33, 15 February 2023 diff hist +358 N Needleman–Wunsch algorithm (Edit sequence, global alignment Sequence Alignment) Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(mn)$ words (Uses an m*n array, whose contents are of size O(1)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1970 == Reference == https://www.sciencedirect.com/science/article/pii/0022283670900574" current
- 10:3310:33, 15 February 2023 diff hist +426 N Rabin-Karp (RK) algorithm (Single String Search String Search) Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O({1})$ words (Derived: only storing a rolling hash) == Description == Hashing-based, compare the text and patterns via their hash functions == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1987 == Reference == https://pdfs.semanticscholar.org/c47d/151f09c567013761632c89e237431c6291a2.pdf" current
- 10:3310:33, 15 February 2023 diff hist +427 N Boyer-Moore (BM) algorithm (Single String Search String Search) Created page with "== Time Complexity == $O(mn + s)$ == Space Complexity == $O(s)$ words (https://www.cs.utexas.edu/users/moore/publications/fstrpos.pdf) == Description == Heuristics-based, bad-character and good-suffix heuristics == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1977 == Reference == https://www.cs.utexas.edu/users/moore/publications/fstrpos.pdf" current
- 10:3310:33, 15 February 2023 diff hist +464 N Knuth-Morris-Pratt (KMP) algorithm (Single String Search String Search) Created page with "== Time Complexity == $O(m+n)$ == Space Complexity == $O(m)$ words (https://www.semanticscholar.org/paper/Fast-Pattern-Matching-in-Strings-Knuth-Morris/5253fead88bfeaaa2930daccb7324a264cb681a9?p2df) == Description == Automaton-based == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1977 == Reference == https://pdfs.semanticscholar.org/4479/9559a1067e06b5a6bf052f8f10637707928f.pdf"
- 10:3310:33, 15 February 2023 diff hist +295 N Naïve string-search algorithm (Single String Search String Search) Created page with "== Time Complexity == $O(m(n-m+{1}))$ == Space Complexity == $O({1})$ words (Derived (pointer algorithm)) == Description == Linear searching == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == -" current
- 10:3310:33, 15 February 2023 diff hist +315 N Time-Bounded A* (TBA*) (Informed Search Informed Search) 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 == 2009 == Reference == https://www.cs.du.edu/~sturtevant/papers/TBA.pdf" current
- 10:3310:33, 15 February 2023 diff hist +357 N Anytime Repairing A* (ARA*) (Informed Search Informed Search) 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://papers.nips.cc/paper/2382-ara-anytime-a-with-provable-bounds-on-sub-optimality.pdf" current
- 10:3310:33, 15 February 2023 diff hist +318 N Theta* (Informed Search Informed Search) 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 == 2010 == Reference == http://idm-lab.org/bib/abstracts/papers/aaai07a.pdf" current
- 10:3310:33, 15 February 2023 diff hist +332 N Simplified Memory-Bounded A* (SMA*) (Informed Search Informed Search) 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 == 1992 == Reference == https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.105.7839" current
- 10:3310:33, 15 February 2023 diff hist +318 N Lifelong Planning A* (LPA*) (Informed Search Informed Search) 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 == 2001 == Reference == http://idm-lab.org/bib/abstracts/papers/aaai02b.pdf" current
- 10:3310:33, 15 February 2023 diff hist +345 N Jump Point Search (JPS) (Informed Search Informed Search) 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 == 2011 == Reference == http://users.cecs.anu.edu.au/~dharabor/data/papers/harabor-grastien-aaai11.pdf" current
- 10:3310:33, 15 February 2023 diff hist +328 N Iterative Deepening A* (IDA*) (Informed Search Informed Search) 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 == 1985 == Reference == https://linkinghub.elsevier.com/retrieve/pii/0004370285900840" current
- 10:3210:32, 15 February 2023 diff hist +319 N Generalized Adaptive A* (GAA*) (Informed Search Informed Search) 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 == 2008 == Reference == http://idm-lab.org/bib/abstracts/papers/aamas08b.pdf" current
- 10:3210:32, 15 February 2023 diff hist +319 N Fringe Saving A* (FSA*) (Informed Search Informed Search) 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 == 2008 == Reference == http://idm-lab.org/bib/abstracts/papers/aamas09d.pdf" current
- 10:3210:32, 15 February 2023 diff hist +388 N Bidirectional A* Algorithm (Informed Search Informed Search) Created page with "== Time Complexity == $O(b^{(d/{2})})$ == Space Complexity == $O(b^{(d/{2})$}) (Stores all generated nodes in memory) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2007 == Reference == https://www.cs.princeton.edu/courses/archive/spr06/cos423/Handouts/EPP%20shortest%20path%20algorithms.pdf" current
- 10:3210:32, 15 February 2023 diff hist +363 N A* Algorithm (Informed Search Informed Search) Created page with "== Time Complexity == $O(b^d)$ == Space Complexity == $O(b^d)$ (https://en.wikipedia.org/wiki/A*_search_algorithm: Stores all generated nodes in memory) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1968 == Reference == https://ieeexplore.ieee.org/document/4082128/" current
- 10:3210:32, 15 February 2023 diff hist +314 N Okunev; Johnson (Square Matrix LU Decomposition LU Decomposition) Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O({1})$ words (Derived: all in-place calculations) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1997 == Reference == https://arxiv.org/abs/math/0506382" current
- 10:3210:32, 15 February 2023 diff hist +355 N Crout and LUP algorithms (Square Matrix LU Decomposition LU Decomposition) Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $\tilde{O}({1})$ words (Derived: only storing 1 intermediate variable) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2007 == Reference == https://en.wikipedia.org/wiki/Crout_matrix_decomposition" current
- 10:3210:32, 15 February 2023 diff hist +296 N Doolittle Algorithm (Square Matrix LU Decomposition LU Decomposition) Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $\tilde{O}({1})$ words (Derived: only storing 1 intermediate variable) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1878 == Reference ==" current
- 10:3210:32, 15 February 2023 diff hist +279 N Naive Implementation (k-dimensional space, l m (or l infty) norm Closest Pair Problem) Created page with "== Time Complexity == $O(kn^{2})$ == Space Complexity == $O({1})$ auxiliary words (can be easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1975 == Reference == -"
- 10:3210:32, 15 February 2023 diff hist +347 N Karger; Klein & Tarjan (Undirected, General MST Minimum Spanning Tree (MST)) Created page with "== Time Complexity == $O(min(V^{2}, ElogV)$) == Space Complexity == $O(E)$ auxiliary words (can be easily derived) == Description == == Approximate? == Exact == Randomized? == Yes, Las Vegas == Model of Computation == Word RAM == Year == 1995 == Reference == http://cs.brown.edu/research/pubs/pdfs/1995/Karger-1995-RLT.pdf"
- 10:3210:32, 15 February 2023 diff hist +319 N Quick Kruskal algorithm (Undirected, General MST Minimum Spanning Tree (MST)) Created page with "== Time Complexity == $O(Elog(V)$) == Space Complexity == $O(E)$ auxiliary words (can be easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference == https://dl.acm.org/citation.cfm?id=2791187"
- 10:3210:32, 15 February 2023 diff hist +329 N Kruskal’s algorithm with demand-sorting (Undirected, General MST Minimum Spanning Tree (MST)) Created page with "== Time Complexity == $O(Elog(V)$) == Space Complexity == $O(E)$ auxiliary words (can be easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1991 == Reference == https://link.springer.com/chapter/10.1007/BFb0028279"
- 10:3210:32, 15 February 2023 diff hist +336 N Jarvis (2-dimensional Convex Hull) Created page with "== Time Complexity == $O(nh)$ == Space Complexity == $O({1})$ auxiliary? words (can be easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1973 == Reference == https://linkinghub.elsevier.com/retrieve/pii/0020019073900203"
- 10:3210:32, 15 February 2023 diff hist +266 N Brute Force (2-dimensional Convex Hull) Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n)$ words (can be easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1935 == Reference == -" current
- 10:3210:32, 15 February 2023 diff hist +356 N Bentley–Ottmann algorithm (Reporting all intersection points, line segments Line segment intersection) Created page with "== Time Complexity == $O( n log n + k log n)$ == Space Complexity == $O(n)$ auxiliary words (https://dl.acm.org/doi/pdf/10.1145/147508.147511) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1979 == Reference == https://doi.org/10.1109%2FTC.1979.1675432"
- 10:3210:32, 15 February 2023 diff hist +325 N Naive (Reporting all intersection points, line segments Line segment intersection) Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n+k)$ total ($O({1})$ auxiliary if excluding input and output) words (can be easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1940 == Reference == -"
- 10:3210:32, 15 February 2023 diff hist +397 N Khachiyan Ellipsoid algorithm ( Linear Programming) Created page with "== Time Complexity == $O(n^{6} * L^{2} logL loglogL)$ == Space Complexity == $O(nmL)$ words (see orginal paper (noting that O(alpha*log(H*alpha)) = O(L))) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1979 == Reference == https://www.sciencedirect.com/science/article/abs/pii/0041555380900610"
- 10:3210:32, 15 February 2023 diff hist +327 N Fourier–Motzkin elimination ( Linear Programming) Created page with "== Time Complexity == $O((m/{4})$^{({2}^n)}) == Space Complexity == $O((m/{4})$*({2}^n)) words ((can be easily derived? you have that many inequalities)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == -"
- 10:3210:32, 15 February 2023 diff hist +373 N Bjorck-Pereyra (Vandermonde Matrix Linear System) Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ total words (can be easily derived (lower bounded by input size, upper bounded by runtime)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1970 == Reference == https://www.jstor.org/stable/2004623?seq=1" current
- 10:3210:32, 15 February 2023 diff hist +383 N Bareiss Algorithm (Toeplitz Matrix Linear System) Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ total words (can be easily derived (lower bounded by input size, upper bounded by runtime)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1969 == Reference == https://link.springer.com/article/10.1007/BF02163269" current
- 10:3210:32, 15 February 2023 diff hist +393 N Levinson–Durbin recursion (Toeplitz Matrix Linear System) Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ total words (can be easily derived (lower bounded by input size, upper bounded by runtime)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1947 == Reference == https://onlinelibrary.wiley.com/doi/abs/10.1002/sapm1946251261" current
- 10:3210:32, 15 February 2023 diff hist +327 N Aasen's method (Non-Definite, Symmetric Matrix Linear System) Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$ total words (can be easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1971 == Reference == https://link.springer.com/article/10.1007/BF01931804" current
- 10:3210:32, 15 February 2023 diff hist +270 N Cholesky (Positive Definite, Hermitian Matrix Linear System) Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$ words (can be easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == -" current
- 10:3210:32, 15 February 2023 diff hist +270 N Gaussian-Jordan Elimination (General Linear System; Positive Definite, Hermitian Matrix; Non-Definite, Symmetric Matrix; Toeplitz Matrix; Vandermonde Matrix Linear System) Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$ words (can be easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == -150 == Reference == -" current
- 10:3210:32, 15 February 2023 diff hist +280 N Brute force (4-Graph Coloring Graph Coloring) Created page with "== Time Complexity == $O((m+n)*{4}^n)$ == Space Complexity == $O(n)$ auxiliary words ((can be easily derived)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1852 == Reference ==" current
- 10:3210:32, 15 February 2023 diff hist +284 N Brute-force search (3-Graph Coloring Graph Coloring) Created page with "== Time Complexity == $O((n+m)*{3}^n)$ == Space Complexity == $O(n)$ auxiliary words ((can be easily derived)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1852 == Reference == -"
- 10:3210:32, 15 February 2023 diff hist +326 N François Le Gall (Matrix Multiplication Matrix Product) Created page with "== Time Complexity == $O(n^{2.{372863}9})$ == Space Complexity == $O(n^{2})$ words (Re-use of space in recursive branches) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2014 == Reference == https://arxiv.org/abs/1401.7714" current
- 10:3210:32, 15 February 2023 diff hist +344 N Vassilevska Williams (Matrix Multiplication Matrix Product) Created page with "== Time Complexity == $O(n^{2.{37287}3})$ == Space Complexity == $O(n^{2})$ words (Re-use of space in recursive branches) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2014 == Reference == http://theory.stanford.edu/~virgi/matrixmult-f.pdf" current