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)

• 11:16, 15 February 2023 Admin talk contribs created page Priority Queue Algorithm (Duplicate Elimination Duplicate Elimination) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words (Derived: Auxiliary space needed for the priority queue) == Description == Selection sort using priority queue? == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference ==")
• 11:16, 15 February 2023 Admin talk contribs created page BST Algorithm (Duplicate Elimination Duplicate Elimination) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(\log n)$ words (Derived: Space required for the recursion stack space) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1999 == Reference ==")
• 11:16, 15 February 2023 Admin talk contribs created page Sorting based (Merge Sort) + real-time elimination (Duplicate Elimination Duplicate Elimination) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1964 == Reference ==")
• 11:16, 15 February 2023 Admin talk contribs created page Sorting based (Merge Sort) (Duplicate Elimination Duplicate Elimination) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (Derived: linear space for mergesort) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1964 == Reference ==")
• 11:16, 15 February 2023 Admin talk contribs created page Berger & Müller-Hannemann (DAG Realization Problem Graph Realization Problems) (Created page with "== Time Complexity == $O(\exp(n)$) == Space Complexity == ? words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2011 == Reference == https://arxiv.org/abs/1203.3636")
• 11:16, 15 February 2023 Admin talk contribs created page Fulkerson–Chen–Anstee (Digraph Realization Problem Graph Realization Problems) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ words (Derived: Checking an inequality that involves 3 summations, of max value $O(n^2)$ each (assuming max degree $\leq n$) which is $O(1)$ words in our Word RAM. We check this inequality for each $k = 1, \ldots, n$, but you can store the summations dynamically, so you only need to run $O(1)$ operations per iteration) == Description == Makes use of (0,1) matrix properties, checks a property of the inp...")
• 11:16, 15 February 2023 Admin talk contribs created page Kleitman–Wang Algorithm (Digraph Realization Problem Graph Realization Problems) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ words (Derived: Space complexity bounded by time complexity; keep track of a constant number of sets of size $O(n)$) == Description == Constructs graph == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1973 == Reference == https://linkinghub.elsevier.com/retrieve/pii/0012365X7390037X")
• 11:16, 15 February 2023 Admin talk contribs created page Bodlaender (Partial k-trees Graph Isomorphism Problem) (Created page with "== Time Complexity == $O(n^{(k+{4.5})})$ == Space Complexity == check words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1990 == Reference == https://www.sciencedirect.com/science/article/pii/0196677490900135")
• 11:16, 15 February 2023 Admin talk contribs created page Babai & Codenotti (Hypergraphs isomorphism Graph Isomorphism Problem) (Created page with "== Time Complexity == $exp(O(k^{2} \sqrt{n})$ == Space Complexity == check words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2008 == Reference == https://oa.mg/work/10.1109/focs.2008.80")
• 11:16, 15 February 2023 Admin talk contribs created page Muzychuk (Circulant graphs Graph Isomorphism Problem) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (derived in notes) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2004 == Reference == https://londmathsoc.onlinelibrary.wiley.com/doi/abs/10.1112/S0024611503014412")
• 11:16, 15 February 2023 Admin talk contribs created page Babai ( Graph Isomorphism Problem) (Created page with "== Time Complexity == {2}^{$O(\log n)$^3} == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2017 == Reference == http://people.cs.uchicago.edu/~laci/update.html, http://people.cs.uchicago.edu/~laci/17groups/version2.1.pdf")
• 11:16, 15 February 2023 Admin talk contribs created page Ullman (Subgraph Isomorphism Graph Isomorphism Problem) (Created page with "== Time Complexity == == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1976 == Reference == https://dl.acm.org/doi/10.1145/321921.321925")
• 11:16, 15 February 2023 Admin talk contribs created page Schmidt & Druffel ( Graph Isomorphism Problem) (Created page with "== Time Complexity == $O(n*n!)$ == Space Complexity == $O(n^{2})$ words (derived in sheet) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == https://dl.acm.org/doi/10.1145/321958.321963")
• 11:16, 15 February 2023 Admin talk contribs created page Spielman (Isomorphism of strongly regular graphs Graph Isomorphism Problem) (Created page with "== Time Complexity == $n^{O(n^{({1}/{3})} log n)}$ == Space Complexity == check words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1996 == Reference == https://www.cs.yale.edu/homes/spielman/PAPERS/srg.pdf")
• 11:16, 15 February 2023 Admin talk contribs created page McKay ( Graph Isomorphism Problem) (Created page with "== Time Complexity == $O((m1 + m2)n^{3} + m2 n^{2} L)$ == Space Complexity == ${2}mn+{10}n+m+(m+{4})K+{2}mL$ words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1981 == Reference == http://users.cecs.anu.edu.au/~bdm/papers/pgi.pdf")
• 11:16, 15 February 2023 Admin talk contribs created page Babai (Graph Isomorphism, Bounded Number of Vertices of Each Color Graph Isomorphism Problem) (Created page with "== Time Complexity == o(\exp({2}n^{1/2}\log^{2}n)) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1980 == Reference == https://epubs.siam.org/doi/10.1137/0209018")
• 11:16, 15 February 2023 Admin talk contribs created page Babai and Luks (Graph Isomorphism, General Graphs Graph Isomorphism Problem) (Created page with "== Time Complexity == \exp(n^{\frac{1}{2} + o({1})}) == Space Complexity == words () == Description == Construct canonical forms of graphs and compare == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1983 == Reference == https://dl.acm.org/doi/10.1145/800061.808746")
• 11:16, 15 February 2023 Admin talk contribs created page Sethi–Ullman Algorithm (Arithmetic Expression Binary Tree AST to Code Translation) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ words (Derived: Only uses in-situ updates to the input tree, no auxiliary data structures) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1970 == Reference == https://dl.acm.org/doi/10.1145/321607.321620")
• 11:16, 15 February 2023 Admin talk contribs created page Demand-Driven Register Allocation (Global Register Allocation Register Allocation) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (Derived: Requires storing a so-called $\Delta$-table of size $n \times n$ to keep track of $\Delta$-estimates) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1996 == Reference == https://dl.acm.org/doi/10.1145/236114.236117")
• 11:16, 15 February 2023 Admin talk contribs created page Gusfield (Longest Palindromic Substring Longest Palindromic Substring) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ auxiliary words (At the very least it pre-processes and stores the string and the reverse of the string, requiring O(n) space. Space usage is bounded from above by runtime, so at most O(n) space is used.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1997 == Reference == https://www.cambridge.org/core/books/al...")
• 11:16, 15 February 2023 Admin talk contribs created page Jeuring (Longest Palindromic Substring Longest Palindromic Substring) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ auxiliary? words (Stores (and uses) previously computed palindrome information; unclear if O(n) is best bound possible) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1994 == Reference == https://doi.org/10.1007%2FBF01182773")
• 11:16, 15 February 2023 Admin talk contribs created page Manacher (Longest Palindromic Substring Longest Palindromic Substring) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ auxiliary words (At the very least it stores the radii for each center, requiring O(n) space. Space usage is bounded from above by runtime, so at most O(n) space is used.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1975 == Reference == https://doi.org/10.1145%2F321892.321896")
• 11:16, 15 February 2023 Admin talk contribs created page Dynamic Programming (Longest Palindromic Substring Longest Palindromic Substring) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (https://www.geeksforgeeks.org/longest-palindrome-substring-set-1/) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1953 == Reference == -")
• 11:16, 15 February 2023 Admin talk contribs created page Naive (Longest Palindromic Substring Longest Palindromic Substring) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O({1})$ auxiliary words (https://www.geeksforgeeks.org/longest-palindrome-substring-set-1/) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == -")
• 11:16, 15 February 2023 Admin talk contribs created page Record linking (Entity Resolution Entity Resolution) (Created page with "== Time Complexity == $O(n^{2}k)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1993 == Reference ==")
• 11:16, 15 February 2023 Admin talk contribs created page Ananthakrishna (Entity Resolution Entity Resolution) (Created page with "== Time Complexity == $O(n^{2} k)$ == Space Complexity == $O(n)$ words (Derived: the token table, the children table, and the tuples in G are stored in main memory, each are of size $O(n)$) == Description == Delphi algorithm == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2002 == Reference == https://doi.org/10.1016/B978-155860869-6/50058-5")
• 11:16, 15 February 2023 Admin talk contribs created page Bellare Active Learning (Entity Resolution Entity Resolution) (Created page with "== Time Complexity == $O(n^{2} logn clogc)$ == Space Complexity == () == Description == Pairwise ER Active Learning == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2012 == Reference == https://dl.acm.org/doi/10.1145/2339530.2339707")
• 11:16, 15 February 2023 Admin talk contribs created page EM Based Winkler (Entity Resolution Entity Resolution) (Created page with "== Time Complexity == $O(n^{3}k)$ == Space Complexity == $O(k)$ words (Derived: One value per feature in the discretized vector) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2000 == Reference == https://courses.cs.washington.edu/courses/cse590q/04au/papers/WinklerEM.pdf")
• 11:16, 15 February 2023 Admin talk contribs created page Ravikumar & Cohen Generative Models (Entity Resolution Entity Resolution) (Created page with "== Time Complexity == $O(n^{2} k)$ == Space Complexity == $O(k)$ words (Derived: One value per feature in the discretized vector) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2004 == Reference == https://arxiv.org/abs/1207.4180")
• 11:16, 15 February 2023 Admin talk contribs created page Chen Ensembles of classifiers (Entity Resolution Entity Resolution) (Created page with "== Time Complexity == $O(n^{2} logn)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1989 == Reference ==")
• 11:16, 15 February 2023 Admin talk contribs created page Gupta & Sarawagi CRF (Entity Resolution Entity Resolution) (Created page with "== Time Complexity == $O(n^{3}k)$ == Space Complexity == () == Description == Bipartite method to compute pairwise ER == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2009 == Reference == https://doi.org/10.14778/1687627.1687661")
• 11:16, 15 February 2023 Admin talk contribs created page Fellegi & Sunter Model (Entity Resolution Entity Resolution) (Created page with "== Time Complexity == $O(n^{3}k)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1969 == Reference == https://www.tandfonline.com/doi/abs/10.1080/01621459.1969.10501049")
• 11:16, 15 February 2023 Admin talk contribs created page McCreight (Constructing Suffix Trees Constructing Suffix Trees) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ words (Needs to store the intermediate steps of constructing a suffix tree, which can reach size O(n)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == http://libeccio.di.unisa.it/TdP/suffix.pdf")
• 11:16, 15 February 2023 Admin talk contribs created page Farach (Constructing Suffix Trees Constructing Suffix Trees) (Created page with "== Time Complexity == $O(log n)$ == Space Complexity == $O(n)$ words (https://www.cs.rutgers.edu/~farach/pubs/PRAMSuffixICALP.pdf) == Description == == Approximate? == Exact == Randomized? == Yes, Las Vegas == Model of Computation == CRCW PRAM == Year == 1997 == Reference == https://www.cs.rutgers.edu/~farach/pubs/PRAMSuffixICALP.pdf")
• 11:16, 15 February 2023 Admin talk contribs created page Rytter (Constructing Suffix Trees Constructing Suffix Trees) (Created page with "== Time Complexity == $O(logn)$ == Space Complexity == $O(n)$ words (https://www.researchgate.net/publication/228945502_On_parallel_transformations_of_suffix_arrays_into_suffix_trees) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == CREW PRAM == Year == 2004 == Reference == https://www.researchgate.net/publication/228945502_On_parallel_transformations_of_suffix_arrays_into_suffix_trees")
• 11:16, 15 February 2023 Admin talk contribs created page Süleyman Cenk Sahinalp ; Uzi Vishkin (Constructing Suffix Trees Constructing Suffix Trees) (Created page with "== Time Complexity == $O(log^{2}(n)$) == Space Complexity == $O(n^{({1}+\eps)})$ for any fixed eps>{0} words (https://link.springer.com/content/pdf/10.1007/3-540-57811-0_3.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == CRCW PRAM == Year == 1994 == Reference == https://link.springer.com/content/pdf/10.1007/3-540-57811-0_3.pdf")
• 11:16, 15 February 2023 Admin talk contribs created page Hariharan (Constructing Suffix Trees Constructing Suffix Trees) (Created page with "== Time Complexity == $O(log^{4}(n)$) == Space Complexity == $O(n)$ words (https://www.sciencedirect.com/science/article/pii/S0022000097914963) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == CREW PRAM == Year == 1997 == Reference == https://www.sciencedirect.com/science/article/pii/S0022000097914963")
• 11:16, 15 February 2023 Admin talk contribs created page Ukkonen and D. Wood (Constructing Suffix Trees Constructing Suffix Trees) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (https://link.springer.com/article/10.1007/BF01769703) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1993 == Reference == https://link.springer.com/article/10.1007/BF01769703")
• 11:16, 15 February 2023 Admin talk contribs created page Ukkonen (Constructing Suffix Trees Constructing Suffix Trees) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ words (Needs to store the intermediate steps of constructing a suffix tree, which can reach size O(n)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1995 == Reference == https://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf")
• 11:16, 15 February 2023 Admin talk contribs created page Pratt (Constructing Suffix Trees Constructing Suffix Trees) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1973 == Reference == -")
• 11:16, 15 February 2023 Admin talk contribs created page Weiner's algorithm (Constructing Suffix Trees Constructing Suffix Trees) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ words (Needs to store the intermediate steps of constructing a suffix tree, which can reach size O(n)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1973 == Reference == https://dl.acm.org/citation.cfm?id=1441766")
• 11:16, 15 February 2023 Admin talk contribs created page Ioannidou; Kyriaki; Mertzios; George B.; Nikolopoulos; Stavros D. (Longest Path on Interval Graphs Longest Path Problem) (Created page with "== Time Complexity == $O(n^{4})$ == Space Complexity == $O(n^{3})$ words (https://link.springer.com/content/pdf/10.1007/s00453-010-9411-3.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2011 == Reference == https://community.dur.ac.uk/george.mertzios/papers/Conf/Conf_Longest-Interval.pdf")
• 11:16, 15 February 2023 Admin talk contribs created page Naive (Constructing Suffix Trees Constructing Suffix Trees) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words (Needs to store the intermediate steps of constructing a suffix tree, which can reach size O(n)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1973 == Reference == -")
• 11:16, 15 February 2023 Admin talk contribs created page Patrick Posser (Stable Roommates Problem Stable Matching Problem) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n)$ words (https://link.springer.com/chapter/10.1007%2F978-3-319-07046-9_2) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2014 == Reference == https://link.springer.com/chapter/10.1007%2F978-3-319-07046-9_2")
• 11:16, 15 February 2023 Admin talk contribs created page S. S. TSENG and R. C. T. LEE (Stable Marriage Problem Stable Matching Problem) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ per processor? words (Only need to keep track of current (provisional) matchings) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1984 == Reference == https://link.springer.com/content/pdf/10.1007/BF02136029.pdf")
• 11:16, 15 February 2023 Admin talk contribs created page Unsworth; C.; Prosser; P (Stable Marriage Problem Stable Matching Problem) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$? words (Constructs, preprocesses, and solves an $O(n^2)$-size CSP instance? (see original reference)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2005 == Reference == http://www.dcs.gla.ac.uk/~pat/roommates/distribution/papers/SM2N.pdf")
• 11:16, 15 February 2023 Admin talk contribs created page Gent; I.P.; Irving; R.W.; Manlove; D.F.; Prosser; P.; Smith; B.M. (Stable Marriage Problem Stable Matching Problem) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$? words (Constructs, preprocesses, and solves an O(n^2)-size CSP instance?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2001 == Reference == https://link.springer.com/chapter/10.1007/3-540-45578-7_16")
• 11:16, 15 February 2023 Admin talk contribs created page Gaussian Elimination (Exact Laplacian Solver SDD Systems Solvers) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$ words (Derived: Storing the inverse of the Laplacian) == Description == Use Gaussian elimination to compute the inverse of the Laplacian to solve for x == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == -150 == Reference == -")
• 11:15, 15 February 2023 Admin talk contribs created page 9-point FFT (2-Dimensional Poisson Problem Poisson Problem) (Created page with "== Time Complexity == $O(n^{2} logn)$ == Space Complexity == $O(n^{2})$? words (FFT generally requires aux. space equal to dimension of vector?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1978 == Reference ==")
• 11:15, 15 February 2023 Admin talk contribs created page 5-point cyclic reduction (2-Dimensional Poisson Problem Poisson Problem) (Created page with "== Time Complexity == $O(n^{2} logn)$ == Space Complexity == $O(n^{2})$? words (Generally uses a constant number of n^2*n^2 matrices where O(n^2) entries are nonempty) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1970 == Reference ==")

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