All public logs

Combined display of all available logs of Algorithm Wiki. You can narrow down the view by selecting a log type, the username (case-sensitive), or the affected page (also case-sensitive).

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

• 10:33, 15 February 2023 Admin talk contribs created page 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")
• 10:33, 15 February 2023 Admin talk contribs created page 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:33, 15 February 2023 Admin talk contribs created page 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 == -")
• 10:33, 15 February 2023 Admin talk contribs created page 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")
• 10:33, 15 February 2023 Admin talk contribs created page 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")
• 10:33, 15 February 2023 Admin talk contribs created page 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")
• 10:33, 15 February 2023 Admin talk contribs created page 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")
• 10:33, 15 February 2023 Admin talk contribs created page 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")
• 10:33, 15 February 2023 Admin talk contribs created page 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")
• 10:33, 15 February 2023 Admin talk contribs created page 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")
• 10:32, 15 February 2023 Admin talk contribs created page 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")
• 10:32, 15 February 2023 Admin talk contribs created page 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")
• 10:32, 15 February 2023 Admin talk contribs created page 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")
• 10:32, 15 February 2023 Admin talk contribs created page 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/")
• 10:32, 15 February 2023 Admin talk contribs created page 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")
• 10:32, 15 February 2023 Admin talk contribs created page 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")
• 10:32, 15 February 2023 Admin talk contribs created page 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 ==")
• 10:32, 15 February 2023 Admin talk contribs created page 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:32, 15 February 2023 Admin talk contribs created page 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:32, 15 February 2023 Admin talk contribs created page 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:32, 15 February 2023 Admin talk contribs created page 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:32, 15 February 2023 Admin talk contribs created page 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:32, 15 February 2023 Admin talk contribs created page 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 == -")
• 10:32, 15 February 2023 Admin talk contribs created page 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:32, 15 February 2023 Admin talk contribs created page 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:32, 15 February 2023 Admin talk contribs created page 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:32, 15 February 2023 Admin talk contribs created page 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:32, 15 February 2023 Admin talk contribs created page 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")
• 10:32, 15 February 2023 Admin talk contribs created page 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")
• 10:32, 15 February 2023 Admin talk contribs created page 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")
• 10:32, 15 February 2023 Admin talk contribs created page 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")
• 10:32, 15 February 2023 Admin talk contribs created page 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 == -")
• 10:32, 15 February 2023 Admin talk contribs created page 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 == -")
• 10:32, 15 February 2023 Admin talk contribs created page 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 ==")
• 10:32, 15 February 2023 Admin talk contribs created page 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:32, 15 February 2023 Admin talk contribs created page 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")
• 10:32, 15 February 2023 Admin talk contribs created page 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")
• 10:32, 15 February 2023 Admin talk contribs created page Coppersmith–Winograd algorithm (Matrix Multiplication Matrix Product) (Created page with "== Time Complexity == $O(n^{2.{49554}8})$ == 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 == 1981 == Reference == https://epubs.siam.org/doi/abs/10.1137/0211038")
• 10:32, 15 February 2023 Admin talk contribs created page Romani's algorithm (Matrix Multiplication Matrix Product) (Created page with "== Time Complexity == $O(n^{2.{5166}5})$ == 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 == 1981 == Reference == https://epubs.siam.org/doi/abs/10.1137/0211020")
• 10:32, 15 February 2023 Admin talk contribs created page Pan's algorithm (Matrix Multiplication Matrix Product) (Created page with "== Time Complexity == $O(n^{(log({143640})/log({70}))}) ~ O(n^{2.{79}5})$ == 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 == 1978 == Reference == https://ieeexplore.ieee.org/document/4567976")
• 10:32, 15 February 2023 Admin talk contribs created page Strassen's algorithm (Matrix Multiplication Matrix Product) (Created page with "== Time Complexity == $O(n^{(log7/log2)}) ~ O(n^{2.{80}7})$ == Space Complexity == $O(n^{2})$ words (http://www.cs.cmu.edu/afs/cs/academic/class/15750-s17/ScribeNotes/lecture1.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1969 == Reference == https://link.springer.com/article/10.1007%2FBF02165411")
• 10:32, 15 February 2023 Admin talk contribs created page Naive algorithm (Matrix Multiplication Matrix Product) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O({1})$ auxiliary words (can be easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == -")
• 10:32, 15 February 2023 Admin talk contribs created page Galil & Naamad ( Maximum Flow) (Created page with "== Time Complexity == $O(VELog^{2}V)$ == Space Complexity == $O(E)$ words (https://core.ac.uk/download/pdf/81946904.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1980 == Reference == https://core.ac.uk/download/pdf/81946904.pdf")
• 10:32, 15 February 2023 Admin talk contribs created page Karzanov ( Maximum Flow) (Created page with "== Time Complexity == $O(V^{3})$ == Space Complexity == $O(V^{2})$ words (https://core.ac.uk/download/pdf/81946904.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1974 == Reference == http://alexander-karzanov.net/Publications/maxflow-acyc.pdf")
• 10:32, 15 February 2023 Admin talk contribs created page Edmonds & Karp ( Maximum Flow) (Created page with "== Time Complexity == $O(E^{2}LogU)$ == Space Complexity == $O(E)$ words (https://core.ac.uk/download/pdf/81946904.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1972 == Reference == https://web.eecs.umich.edu/~pettie/matching/Edmonds-Karp-network-flow.pdf")
• 10:32, 15 February 2023 Admin talk contribs created page Dinitz ( Maximum Flow) (Created page with "== Time Complexity == $O(V^{2}E)$ == Space Complexity == $O(E)$ words (https://core.ac.uk/download/pdf/81946904.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1970 == Reference == https://www.scirp.org/(S(lz5mqp453edsnp55rrgjct55))/reference/ReferencesPapers.aspx?ReferenceID=1690549")
• 10:32, 15 February 2023 Admin talk contribs created page Ford & Fulkerson ( Maximum Flow) (Created page with "== Time Complexity == $O(E^{2}U)$ == Space Complexity == $O(E)$ words (https://core.ac.uk/download/pdf/81946904.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1955 == Reference == http://www.cs.yale.edu/homes/lans/readings/routing/ford-max_flow-1956.pdf")
• 10:32, 15 February 2023 Admin talk contribs created page Wagner and Fischer (LCS Longest Common Subsequence) (Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(mn)$, later $O(m+n)$ due to Hirschberg 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/citation.cfm?doid=321796.321811")
• 10:32, 15 February 2023 Admin talk contribs created page Dynamic Programming Algorithm (S. S. Godbole) (Matrix Chain Ordering Problem Matrix Chain Multiplication) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$ words (CLRS) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1953 == Reference == -")
• 10:31, 15 February 2023 Admin talk contribs created page Brute Force (Matrix Chain Ordering Problem Matrix Chain Multiplication) (Created page with "== Time Complexity == O ({4}^n) == Space Complexity == $O(n)$ words (can be derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == -")

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