New pages
Jump to navigation
Jump to search
(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)
- 11:17, 15 February 2023 Trial Multiplication (Discrete Logarithm Over Finite Fields Logarithm Calculations) (hist | edit) [430 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O({1})$ words (Derived: Each power $k$ that you try in the brute force search is size $O(\log n)$, which is $O(1)$ when considering $O(\log n)$ size words. Only need to keep track of one at a time.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == NA")
- 11:17, 15 February 2023 Rautiainen, Marschall (Sequence-to-Graph Alignment Sequence-to-Graph Alignment) (hist | edit) [499 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(|V | + m|E|)$ == Space Complexity == $O(mV)$ words (Derived: algorithm uses a V-sized array of bitvectors each of which is of length m, and also uses a priority queue which has at most V elements. The precomputed pattern bitvectors also takes up O(V * m) space.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2019 == Reference == https://www.ncb...")
- 11:17, 15 February 2023 Jain, Chang (Sequence-to-Graph Alignment Sequence-to-Graph Alignment) (hist | edit) [358 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(|V | + m|E|)$ == Space Complexity == $O(V)$ words (https://www.biorxiv.org/content/10.1101/522912v1.full.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2019 == Reference == https://www.biorxiv.org/content/10.1101/522912v1.full.pdf")
- 11:17, 15 February 2023 Rautiainen and Marschall (Sequence-to-Graph Alignment Sequence-to-Graph Alignment) (hist | edit) [348 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(|V | + m|E|)$ == Space Complexity == $O(\sqrt(m)|V|)$ words (same paper) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2017 == Reference == https://www.biorxiv.org/content/10.1101/216127v1")
- 11:17, 15 February 2023 V-ALIGN (Sequence-to-Graph Alignment Sequence-to-Graph Alignment) (hist | edit) [369 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(m|V |E|)$ == Space Complexity == $O(mV)$ words (https://www.biorxiv.org/content/10.1101/124941v1.full) == Description == Dynamic Programming == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2018 == Reference == https://www.biorxiv.org/content/10.1101/124941v1.full")
- 11:17, 15 February 2023 HybridSpades (Sequence-to-Graph Alignment Sequence-to-Graph Alignment) (hist | edit) [306 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(m(|V | log(m|V |)$ + |E|)) == Space Complexity == $O(m*(V+E)$) words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2015 == Reference == https://www.ncbi.nlm.nih.gov/pubmed/26589280")
- 11:17, 15 February 2023 Navarro (Sequence-to-Graph Alignment Sequence-to-Graph Alignment) (hist | edit) [382 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n(|V | + |E|)$) == Space Complexity == $O(V)$ words (same paper) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2000 == Reference == https://www.sciencedirect.com/science/article/pii/S0304397599003333")
- 11:17, 15 February 2023 Amir et al. (Sequence-to-Graph Alignment Sequence-to-Graph Alignment) (hist | edit) [380 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(m(|n | log |m | + |E|)$) == Space Complexity == $O(mn)$ words (https://reader.elsevier.com/reader/sd/pii/S0304397599003333?token=C0E6BDF7BA98CD5C338EDB86675CB3A29AF44F5B046E169EE0F115788255757C815F0F0307EAF080CDF9A9DE7AA37764) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1997 == Reference == https://link.springer.com/chapter/10.1007/3-540-633...")
- 11:17, 15 February 2023 PSLQ algorithm (Integer Relation Integer Relation) (hist | edit) [431 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$ words (Derived: Uses multiple nxn auxiliary matrices) == Description == Partial Sum of Squares using QR decomposition == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1992 == Reference == https://www.ams.org/journals/mcom/1999-68-225/S0025-5718-99-00995-3/S0025-5718-99-00995-3.pdf")
- 11:17, 15 February 2023 PSOS algorithm (Integer Relation Integer Relation) (hist | edit) [416 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$ words (Derived: Uses multiple nxn auxiliary matrices) == Description == Partial Sum of Squares == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1988 == Reference == https://www.ams.org/journals/mcom/1989-53-188/S0025-5718-1989-0979934-9/S0025-5718-1989-0979934-9.pdf")
- 11:17, 15 February 2023 LLL algorithm (Integer Relation Integer Relation) (hist | edit) [399 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{4})$ == Space Complexity == $O(n^{2})$ words (Derived: Uses n auxiliary vectors each of length n, as well as an nxn matrix) == Description == Lattice-based == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1982 == Reference == https://www.math.leidenuniv.nl/~hwl/PUBLICATIONS/1982f/art.pdf")
- 11:17, 15 February 2023 Ferguson–Forcade algorithm (Integer Relation Integer Relation) (hist | edit) [388 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$ words (Derived: Uses auxiliary $n\times n$ matrices) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1979 == Reference == https://www.ams.org/journals/bull/1979-01-06/S0273-0979-1979-14691-3/S0273-0979-1979-14691-3.pdf")
- 11:17, 15 February 2023 Bareiss algorithm with fast multiplication (Determinant of Matrices with Integer Entries Determinant of Matrices with Integer Entries) (hist | edit) [413 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{4}L(log(n)$ + L)log(log(n) + L)) == Space Complexity == $O(n^{2}(n*log(n)$+nL)) bits (Keeps track of $O(n^2)$ entries that have absolute value at most $O(n^{(n/2)}2^{(nL)})$) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? (without O(1) multiplication) == Year == 1968 == Reference == -")
- 11:17, 15 February 2023 Bareiss algorithm (Determinant of Matrices with Integer Entries Determinant of Matrices with Integer Entries) (hist | edit) [507 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{5}L^{2} (log(n)$^{2} + L^{2})) == Space Complexity == $O(n^{2}(n*log(n)$+nL)) bits (Keeps track of $O(n^2)$ entries that have absolute value at most $O(n^{(n/2)}2^{(nL)})$) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? (without O(1) multiplication) == Year == 1968 == Reference == https://www.ams.org/journals/mcom/1968-22-103/S0025-5718-1968-0226829-0...")
- 11:16, 15 February 2023 Ruchansky (Minimum Wiener Connector problem Wiener Index) (hist | edit) [452 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(q(m*log(n)$+n*log^{2}(n))) == Space Complexity == $O(q(m+n*log(n)$)? words (Keeps track of $O(qm)$ shortest-path distances and $O(q*log(n))$ approximate Steiner trees, each of size $O(n)$) == Description == == Approximate? == Approximate Approximation Factor: O(1) == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2015 == Reference == https://arxiv.org/abs/1504.00513")
- 11:16, 15 February 2023 Dunning; Gupta & Silberholz (Maximum Cut, Approximate Maximum Cut) (hist | edit) [297 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(VE)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2018 == Reference == https://pubsonline.informs.org/doi/epdf/10.1287/ijoc.2017.0798")
- 11:16, 15 February 2023 LEE Y.; KIM H. S.; LEE S 2002 (Mesh Parameterization Mesh Parameterization) (hist | edit) [302 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n log^{3}n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2002 == Reference == https://www.sciencedirect.com/science/article/abs/pii/S0097849302001231")
- 11:16, 15 February 2023 PINKALL U.; POLTHIER K 1993 (Mesh Parameterization Mesh Parameterization) (hist | edit) [274 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1993 == Reference == http://www.cs.jhu.edu/~misha/Fall09/Pinkall93.pdf")
- 11:16, 15 February 2023 FLOATER 1997 (Mesh Parameterization Mesh Parameterization) (hist | edit) [274 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1997 == Reference == http://www.cs.jhu.edu/~misha/Fall09/Floater97.pdf")
- 11:16, 15 February 2023 ECK M.; DEROSE T.; DUCHAMP T.; 1995 (Mesh Parameterization Mesh Parameterization) (hist | edit) [269 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1995 == Reference == https://dl.acm.org/doi/10.1145/218380.218440")
- 11:16, 15 February 2023 B. I. Kvasov 2000 (Hyperbolic Spline Interpolation Hyperbolic Spline Interpolation) (hist | edit) [222 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{4})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2000 == Reference ==")
- 11:16, 15 February 2023 P. Costantini; B. I. Kvasov; and C. Manni 1999 (Hyperbolic Spline Interpolation Hyperbolic Spline Interpolation) (hist | edit) [409 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{5} logK)$ == Space Complexity == $O(n)$? words (Derived: Pentadiagonal matrix in the linear system only requires O(n) space) == Description == Pentadiagonal linear system == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1999 == Reference == https://link.springer.com/article/10.1023/A:1018988312596")
- 11:16, 15 February 2023 V. I. Paasonen 1968 (Hyperbolic Spline Interpolation Hyperbolic Spline Interpolation) (hist | edit) [227 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{5} logK)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1968 == Reference ==")
- 11:16, 15 February 2023 V. A. Lyul’ka and I. E. Mikhailov 2003 (Hyperbolic Spline Interpolation Hyperbolic Spline Interpolation) (hist | edit) [316 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{4})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2003 == Reference == http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=zvmmf&paperid=943&option_lang=eng")
- 11:16, 15 February 2023 V. A. Lyul’ka and A. V. Romanenko 1994 (Hyperbolic Spline Interpolation Hyperbolic Spline Interpolation) (hist | edit) [261 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{5})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1994 == Reference == https://www.mathnet.ru/eng/zvmmf2544")
- 11:16, 15 February 2023 Kvasov 2006 (Hyperbolic Spline Interpolation Hyperbolic Spline Interpolation) (hist | edit) [293 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3} log^{2}K)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2008 == Reference == https://link.springer.com/article/10.1134/S0965542508040039")
- 11:16, 15 February 2023 Adaptive Duplicate Detection Algorithm (ADD) (Duplicate Elimination Duplicate Elimination) (hist | edit) [384 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O({1})$ words (Derived: For SVM, only need to store a constant number of support vectors) == Description == SVM string similarity == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2003 == Reference == https://dl.acm.org/doi/10.1145/956750.956759")
- 11:16, 15 February 2023 Sorted Neighborhood Algorithm (SNA) (Duplicate Elimination Duplicate Elimination) (hist | edit) [362 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words (Derived: store a key for each entry in the "Create Key" phase) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1998 == Reference == https://link.springer.com/article/10.1023/A:1009761603038")
- 11:16, 15 February 2023 Duplicate Elimination Sorted Neighborhood Algorithm (DE-SNA) (Duplicate Elimination Duplicate Elimination) (hist | edit) [225 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2002 == Reference ==")
- 11:16, 15 February 2023 Priority Queue Algorithm (Duplicate Elimination Duplicate Elimination) (hist | edit) [331 bytes] Admin (talk | contribs) (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 BST Algorithm (Duplicate Elimination Duplicate Elimination) (hist | edit) [302 bytes] Admin (talk | contribs) (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 Sorting based (Merge Sort) + real-time elimination (Duplicate Elimination Duplicate Elimination) (hist | edit) [225 bytes] Admin (talk | contribs) (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 Sorting based (Merge Sort) (Duplicate Elimination Duplicate Elimination) (hist | edit) [279 bytes] Admin (talk | contribs) (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 Berger & Müller-Hannemann (DAG Realization Problem Graph Realization Problems) (hist | edit) [272 bytes] Admin (talk | contribs) (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 Fulkerson–Chen–Anstee (Digraph Realization Problem Graph Realization Problems) (hist | edit) [841 bytes] Admin (talk | contribs) (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 Kleitman–Wang Algorithm (Digraph Realization Problem Graph Realization Problems) (hist | edit) [425 bytes] Admin (talk | contribs) (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 Babai & Codenotti (Hypergraphs isomorphism Graph Isomorphism Problem) (hist | edit) [295 bytes] Admin (talk | contribs) (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 Bodlaender (Partial k-trees Graph Isomorphism Problem) (hist | edit) [317 bytes] Admin (talk | contribs) (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 Muzychuk (Circulant graphs Graph Isomorphism Problem) (hist | edit) [341 bytes] Admin (talk | contribs) (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 Babai ( Graph Isomorphism Problem) (hist | edit) [342 bytes] Admin (talk | contribs) (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 Ullman (Subgraph Isomorphism Graph Isomorphism Problem) (hist | edit) [259 bytes] Admin (talk | contribs) (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 Schmidt & Druffel ( Graph Isomorphism Problem) (hist | edit) [307 bytes] Admin (talk | contribs) (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 Spielman (Isomorphism of strongly regular graphs Graph Isomorphism Problem) (hist | edit) [315 bytes] Admin (talk | contribs) (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 McKay ( Graph Isomorphism Problem) (hist | edit) [338 bytes] Admin (talk | contribs) (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 Babai (Graph Isomorphism, Bounded Number of Vertices of Each Color Graph Isomorphism Problem) (hist | edit) [364 bytes] Admin (talk | contribs) (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 Babai and Luks (Graph Isomorphism, General Graphs Graph Isomorphism Problem) (hist | edit) [349 bytes] Admin (talk | contribs) (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 Sethi–Ullman Algorithm (Arithmetic Expression Binary Tree AST to Code Translation) (hist | edit) [368 bytes] Admin (talk | contribs) (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 Demand-Driven Register Allocation (Global Register Allocation Register Allocation) (hist | edit) [401 bytes] Admin (talk | contribs) (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 Gusfield (Longest Palindromic Substring Longest Palindromic Substring) (hist | edit) [537 bytes] Admin (talk | contribs) (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 Jeuring (Longest Palindromic Substring Longest Palindromic Substring) (hist | edit) [377 bytes] Admin (talk | contribs) (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")