User contributions for Admin
Jump to navigation
Jump to search
15 February 2023
- 10:3210:32, 15 February 2023 diff hist +11 Coppersmith–Winograd algorithm (Matrix Multiplication Matrix Product) No edit summary
- 10:3210:32, 15 February 2023 diff hist −38 Strassen's algorithm (Matrix Multiplication Matrix Product) No edit summary
- 10:3210:32, 15 February 2023 diff hist +340 N 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:3210:32, 15 February 2023 diff hist +339 N 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" current
- 10:3210:32, 15 February 2023 diff hist +370 N 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" current
- 10:3210:32, 15 February 2023 diff hist +407 N 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:3210:32, 15 February 2023 diff hist +278 N 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 == -" current
- 10:3210:32, 15 February 2023 diff hist +337 N 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:3210:32, 15 February 2023 diff hist +351 N 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" current
- 10:3210:32, 15 February 2023 diff hist +365 N 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:3210:32, 15 February 2023 diff hist +392 N 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" current
- 10:3210:32, 15 February 2023 diff hist +362 N 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" current
- 10:3210:32, 15 February 2023 diff hist +370 N 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:3210:32, 15 February 2023 diff hist +253 N 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:3110:31, 15 February 2023 diff hist +258 N 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 == -"
- 10:3110:31, 15 February 2023 diff hist +323 N Hoare's Selection Algorithm (QuickSelect) (kth Order Statistic kth Order Statistic) 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 == 1961 == Reference == https://dl.acm.org/citation.cfm?doid=366622.366647"
- 10:3110:31, 15 February 2023 diff hist +294 N Naive Selection (kth Order Statistic kth Order Statistic) Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O({1})$ (can use in-situ sorting) words (can be easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == -"
- 10:3110:31, 15 February 2023 diff hist +261 N Radix Sort (Non-Comparison Sorting Sorting) Created page with "== Time Complexity == $O(wn)$ == Space Complexity == $O(w+n)$ words ((wikipedia page?)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == -" current
- 10:3110:31, 15 February 2023 diff hist +249 N Bucket Sort (Non-Comparison Sorting Sorting) Created page with "== Time Complexity == $O( n² )$ == Space Complexity == $O(n)$ words (CLRS) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == -" current
- 10:3110:31, 15 February 2023 diff hist +424 N Counting Sort (Non-Comparison Sorting Sorting) Created page with "== Time Complexity == $O(n+k)$ == Space Complexity == $O(n+k)$ words ((can be easily derived)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1954 == Reference == http://bitsavers.org/pdf/mit/whirlwind/R-series/R-232_Information_Sorting_in_the_Application_of_Electronic_Digital_Computers_to_Business_Operations_May54.pdf" current
- 10:3110:31, 15 February 2023 diff hist +353 N Heap Sort (Comparison Sorting Sorting) Created page with "== Time Complexity == $O(n logn)$ == Space Complexity == $O({1})$ (in-situ) words ((can be easily derived)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1964 == Reference == https://www.bibsonomy.org/bibtex/2f485e4ea9a877871b59ab503151a7f10/bjoern"
- 10:3110:31, 15 February 2023 diff hist +398 N Intro Sort (Comparison Sorting Sorting) Created page with "== Time Complexity == $O(n logn)$ == Space Complexity == $O(logn)$ words ((see quicksort + heapsort)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1997 == Reference == https://onlinelibrary.wiley.com/doi/abs/10.1002/%28SICI%291097-024X%28199708%2927%3A8%3C983%3A%3AAID-SPE117%3E3.0.CO%3B2-%23"
- 10:3110:31, 15 February 2023 diff hist +264 N Bubble Sort (Comparison Sorting Sorting) Created page with "== Time Complexity == $O( n² )$ == Space Complexity == $O({1})$ (in-situ) words (in-situ) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1956 == Reference == -"
- 10:3110:31, 15 February 2023 diff hist +308 N Merge Sort (Comparison Sorting Sorting) Created page with "== Time Complexity == $O(n logn)$ == Space Complexity == $O(n)$ words (need some way to store partially processed lists while merging) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1945 == Reference == -"
- 10:3110:31, 15 February 2023 diff hist +264 N Selection Sort (Comparison Sorting Sorting) Created page with "== Time Complexity == $O( n² )$ == Space Complexity == $O({1})$ (in-situ) words (in-situ) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1962 == Reference == -"
- 10:3110:31, 15 February 2023 diff hist +264 N Naive sorting (Comparison Sorting Sorting) Created page with "== Time Complexity == $O( n² )$ == Space Complexity == $O({1})$ (in-situ) words (in-situ) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == -"
- 10:3110:31, 15 February 2023 diff hist +385 N Nivasch ( Cycle Detection) Created page with "== Time Complexity == $O(\mu + \lambda)$ == Space Complexity == $O(logn)$ Stack size (https://www.gabrielnivasch.org/fun/cycle-detection) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == not mentioned == Year == 2004 == Reference == https://drive.google.com/file/d/16H_lrjeaBJqWvcn07C_w-6VNHldJ-ZZl/view" current
- 10:3110:31, 15 February 2023 diff hist +400 N Sedgewick; Szymanski; and Yao ( Cycle Detection) Created page with "== Time Complexity == $(\mu + \lambda)({1}+\Theta({1}/sqrt(M)))$ == Space Complexity == M Memory cells (https://epubs.siam.org/doi/abs/10.1137/0211030?journalCode=smjcat) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1982 == Reference == https://epubs.siam.org/doi/abs/10.1137/0211030?journalCode=smjcat" current
- 10:3110:31, 15 February 2023 diff hist +374 N Grigoryan (n-Queens Completion n-Queens Problem) Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ (Derived: two control arrays of size O(n)) == Description == == Approximate? == Approximate Approximation Factor: error < 0.0001 and decreases with increasing n == Randomized? == Yes, Monte Carlo == Model of Computation == == Year == 2018 == Reference == https://arxiv.org/abs/1912.05935" current
- 10:3110:31, 15 February 2023 diff hist +321 N Spatial GAN-Based; Urs Bergmann, Nikolay Jetchev, Roland Vollgraf (Texture Synthesis Texture Synthesis) Created page with "== Time Complexity == $O(N)$ == Space Complexity == $O(N)$ (https://arxiv.org/abs/1705.06566) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2017 == Reference == https://arxiv.org/abs/1705.06566" current
- 10:3110:31, 15 February 2023 diff hist +373 N Tree-structured vector quantization Wei-Levoy (Texture Synthesis Texture Synthesis) Created page with "== Time Complexity == $O(n^{2} log n)$ == Space Complexity == $O(nd)$ (https://dl.acm.org/doi/abs/10.1145/344779.345009) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == TSVQ Tree == Year == 2000 == Reference == https://dl.acm.org/doi/abs/10.1145/344779.345009" current
- 10:3110:31, 15 February 2023 diff hist +368 N MotifSampler (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 == 2001 == Reference == https://www.ncbi.nlm.nih.gov/pubmed/12015892" current
- 10:3110:31, 15 February 2023 diff hist +387 N Lawrence Gibbs Sampling (Motif Search Motif Search) Created page with "== Time Complexity == $O(nm)$ == Space Complexity == $O(n + m)$ words (derived: two data structures, one uses O(n) and one uses O(m)) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1993 == Reference == https://science.sciencemag.org/content/262/5131/208" current
- 10:3110:31, 15 February 2023 diff hist +358 N Lawrence, Reilly (Motif Search Motif Search) Created page with "== Time Complexity == $O(nm)$ == Space Complexity == $O(nm)$ words (https://www.ncbi.nlm.nih.gov/pubmed/2184437) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1990 == Reference == https://www.ncbi.nlm.nih.gov/pubmed/2184437" current
- 10:3110:31, 15 February 2023 diff hist +358 N Valentin Polishchuk, and Jukka Suomela (Almost Stable Marriage Problem Stable Matching Problem) Created page with "== Time Complexity == $O({1})$ == Space Complexity == $O({1})$ words (derived: must be \leq time complexity) == Description == == Approximate? == Approximate Approximation Factor: 2 + \epsilon == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2008 == Reference == https://arxiv.org/pdf/0812.4893.pdf" current
- 10:3110:31, 15 February 2023 diff hist +346 N Lokshtanov (Subset Sum The Subset-Sum Problem) Created page with "== Time Complexity == $\tilde{O}(n^{3} t)$ == Space Complexity == $O(n^{2})$ (https://dl.acm.org/doi/pdf/10.1145/3329863, Table 1) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2010 == Reference == https://dl.acm.org/doi/abs/10.1145/1806689.1806735" current
- 10:3110:31, 15 February 2023 diff hist −21 Serang (Subset Sum The Subset-Sum Problem) No edit summary Tag: Reverted
- 10:3110:31, 15 February 2023 diff hist +371 N Serang (Subset Sum The Subset-Sum Problem) Created page with "== Time Complexity == $\tilde{O}(n max(S))$ == Space Complexity == $O(t logt)$ (https://dl.acm.org/doi/pdf/10.1145/3329863, Table 1) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2014 == Reference == https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0091507"
- 10:3110:31, 15 February 2023 diff hist +380 N Epstein (Subset Sum The Subset-Sum Problem) Created page with "== Time Complexity == $\tilde{O}(n max(S))$ == Space Complexity == $O(t logt)$ (https://dl.acm.org/doi/pdf/10.1145/3329863, Table 1) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1997 == Reference == https://www.sciencedirect.com/science/article/abs/pii/S019667749690841X?via%3Dihub" current
- 10:3110:31, 15 February 2023 diff hist +371 N Klinz (Subset Sum The Subset-Sum Problem) Created page with "== Time Complexity == $O(σ^{({3}/{2})})$ == Space Complexity == $O(t)$ (https://dl.acm.org/doi/pdf/10.1145/3329863, Table 1) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1999 == Reference == https://doi.org/10.1002/(SICI)1097-0037(199905)33:3%3C189::AID-NET5%3E3.0.CO;2-2" current
- 10:3110:31, 15 February 2023 diff hist +336 N Pferschy (Subset Sum The Subset-Sum Problem) Created page with "== Time Complexity == $O(n' t)$ == Space Complexity == $O(t)$ (https://dl.acm.org/doi/pdf/10.1145/3329863, Table 1) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1999 == Reference == https://link.springer.com/article/10.1007/s006070050042" current
- 10:3110:31, 15 February 2023 diff hist +304 N Faaland (Subset Sum The Subset-Sum Problem) Created page with "== Time Complexity == $O(n' t)$ == Space Complexity == $O(t)$ (https://doi.org/10.1287/opre.21.1.332) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1973 == Reference == https://doi.org/10.1287/opre.21.1.332" current
- 10:3110:31, 15 February 2023 diff hist +369 N Pisinger (Subset Sum The Subset-Sum Problem) Created page with "== Time Complexity == $O(nt/logt)$ == Space Complexity == $O(t/logt)$ words (https://link.springer.com/article/10.1007/s00453-002-0989-y) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2003 == Reference == https://link.springer.com/article/10.1007/s00453-002-0989-y" current
- 10:3110:31, 15 February 2023 diff hist +305 N Compression/Clustering (Vector Quantization) (k Approximate Nearest Neighbors Search (k-ANNS) Nearest Neighbor Search) Created page with "== Time Complexity == Varies by codebook structure == Space Complexity == Varies by codebook structure (Table 2) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 1992 == Reference ==" current
- 10:3110:31, 15 February 2023 diff hist +418 N Projected radial search (k Approximate Nearest Neighbors Search (k-ANNS) for a dense 3D map of geometric points Nearest Neighbor Search) Created page with "== Time Complexity == $O(k)$ == Space Complexity == $O({1})$ words (Derived: There are 5 local variables and no tables or lists aside from input/output) == Description == == Approximate? == Approximate Approximation Factor: ? == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2013 == Reference == http://www.araa.asn.au/acra/acra2013/papers/pap148s1-file1.pdf" current
- 10:3110:31, 15 February 2023 diff hist +474 N Locality-sensitive hashing (k Approximate Nearest Neighbors Search (k-ANNS) Nearest Neighbor Search) Created page with "== Time Complexity == $O(nLkt)$ (pre-processing) $O(L(kt+dnP_2^k))$ (query-time) == Space Complexity == $O(nL)$ hash table cells (https://en.wikipedia.org/wiki/Locality-sensitive_hashing#LSH_algorithm_for_nearest_neighbor_search) == Description == == Approximate? == Approximate Approximation Factor: c == Randomized? == No, deterministic == Model of Computation == == Year == 2010 == Reference == http://infolab.stanford.edu/~ullman/mmds/ch3n.pdf" current
- 10:3110:31, 15 February 2023 diff hist +419 N Hierarchical Navigable Small World (HNSW) (k Approximate Nearest Neighbors Search (k-ANNS) Nearest Neighbor Search) Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(M)$ bytes of memory (https://arxiv.org/abs/1603.09320, "Memory usage is proportional to choice of M") == Description == == Approximate? == Approximate Approximation Factor: ? experimental results == Randomized? == No, deterministic == Model of Computation == == Year == 2018 == Reference == https://doi.org/10.1109/TPAMI.2018.2889473" current
- 10:3110:31, 15 February 2023 diff hist +402 N Larmore (Approximate OBST Optimal Binary Search Trees) Created page with "== Time Complexity == $O(n^{1.6})$ == Space Complexity == $O(n)$ (Derived: Computing and storing f_{d,l} for each n elements) == Description == == Approximate? == Approximate Approximation Factor: \epsilon = o(1) == Randomized? == No, deterministic == Model of Computation == == Year == 1987 == Reference == https://www.sciencedirect.com/science/article/pii/0196677487900526" current
- 10:3110:31, 15 February 2023 diff hist +339 N Klawe; Mumey (Alphabetic Tree Problem Optimal Binary Search Trees) Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ (Derived: uses a worklist of size O(n)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1993 == Reference == https://epubs.siam.org/doi/abs/10.1137/S0895480193256651?journalCode=sjdmec" current
- 10:3110:31, 15 February 2023 diff hist +433 N Karpinski (Approximate OBST Optimal Binary Search Trees) Created page with "== Time Complexity == $O(n^{0.6})$ == Space Complexity == $O({1})$ (Derived: dynamic programming and making use of Monge matrix properties) == Description == == Approximate? == Approximate Approximation Factor: \epsilon = o(1) == Randomized? == No, deterministic == Model of Computation == == Year == 1996 == Reference == https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.54.6940&rep=rep1&type=pdf" current