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:35, 15 February 2023 Admin talk contribs created page Dinitz (with dynamic trees) ( Maximum Flow) (Created page with "== Time Complexity == $O(VELogU)$ == Space Complexity == $O(E)$ words (can be derived?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1973 == Reference == https://www.scirp.org/(S(lz5mqp453edsnp55rrgjct55))/reference/ReferencesPapers.aspx?ReferenceID=1690549")
• 10:35, 15 February 2023 Admin talk contribs created page Dantzig ( Maximum Flow) (Created page with "== Time Complexity == $O(V^{2}EU)$ == Space Complexity == $O(VE)$? words (can be derived? (assuming this is referring to simplex algorithm)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1951 == Reference ==")
• 10:35, 15 February 2023 Admin talk contribs created page Mukhopadhyay (LCS Longest Common Subsequence) (Created page with "== Time Complexity == $O((n + p) \log n)$ == Space Complexity == $O(p + n)$ words (https://www.sciencedirect.com/science/article/pii/0020025580900250) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1980 == Reference == https://www.sciencedirect.com/science/article/pii/0020025580900250")
• 10:35, 15 February 2023 Admin talk contribs created page Hunt and Szymanski (LCS Longest Common Subsequence) (Created page with "== Time Complexity == $O((n + p) \log n)$ == Space Complexity == $O(p + n)$ words (https://cse.hkust.edu.hk/mjg_lib/bibs/DPSu/DPSu.Files/HuSz77.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1977 == Reference == http://www.cs.ust.hk/mjg_lib/bibs/DPSu/DPSu.Files/HuSz77.pdf")
• 10:35, 15 February 2023 Admin talk contribs created page T. C. Hu ; M. T. Shing (Matrix Chain Ordering Problem Matrix Chain Multiplication) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (can be derived?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1982 == Reference == https://citeseerx.ist.psu.edu/viewdoc/citations?doi=10.1.1.695.2923")
• 10:35, 15 February 2023 Admin talk contribs created page Hashing (kth Order Statistic kth Order Statistic) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ words (Derived: size of hashtable) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == -")
• 10:35, 15 February 2023 Admin talk contribs created page Spreadsort (Non-Comparison Sorting Sorting) (Created page with "== Time Complexity == $O(n*log n)$ == Space Complexity == $O(n)$? words ((can be easily derived?)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2002 == Reference == https://www.semanticscholar.org/paper/The-Spreadsort-High-performance-General-case-Ross/41f5b49e9843b2d98b6b22a84924dae5761e6e52")
• 10:35, 15 February 2023 Admin talk contribs created page Burst Sort (Non-Comparison Sorting Sorting) (Created page with "== Time Complexity == $O(wn)$ == Space Complexity == $O(wn)$ words ((wikipedia page?)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2004 == Reference == https://dl.acm.org/citation.cfm?doid=1005813.1041517")
• 10:35, 15 February 2023 Admin talk contribs created page Bead Sort (Non-Comparison Sorting Sorting) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n^{2})$ words ((wikipedia page?)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2002 == Reference == https://web.archive.org/web/20170809110409/https://www.cs.auckland.ac.nz/~jaru003/research/publications/journals/beadsort.pdf")
• 10:35, 15 February 2023 Admin talk contribs created page Flash Sort (Non-Comparison Sorting Sorting) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words ((can be easily derived)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1998 == Reference == http://www.neubert.net/FSOIntro.html")
• 10:35, 15 February 2023 Admin talk contribs created page Naive sorting (Non-Comparison Sorting Sorting) (Created page with "== Time Complexity == $O( n² )$ == Space Complexity == $O({1})$ (in-situ) ((can be easily derived)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == -")
• 10:35, 15 February 2023 Admin talk contribs created page Thorup's Sorting Algorithm (Comparison Sorting Sorting) (Created page with "== Time Complexity == $O(n loglogn)$ == Space Complexity == $O(n)$ words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2002 == Reference == https://www.sciencedirect.com/science/article/pii/S0196677402912113?via%3Dihub")
• 10:35, 15 February 2023 Admin talk contribs created page Bitonic Merge Sort Parallel Implementation (Comparison Sorting Sorting) (Created page with "== Time Complexity == $O(log² n)$ == Space Complexity == $O({1})$? words (Paper claims "logspace uniform", so with O(log n) words, this is constant # of words) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == PRAC (shared-memory multiprocessor of the EREW PRAM variety) == Year == 1968 == Reference == https://epubs.siam.org/doi/abs/10.1137/0218014")
• 10:35, 15 February 2023 Admin talk contribs created page Shell Sort; (Sedgewick) (Comparison Sorting Sorting) (Created page with "== Time Complexity == $O(n^{1.{3}3})$ == Space Complexity == $O({1})$ (in-situ) words ((can be easily derived)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1986 == Reference == https://www.sciencedirect.com/science/article/pii/0196677486900015?via%3Dihub")
• 10:35, 15 February 2023 Admin talk contribs created page Shell Sort; (Pratt) (Comparison Sorting Sorting) (Created page with "== Time Complexity == $O(n log² n)$ == Space Complexity == $O({1})$ (in-situ) words ((can be easily derived)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1971 == Reference == https://apps.dtic.mil/sti/pdfs/AD0740110.pdf")
• 10:35, 15 February 2023 Admin talk contribs created page Shell Sort; (Frank & Lazarus) (Comparison Sorting Sorting) (Created page with "== Time Complexity == $O(n^{1.5})$ == Space Complexity == $O({1})$ (in-situ) words ((can be easily derived)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1960 == Reference == https://dl.acm.org/citation.cfm?doid=366947.366957")
• 10:35, 15 February 2023 Admin talk contribs created page Shell Sort; (Shell) (Comparison Sorting Sorting) (Created page with "== Time Complexity == $O( n² )$ == Space Complexity == $O({1})$ (in-situ) words ((can be easily derived)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1959 == Reference == https://dl.acm.org/citation.cfm?doid=368370.368387")
• 10:35, 15 February 2023 Admin talk contribs created page Cube Sort Parallel Implementation (Comparison Sorting Sorting) (Created page with "== Time Complexity == $O(n logn)$ == Space Complexity == $O(n)$ words ((can be easily derived)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Parallel RAM == Year == 1992 == Reference == https://www.sciencedirect.com/science/article/pii/0196677492900166?via%3Dihub")
• 10:35, 15 February 2023 Admin talk contribs created page Tim Sort (Comparison Sorting Sorting) (Created page with "== Time Complexity == $O(n logn)$ == Space Complexity == $O(n)$ words ((can be easily derived)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2002 == Reference == -")
• 10:35, 15 February 2023 Admin talk contribs created page Quick Sort (Comparison Sorting Sorting) (Created page with "== Time Complexity == $O( n² )$ == Space Complexity == $O(logn)$ words (https://academic.oup.com/comjnl/article/5/1/10/395338?login=true) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1961 == Reference == https://apps.dtic.mil/dtic/tr/fulltext/u2/740110.pdf")
• 10:35, 15 February 2023 Admin talk contribs created page Tree sort (Comparison Sorting Sorting) (Created page with "== Time Complexity == $O(n logn)$ == Space Complexity == $O(n)$ words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1962 == Reference == http://www.neubert.net/FSOIntro.html")
• 10:35, 15 February 2023 Admin talk contribs created page Bitap algorithm (Single String Search String Search) (Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(m)$ words (Derived: Uses a bit array of size $O(m)$) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1964 == Reference == https://en.wikipedia.org/wiki/Bitap_algorithm")
• 10:35, 15 February 2023 Admin talk contribs created page Bunch; Hopcroft (Square Matrix LU Decomposition LU Decomposition) (Created page with "== Time Complexity == $O(n^{2.{37}6})$ == Space Complexity == $\tilde{O}(n^{2})$ words (Derived: Uses Strassen multiplication and a constant number of $n \times n$ auxiliary matrices) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1974 == Reference == https://dl.acm.org/citation.cfm?id=248979")
• 10:35, 15 February 2023 Admin talk contribs created page Khuller; Matias Randomized Sieve ( Closest Pair Problem) (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 == == Approximate? == Exact == Randomized? == Yes, Las Vegas == Model of Computation == not mentioned == Year == 1995 == Reference == https://dl.acm.org/citation.cfm?id=207181")
• 10:35, 15 February 2023 Admin talk contribs created page Fomin; Gaspers & Saurabh (4-Graph Coloring Graph Coloring) (Created page with "== Time Complexity == $O({1.7272}^n)$ == Space Complexity == $O(n)$ words (Derived: we store the sets I and C (in algorithm enumIS), and the maximum size of these sets is equal to the number of vertices in the graph. The algorithm also stores the solution sets S1 and S2, which have a maximum size equal to the number of vertices in the graph. We also call a 3-coloring algorithm, which likely has O(n) space complexity) == Description == == Approximate? == Exac...")
• 10:35, 15 February 2023 Admin talk contribs created page Petford and Welsh (3-Graph Coloring Graph Coloring) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (Derived: we store the coloring of each vertex in a dictionary and the maximum size of this dictionary is equal to the number of vertices in the graph, n.) == Description == == Approximate? == Exact == Randomized? == Yes, Monte Carlo == Model of Computation == Word RAM == Year == 1989 == Reference == https://www.sciencedirect.com/science/article/pii/0012365X89902148")
• 10:35, 15 February 2023 Admin talk contribs created page Rao-Blackwellized Particle Filtering SLAM (SLAM Algorithms SLAM Algorithms) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$? words? ((based on Section 4 of the paper?)) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2001 == Reference == https://papers.nips.cc/paper/1716-bayesian-map-learning-in-dynamic-environments.pdf")
• 10:35, 15 February 2023 Admin talk contribs created page Compressed Extended KF (SLAM Algorithms SLAM Algorithms) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$? words? ((can be easily derived? it's mostly square matrices here)) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2002 == Reference == https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.206.999&rep=rep1&type=pdf")
• 10:35, 15 February 2023 Admin talk contribs created page UKF (SLAM Algorithms SLAM Algorithms) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$? words? ((can be easily derived? it's mostly square matrices here)) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2000 == Reference == https://www.seas.harvard.edu/courses/cs281/papers/unscented.pdf")
• 10:35, 15 February 2023 Admin talk contribs created page EKF SLAM (SLAM Algorithms SLAM Algorithms) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$? words? ((can be easily derived? it's mostly square matrices here)) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 1998 == Reference == http://ais.informatik.uni-freiburg.de/teaching/ss12/robotics/slides/12-slam.pdf")
• 10:35, 15 February 2023 Admin talk contribs created page Image quilting Efros-Freeman (Texture Synthesis Texture Synthesis) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2001 == Reference == https://dl.acm.org/doi/abs/10.1145/383259.383296")
• 10:35, 15 February 2023 Admin talk contribs created page R. Paget ; I.D. Longstaff (Texture Synthesis Texture Synthesis) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 1998 == Reference == https://ieeexplore.ieee.org/abstract/document/679446")
• 10:35, 15 February 2023 Admin talk contribs created page Image analogies Hertzmann (Texture Synthesis Texture Synthesis) (Created page with "== Time Complexity == $O(N log n)$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2001 == Reference == https://dl.acm.org/doi/abs/10.1145/383259.383295")
• 10:35, 15 February 2023 Admin talk contribs created page Non-parametric sampling Efros and Leung (Texture Synthesis Texture Synthesis) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 1999 == Reference == https://ieeexplore.ieee.org/abstract/document/790383")
• 10:35, 15 February 2023 Admin talk contribs created page Petro Vlahos Algorithm (Image Compositing Image Compositing) (Created page with "== Time Complexity == $O(n^{2} k/r)$ == Space Complexity == $O(nk)$?? words (Keeps track of all pixels across all images) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1985 == Reference ==")
• 10:35, 15 February 2023 Admin talk contribs created page Roth AlignACE (Motif Search Motif Search) (Created page with "== Time Complexity == $O(nm)$ == Space Complexity == $O(n + m)$ words (derived: essentially just modified Gibbs sampling) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1998 == Reference == https://www.ncbi.nlm.nih.gov/pubmed/9788350")
• 10:35, 15 February 2023 Admin talk contribs created page Alon; Moshkovitz & Safra (Unweighted Set-Covering The Set-Covering Problem) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2006 == Reference == https://dl.acm.org/doi/pdf/10.1145/1150334.1150336")
• 10:35, 15 February 2023 Admin talk contribs created page Chvatal greedy heuristic (Weighted Set-Covering The Set-Covering Problem) (Created page with "== Time Complexity == $O(dn^{2})$ == Space Complexity == $O(dm)$ (Derived -- worst case, updating each set in S to be something else and we don't want to change the input) == Description == == Approximate? == Approximate Approximation Factor: ln n - lnln n + \Theta(1) == Randomized? == No, deterministic == Model of Computation == == Year == 1979 == Reference == https://www.jstor.org/stable/3689577#metadata_info_tab_contents")
• 10:35, 15 February 2023 Admin talk contribs created page The SUSAN corner detector ( Corner Detection) (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:35, 15 February 2023 Admin talk contribs created page L. Kitchen and A. Rosenfeld (Grey-scale Corner Detection) (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:34, 15 February 2023 Admin talk contribs created page Harris and Stephens algorithm ( Corner Detection) (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:34, 15 February 2023 Admin talk contribs created page Barvinok (Geometric Maximum TSP The Traveling-Salesman Problem) (Created page with "== Time Complexity == $O(V^{2} loglogE)$ == Space Complexity == $O(V)$? memory cells (Derived: One memory cell per tunnel-city pair, with one tunnel total) == Description == Tunneling == Approximate? == Approximate Approximation Factor: ? == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 2003 == Reference == https://dl.acm.org/doi/10.1145/876638.876640")
• 10:34, 15 February 2023 Admin talk contribs created page Dantzig-Fulkerson-Johnson (DFJ) formulation (Minimum TSP The Traveling-Salesman Problem) (Created page with "== Time Complexity == $O({1.674}^V E^{2})$ == Space Complexity == $O({2}^V)$ words (http://web.ist.utl.pt/~ist11038/CD_Casquilho/TSP1992EJOR_Laporte.pdf) == Description == ILP formulation == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1954 == Reference == https://doi.org/10.1287/opre.2.4.393")
• 10:34, 15 February 2023 Admin talk contribs created page Miller-Tucker-Zemlin (MTZ) formulation (Minimum TSP The Traveling-Salesman Problem) (Created page with "== Time Complexity == $exp(V)$ == Space Complexity == $O(V^{4})$ words (Derived: V^2 + 2V constraints on V^2 variables, most integer programs use space of O(nm) where n=#vars and m=#constraints) == Description == ILP formulation == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1960 == Reference == https://dl.acm.org/doi/10.1145/321043.321046")
• 10:34, 15 February 2023 Admin talk contribs created page Micali and Vazirani ( Maximum Cardinality Matching) (Created page with "== Time Complexity == $O(V^{0.5} E)$ == Space Complexity == $O(V)$ not mentioned (https://link.springer.com/content/pdf/10.1007/PL00009186.pdf) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == Restricted Randomness (RR) == Year == 1980 == Reference == https://dl.acm.org/doi/10.1109/SFCS.1980.12")
• 10:34, 15 February 2023 Admin talk contribs created page Brélaz (DSatur) (3-Graph Coloring Graph Coloring) (Created page with "== Time Complexity == $O(V^{2})$ == Space Complexity == $O(V + E)$ words (Derived using adjacency lists) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1979 == Reference == https://dl.acm.org/doi/10.1145/359094.359101")
• 10:34, 15 February 2023 Admin talk contribs created page Karger, Blum ( Graph Coloring) (Created page with "== Time Complexity == $O(poly(V))$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: $\tilde{O}(n^{3/14})$ == Randomized? == No, deterministic == Model of Computation == == Year == 1997 == Reference == http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.4204")
• 10:34, 15 February 2023 Admin talk contribs created page Schonhage's algorithm (Matrix Multiplication Matrix Product) (Created page with "== Time Complexity == $O(n^{({3}*log52/log110)}) ~ O(n^{2.{521}8})$ == Space Complexity == $O(n^{2})$ words (Derived: Same idea as Strassen's, plus three additional nxn matrices) == Description == == Approximate? == Approximate Approximation Factor: ? == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1980 == Reference == https://epubs.siam.org/doi/abs/10.1137/0210032")
• 10:34, 15 February 2023 Admin talk contribs created page Bini's algorithm (Matrix Multiplication Matrix Product) (Created page with "== Time Complexity == $O(n^{2.{779}9})$ == Space Complexity == $O(n^{2})$ words (Derived: Same idea as Strassen's, plus three additional nxn matrices) == Description == == Approximate? == Approximate Approximation Factor: $O(n logn)$ error == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1979 == Reference == https://doi.org/10.1016/0020-0190(79)90113-3")
• 10:34, 15 February 2023 Admin talk contribs created page Chin (Approximate MCOP Matrix Chain Multiplication) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ words (Derived: There are a few auxiliary variables, only one of which is variable length. That is a list of length $O(n)$.) == Description == == Approximate? == Approximate Approximation Factor: 1.2485 == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1978 == Reference == https://dl.acm.org/citation.cfm?id=359556")

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