User contributions for Admin
Jump to navigation
Jump to search
15 February 2023
- 10:3610:36, 15 February 2023 diff hist +366 N James B Orlin's + KRT (King; Rao; Tarjan)'s algorithm (st-Maximum Flow Maximum Flow) Created page with "== Time Complexity == $O(VE)$ == Space Complexity == $O(V + E)$ words (Derived: creates and updates an auxiliary graph) == Description == Improvement of the KRT algorithm == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2013 == Reference == https://dl.acm.org/citation.cfm?id=2488705" current
- 10:3610:36, 15 February 2023 diff hist +4 Goldberg & Rao (Integer Maximum Flow Maximum Flow) No edit summary Tag: Reverted
- 10:3610:36, 15 February 2023 diff hist +378 N Goldberg & Rao (Integer Maximum Flow Maximum Flow) Created page with "== Time Complexity == $O(E^{1.5} Log(V^{2}/E) LogU)$ == Space Complexity == $O(V + E)$ words (Derived: creates and updates an auxiliary graph) == Description == Finding blocking flows == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1997 == Reference == https://dl.acm.org/citation.cfm?id=290181"
- 10:3610:36, 15 February 2023 diff hist +416 N Phillips & Westbrook (st-Maximum Flow Maximum Flow) Created page with "== Time Complexity == $O(VE(Log(V;V/E)) + V^{2}(LogV)^{2} )$ == Space Complexity == $O(V + E)$ words (Derived: essentially the same as (CH89) above but derandomized) == Description == Derandomization of Cheriyan & Hagerup == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1993 == Reference == https://dl.acm.org/citation.cfm?id=167201"
- 10:3610:36, 15 February 2023 diff hist +401 N King et al. (KRT) (st-Maximum Flow Maximum Flow) Created page with "== Time Complexity == $O(VE + V^{({2}+eps)})$ == Space Complexity == $O(V + E)$ words (Derived: essentially the same as (CH89) above but derandomized) == Description == Derandomization of Cheriyan & Hagerup == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1992 == Reference == https://dl.acm.org/citation.cfm?id=139438"
- 10:3610:36, 15 February 2023 diff hist +429 N Alon (st-Maximum Flow Maximum Flow) Created page with "== Time Complexity == $O(VE + V^{({2.66})}LogV)$ == Space Complexity == $O(V + E)$ words (Derived: essentially the same as (CH89) above but derandomized) == Description == Derandomization of Cheriyan & Hagerup == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1990 == Reference == https://www.sciencedirect.com/science/article/pii/002001909090024R"
- 10:3610:36, 15 February 2023 diff hist +446 N Cheriyan et al. (st-Maximum Flow Maximum Flow) Created page with "== Time Complexity == $O(V^{3} / LogV)$ == Space Complexity == $O(V + E)$ words (Derived: essentially the same as (CH89) above but derandomized) == Description == Derandomization of Cheriyan & Hagerup == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Uniform-Cost RAM (is this the same as Word RAM?) == Year == 1990 == Reference == https://link.springer.com/chapter/10.1007/BFb0032035"
- 10:3610:36, 15 February 2023 diff hist +436 N Cheriyan & Hagerup (st-Maximum Flow Maximum Flow) Created page with "== Time Complexity == $O(VE*log(V))$ == Space Complexity == $O(V + E)$ words (Derived: d_heap and e_heap are size O(V). Adjacency list of a given vertex is O(V). Dynamic trees data structure is size O(E).) == Description == Push-relabel method == Approximate? == Exact == Randomized? == Yes, Las Vegas == Model of Computation == Word RAM == Year == 1989 == Reference == https://ieeexplore.ieee.org/document/63465"
- 10:3610:36, 15 February 2023 diff hist +379 N Ahuja & Orlin ( Maximum Flow) Created page with "== Time Complexity == $O(VE + V^{2}LogU)$ == Space Complexity == $O(ELogU)$ words (derived in sheet) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1987 == Reference == https://www.researchgate.net/publication/38008130_A_Fast_and_Simple_Algorithm_for_the_Maximum_Flow_Problem"
- 10:3610:36, 15 February 2023 diff hist +410 N Goldberg & Tarjan ( Maximum Flow) Created page with "== Time Complexity == $O(VELog(V^{2}/E))$ == Space Complexity == $O(E)$ words (can be derived? also hints of space complexity might be in the paper) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1986 == Reference == https://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/a%20new%20approach.pdf"
- 10:3610:36, 15 February 2023 diff hist +326 N Sleator & Tarjan ( Maximum Flow) Created page with "== Time Complexity == $O(VELogV)$ == Space Complexity == $O(E)$ words (can be derived?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1983 == Reference == https://www.sciencedirect.com/science/article/pii/0022000083900065"
- 10:3510:35, 15 February 2023 diff hist +366 N Cherkassky ( Maximum Flow) Created page with "== Time Complexity == $O(V^{2}E^{0.5})$ == 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 == 1977 == Reference == https://www.sciencedirect.com/science/article/abs/pii/S037722179600269X" current
- 10:3510:35, 15 February 2023 diff hist +363 N 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:3510:35, 15 February 2023 diff hist +310 N 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:3510:35, 15 February 2023 diff hist +389 N 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" current
- 10:3510:35, 15 February 2023 diff hist +381 N 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" current
- 10:3510:35, 15 February 2023 diff hist +326 N 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:3510:35, 15 February 2023 diff hist +267 N 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 == -" current
- 10:3510:35, 15 February 2023 diff hist +399 N 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:3510:35, 15 February 2023 diff hist +311 N 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" current
- 10:3510:35, 15 February 2023 diff hist +386 N 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" current
- 10:3510:35, 15 February 2023 diff hist +303 N 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:3510:35, 15 February 2023 diff hist +275 N 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:3510:35, 15 February 2023 diff hist +326 N 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:3510:35, 15 February 2023 diff hist +431 N 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:3510:35, 15 February 2023 diff hist +361 N 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" current
- 10:3510:35, 15 February 2023 diff hist +327 N 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" current
- 10:3510:35, 15 February 2023 diff hist +331 N 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" current
- 10:3510:35, 15 February 2023 diff hist +329 N 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" current
- 10:3510:35, 15 February 2023 diff hist +349 N 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" current
- 10:3510:35, 15 February 2023 diff hist +269 N 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 == -" current
- 10:3510:35, 15 February 2023 diff hist +363 N 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:3510:35, 15 February 2023 diff hist +281 N 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:3510:35, 15 February 2023 diff hist +326 N 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" current
- 10:3510:35, 15 February 2023 diff hist +397 N 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" current
- 10:3510:35, 15 February 2023 diff hist +402 N 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" current
- 10:3510:35, 15 February 2023 diff hist +654 N 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..." current
- 10:3510:35, 15 February 2023 diff hist +462 N 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:3510:35, 15 February 2023 diff hist +385 N 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:3510:35, 15 February 2023 diff hist +412 N 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:3510:35, 15 February 2023 diff hist +392 N 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:3510:35, 15 February 2023 diff hist +408 N 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:3510:35, 15 February 2023 diff hist +303 N 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" current
- 10:3510:35, 15 February 2023 diff hist +307 N 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" current
- 10:3510:35, 15 February 2023 diff hist +305 N 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:3510:35, 15 February 2023 diff hist +307 N 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" current
- 10:3510:35, 15 February 2023 diff hist +322 N 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 ==" current
- 10:3510:35, 15 February 2023 diff hist +367 N 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" current
- 10:3510:35, 15 February 2023 diff hist +305 N 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" current
- 10:3510:35, 15 February 2023 diff hist +455 N 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" current