New pages

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

• 11:15, 15 February 2023 ‎MRRR algorithm (Any eigenpair; Any eigenvalue Eigenvalues (Iterative Methods)) (hist | edit) ‎[426 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n^{2})$ words (Need to compute and store some matrix of the form $(A-mu*I)^{(-1)}$ (for inverse iteration-like uses)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1999 == Reference == https://www.cs.utexas.edu/users/inderjit/public_papers/DesignMRRR_toms06.pdf")
• 11:15, 15 February 2023 ‎Homotopy method (All eigenpairs; Eigenpair closest to mu; Any eigenpair; Any eigenvalue; All eigenvalues Eigenvalues (Iterative Methods)) (hist | edit) ‎[403 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$?? words (Conservative bound on space used per iteration) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1992 == Reference == https://www.scirp.org/(S(czeh2tfqyw2orz553k1w0r45))/reference/ReferencesPapers.aspx?ReferenceID=530065")
• 11:15, 15 February 2023 ‎Folded spectrum method (Eigenpair closest to mu; Any eigenpair; Any eigenvalue Eigenvalues (Iterative Methods)) (hist | edit) ‎[438 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$? words (Requires only a constant number of O(n)-sized vectors per iteration; matrix-to-vector multiplication only requires O(n) aux space) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1934 == Reference == https://journals.aps.org/pr/abstract/10.1103/PhysRev.46.828")
• 11:15, 15 February 2023 ‎Divide-and-conquer (All eigenvalues; Any eigenvalue Eigenvalues (Iterative Methods)) (hist | edit) ‎[411 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n^{2})$ words (Stores reduction to tridiagonal form; recursion (S(n)=2S(n/2)+O(n^2)) should work out to O(n^2)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1986 == Reference == https://link.springer.com/content/pdf/10.1007/BF01389480.pdf")
• 11:15, 15 February 2023 ‎Jacobi eigenvalue algorithm (All eigenvalues; Any eigenvalue Eigenvalues (Iterative Methods)) (hist | edit) ‎[355 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$? words (Computes and stores results of GSG^T iterations) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1846 == Reference == https://gdz.sub.uni-goettingen.de/id/PPN243919689_0030")
• 11:15, 15 February 2023 ‎QR algorithm (All eigenvalues; Any eigenvalue Eigenvalues (Iterative Methods)) (hist | edit) ‎[361 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (Computes and stores QR factorization at each iteration) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1962 == Reference == https://academic.oup.com/comjnl/article/4/4/332/432033")
• 11:15, 15 February 2023 ‎Laguerre iteration (Any eigenvalue Eigenvalues (Iterative Methods)) (hist | edit) ‎[266 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$? words (^ see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1940 == Reference == -")
• 11:15, 15 February 2023 ‎Bisection method (Any eigenvalue Eigenvalues (Iterative Methods)) (hist | edit) ‎[424 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$? words (Computing characteristic polynomial takes $O(n^2)$ space (via e.g. Faddeev–LeVerrier algorithm); rest of algo can be done in $O(n)$ space (related to root computation)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1985 == Reference == -")
• 11:15, 15 February 2023 ‎LOBPCG algorithm (Eigenpair closest to mu; Any eigenpair; Any eigenvalue Eigenvalues (Iterative Methods)) (hist | edit) ‎[320 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$? words (Requires only a constant number of $O(n)$-sized vectors per iteration) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1948 == Reference == -")
• 11:15, 15 February 2023 ‎Rayleigh quotient iteration (Any eigenpair; Any eigenvalue Eigenvalues (Iterative Methods)) (hist | edit) ‎[299 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (Need to compute and store $(A-mu_i*I)^{(-1)}$) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1940 == Reference == -")
• 11:15, 15 February 2023 ‎Inverse iteration (Eigenpair closest to mu; Any eigenpair; Any eigenvalue Eigenvalues (Iterative Methods)) (hist | edit) ‎[360 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (Need to compute and store $(A-mu*I)^{(-1)}$) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1921 == Reference == https://onlinelibrary.wiley.com/doi/abs/10.1002/zamm.19210010104")
• 11:15, 15 February 2023 ‎Weiler–Atherton clipping algorithm (Polygon Clipping with Arbitrary Clipping Polygon Polygon Clipping) (hist | edit) ‎[382 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ auxiliary? words (Needs to keep track of (possibly) $O(n^2)$ intersection points) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1977 == Reference == https://www.cs.drexel.edu/~david/Classes/CS430/HWs/p214-weiler.pdf")
• 11:15, 15 February 2023 ‎Vatti clipping algorithm (Polygon Clipping with Arbitrary Clipping Polygon Polygon Clipping) (hist | edit) ‎[362 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ ? == Space Complexity == $O(n^{2})$ auxiliary? words (Needs to keep track of (possibly) $O(n^2)$ intersection points) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1992 == Reference == https://dl.acm.org/doi/10.1145/129902.129906")
• 11:15, 15 February 2023 ‎Sutherland–Hodgman algorithm (Polygon Clipping with Convex Clipping Polygon Polygon Clipping) (hist | edit) ‎[464 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ auxiliary words (Each iteration, keeps track of updated polygon after clipping by a side. Note that there can be at most $O(n)$ intersection points due to the clipping polygon being convex) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1974 == Reference == https://dl.acm.org/doi/10.1145/360767.360802")
• 11:15, 15 February 2023 ‎Gupta-Sproull algorithm (Line Drawing Line Drawing) (hist | edit) ‎[459 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary words? (Constant number of O(1)-word-sized variables (for determining which pixels to shade and what shading to use) is sufficient) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1981 == Reference == http://www.cs.gettysburg.edu/~ilinkin/courses/Fall-2014/cs373/handouts/papers/gs-fegsd-81.pdf")
• 11:15, 15 February 2023 ‎Greiner–Hormann clipping algorithm (Polygon Clipping with Arbitrary Clipping Polygon Polygon Clipping) (hist | edit) ‎[362 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ ? == Space Complexity == $O(n^{2})$ auxiliary? words (Needs to keep track of (possibly) $O(n^2)$ intersection points) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1998 == Reference == http://davis.wpi.edu/~matt/courses/clipping/")
• 11:15, 15 February 2023 ‎Bresenham's line algorithm (Line Drawing Line Drawing) (hist | edit) ‎[442 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary words? (Constant number of O(1)-word-sized variables (for determining which pixels to shade) is sufficient) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1965 == Reference == https://web.archive.org/web/20080528040104/http://www.research.ibm.com/journal/sj/041/ibmsjIVRIC.pdf")
• 11:15, 15 February 2023 ‎Xiaolin Wu's line algorithm (Line Drawing Line Drawing) (hist | edit) ‎[423 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary words? (Constant number of O(1)-word-sized variables (for determining which pixels to shade and what shading to use) is sufficient) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1991 == Reference == http://www-users.mat.umk.pl/~gruby/teaching/lgim/1_wu.pdf")
• 11:15, 15 February 2023 ‎Digital Differential Analyzer (Line Drawing Line Drawing) (hist | edit) ‎[343 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary words? (Constant number of O(1)-word-sized variables (for determining which pixels to shade) is sufficient) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1940 == Reference == -")
• 11:15, 15 February 2023 ‎Gao’s additive FFT (Discrete Fourier Transform Discrete Fourier Transform) (hist | edit) ‎[378 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n logn loglogn)$ == Space Complexity == $O(n)$ words (https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=5625613) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 2010 == Reference == https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=5625613")
• 11:15, 15 February 2023 ‎Naive algorithm (Line Drawing Line Drawing) (hist | edit) ‎[343 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary words? (Constant number of O(1)-word-sized variables (for determining which pixels to shade) is sufficient) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1940 == Reference == -")
• 11:15, 15 February 2023 ‎Wang-Zhu-Cantor additive FFT (Discrete Fourier Transform Discrete Fourier Transform) (hist | edit) ‎[383 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n(logn)$^{1.{58}5}) == Space Complexity == $O(n)$? words (Computes O(n) remainders per stage; storage space can be reused across stages) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1988 == Reference == https://ieeexplore.ieee.org/document/1926/")
• 11:15, 15 February 2023 ‎Von zur Gathen-Gerhard additive FFT (Discrete Fourier Transform Discrete Fourier Transform) (hist | edit) ‎[346 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n (logn)$^{2}) == Space Complexity == $O(n)$ words (https://dl.acm.org/doi/10.1145/236869.236882) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1996 == Reference == https://dl.acm.org/doi/10.1145/236869.236882")
• 11:15, 15 February 2023 ‎Radix sorting method (General Permutations Generating Random Permutations) (hist | edit) ‎[309 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ words (Need to keep track of randomly generated numbers, but otherwise see radix sort) == Description == == Approximate? == Exact == Randomized? == Yes, ?? == Model of Computation == Word RAM == Year == 1887 == Reference == -")
• 11:15, 15 February 2023 ‎Bergland; Glenn radix-8 algorithm (Discrete Fourier Transform Discrete Fourier Transform) (hist | edit) ‎[340 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (https://ieeexplore.ieee.org/document/1162043) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1969 == Reference == https://ieeexplore.ieee.org/document/1162043")
• 11:15, 15 February 2023 ‎Extended Split Radix FFT algorithm (Discrete Fourier Transform Discrete Fourier Transform) (hist | edit) ‎[351 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$? words (Computes and keeps track of DFTs for recursive subcases) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 2001 == Reference == https://ieeexplore.ieee.org/document/917698")
• 11:15, 15 February 2023 ‎Gentleman; Morven and Gordon Sande radix-4 algorithm (Discrete Fourier Transform Discrete Fourier Transform) (hist | edit) ‎[359 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$? words (Computes and keeps track of DFTs for recursive subcases) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1966 == Reference == http://cis.rit.edu/class/simg716/FFT_Fun_Profit.pdf")
• 11:15, 15 February 2023 ‎Yavne Split Radix FFT algorithm (Discrete Fourier Transform Discrete Fourier Transform) (hist | edit) ‎[350 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$? words (Computes and keeps track of DFTs for recursive subcases) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1968 == Reference == https://dl.acm.org/citation.cfm?id=1476610")
• 11:15, 15 February 2023 ‎Bruun's FFT algorithm (Discrete Fourier Transform Discrete Fourier Transform) (hist | edit) ‎[375 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$? words (Computes O(n) remainders per stage; storage space can be reused across stages) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1978 == Reference == https://ieeexplore.ieee.org/document/1163036/")
• 11:15, 15 February 2023 ‎Rader–Brenner algorithm (Discrete Fourier Transform Discrete Fourier Transform) (hist | edit) ‎[352 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$? words (Computes and keeps track of DFTs for recursive subcases) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1976 == Reference == https://ieeexplore.ieee.org/document/1162805")
• 11:15, 15 February 2023 ‎Naive algorithm (Discrete Fourier Transform Discrete Fourier Transform) (hist | edit) ‎[347 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O({1})$ words (Derived: You only need a constant number of variables that are of $O(1)$ size at any given time) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1965 == Reference == -")
• 11:15, 15 February 2023 ‎Cooley–Tukey algorithm (Discrete Fourier Transform Discrete Fourier Transform) (hist | edit) ‎[409 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$? words (Computes and keeps track of DFTs for recursive subcases) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1965 == Reference == https://www.ams.org/journals/mcom/1965-19-090/S0025-5718-1965-0178586-1/S0025-5718-1965-0178586-1.pdf")
• 11:15, 15 February 2023 ‎Fleury's algorithm + Thorup (Constructing Eulerian Trails in a Graph Constructing Eulerian Trails in a Graph) (hist | edit) ‎[408 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(E log^{3}(E)$ loglogE) == Space Complexity == $O(E)$ words (Keep track of current path + remaining edges needed to be traversed) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2000 == Reference == https://www.cs.princeton.edu/courses/archive/spr10/cos423/handouts/NearOpt.pdf")
• 11:15, 15 February 2023 ‎Hierholzer's algorithm (Constructing Eulerian Trails in a Graph Constructing Eulerian Trails in a Graph) (hist | edit) ‎[308 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(E)$ == Space Complexity == $O(E)$ words (Keep track of current path + remaining edges needed to be traversed) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1873 == Reference == -")
• 11:15, 15 February 2023 ‎Fleury's algorithm + Tarjan (Constructing Eulerian Trails in a Graph Constructing Eulerian Trails in a Graph) (hist | edit) ‎[401 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(E^{2})$ == Space Complexity == $O(E)$ words (Keep track of current path + remaining edges needed to be traversed) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1974 == Reference == https://collaborate.princeton.edu/en/publications/a-note-on-finding-the-bridges-of-a-graph")
• 11:15, 15 February 2023 ‎Mucha and Sankowski ( Maximum-Weight Matching) (hist | edit) ‎[268 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2004 == Reference == https://dl.acm.org/doi/10.1109/FOCS.2004.40")
• 11:15, 15 February 2023 ‎Micali; Vazirani ( Maximum-Weight Matching) (hist | edit) ‎[276 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3} logn)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1980 == Reference == https://ieeexplore.ieee.org/document/4567800")
• 11:15, 15 February 2023 ‎Edmonds (Maximum-Weight Matching Maximum-Weight Matching) (hist | edit) ‎[418 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn^{2})$ == Space Complexity == $O(mn^{2})$?? words (At worst, keeps track of the entire sequence of graphs created; it's possible this can be improved?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1965 == Reference == https://nvlpubs.nist.gov/nistpubs/jres/69B/jresv69Bn1-2p125_A1b.pdf")
• 11:15, 15 February 2023 ‎Lipton; Mehta (2-player Nash Equilibria) (hist | edit) ‎[368 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{(O(log n)$)} (previously $O(n^{2} logn)$????) == Space Complexity == (see sheet {2}) words () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2003 == Reference == https://dl.acm.org/doi/10.1145/779928.779933")
• 11:15, 15 February 2023 ‎Hungarian algorithm (Bipartite Maximum-Weight Matching Maximum-Weight Matching) (hist | edit) ‎[464 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{4})$ == Space Complexity == $O(n^{2})$ words (Either graph interpretation maintains O(n^2) orientations and O(n) potential or matrix interpretation manipulates an O(n)*O(n) auxiliary matrix) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1955 == Reference == https://web.eecs.umich.edu/~pettie/matching/Kuhn-hungarian-assignment.pdf")
• 11:15, 15 February 2023 ‎Lemke–Howson algorithm (2-player Nash Equilibria) (hist | edit) ‎[347 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == {2}^{($O(n+m)$)} (previously $O(n^{4})$????) == Space Complexity == $O(mn)$? words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1964 == Reference == https://epubs.siam.org/doi/abs/10.1137/0112033?journalCode=smjmap.1")
• 11:15, 15 February 2023 ‎De Prisco (Approximate OBST Optimal Binary Search Trees) (hist | edit) ‎[502 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ words (Derived: Uses an auxiliary probability distribution, and three phases that alter a single tree that eventually is the result) == Description == == Approximate? == Approximate Approximation Factor: Upper bound: $H + 1 - p_0 - p_n + p_{max}$ == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1993 == Reference == https://www.sciencedirect.com/science/a...")
• 11:15, 15 February 2023 ‎Levcopoulos; Lingas; Sack (Approximate OBST Optimal Binary Search Trees) (hist | edit) ‎[402 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ words (Derived: Uses an auxiliary list of initial size $4n$) == Description == == Approximate? == Approximate Approximation Factor: $1 + \epsilon$ == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1989 == Reference == https://www.sciencedirect.com/science/article/pii/0304397589901345")
• 11:15, 15 February 2023 ‎Yao (OBST Optimal Binary Search Trees) (hist | edit) ‎[310 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (https://doi.org/10.1137/0603055) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1982 == Reference == https://doi.org/10.1137/0603055")
• 11:15, 15 February 2023 ‎Naive algorithm (OBST Optimal Binary Search Trees) (hist | edit) ‎[412 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O({4}^n /n \sqrt{n})$ == Space Complexity == $O({1})$ words (Derived: Constant space to verify optimality. Constant space if you can enumerate the trees in-situ.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == https://www.cs.bgu.ac.il/~michaluz/seminar/Knuth71.pdf")
• 11:15, 15 February 2023 ‎Knuth's DP algorithm (OBST Optimal Binary Search Trees) (hist | edit) ‎[362 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$ words (https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4492658) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1970 == Reference == https://www.cs.bgu.ac.il/~michaluz/seminar/Knuth71.pdf")
• 11:15, 15 February 2023 ‎Modified Knuth's DP algorithm (OBST Optimal Binary Search Trees) (hist | edit) ‎[362 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4492658) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1970 == Reference == https://www.cs.bgu.ac.il/~michaluz/seminar/Knuth71.pdf")
• 11:15, 15 February 2023 ‎Hu–Tucker algorithm (Alphabetic Tree Problem Optimal Binary Search Trees) (hist | edit) ‎[331 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n \log n)$ == Space Complexity == $O(n)$ words (https://epubs.siam.org/doi/10.1137/0121057) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1971 == Reference == https://epubs.siam.org/doi/10.1137/0121057")
• 11:15, 15 February 2023 ‎Garsia–Wachs algorithm (Alphabetic Tree Problem Optimal Binary Search Trees) (hist | edit) ‎[371 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n \log n)$ == Space Complexity == $O(n)$ words (https://epubs.siam.org/doi/epdf/10.1137/0206045, See implementation of MINTREE) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1977 == Reference == https://epubs.siam.org/doi/abs/10.1137/0206045")
• 11:15, 15 February 2023 ‎Heap's algorithm (All Permutations All Permutations) (hist | edit) ‎[347 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ per permutation == Space Complexity == $O(n)$ auxiliary words ($O(n)$-sized stack or array necessary) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1963 == Reference == https://academic.oup.com/comjnl/article/6/3/293/360213")

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