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)

• 08:29, 10 April 2023 Admin talk contribs created page Sedgewick; Szymanski; and Yao (Cycle Detection 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")
• 08:29, 10 April 2023 Admin talk contribs created page Eppstein (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")
• 08:29, 10 April 2023 Admin talk contribs created page Compression/Clustering (Vector Quantization) (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 ==")
• 08:29, 10 April 2023 Admin talk contribs created page Projected radial 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")
• 08:29, 10 April 2023 Admin talk contribs created page Locality-sensitive hashing (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")
• 08:29, 10 April 2023 Admin talk contribs created page Hierarchical Navigable Small World (HNSW) (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")
• 07:57, 10 April 2023 Admin talk contribs created page Work-conserving schedulers (Unweighted Interval Scheduling, Online Interval Scheduling) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
• 07:57, 10 April 2023 Admin talk contribs created page Multilevel queue scheduling (Unweighted Interval Scheduling, Online Interval Scheduling) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n+k)$? words (^see above; also level information for each task) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
• 07:57, 10 April 2023 Admin talk contribs created page Round-robin scheduling (Unweighted Interval Scheduling, Online Interval Scheduling) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n+k)$? words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
• 07:57, 10 April 2023 Admin talk contribs created page First come, first served (Unweighted Interval Scheduling, Online Interval Scheduling) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n+k)$? words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
• 07:57, 10 April 2023 Admin talk contribs created page Shortest remaining time first (Unweighted Interval Scheduling, Online Interval Scheduling) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n+k)$? words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
• 07:57, 10 April 2023 Admin talk contribs created page Priority scheduling (Unweighted Interval Scheduling, Online Interval Scheduling) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n+k)$? words (Keep track of (sorted, based on criteria) list of (unscheduled, running, etc.; just un-done) tasks, along with machine statuses) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
• 07:57, 10 April 2023 Admin talk contribs created page Fixed priority shortest job first (Unweighted Interval Scheduling, Online Interval Scheduling) (Created page with "== Time Complexity == $O(n \log n)$ == Space Complexity == $O(n+k)$? words (Keep track of (sorted, based on criteria) list of (unscheduled, running, etc.; just un-done) tasks, along with machine statuses and task priorities) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
• 07:57, 10 April 2023 Admin talk contribs created page BOYS algorithm (Entity Resolution Entity Resolution) (Created page with "== Time Complexity == $O(n^{2} k)$ == Space Complexity == $O(n^{2})$ words (Derived: As written stores counts/probabailities for all pairs of entries.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1993 == Reference == https://www.sciencedirect.com/science/article/abs/pii/016794739390116B")
• 07:56, 10 April 2023 Admin talk contribs created page Gremban; Miller; Zagha (Inexact Laplacian Solver SDD Systems Solvers) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (https://www.cs.cmu.edu/~glmiller/Publications/Papers/GrMiZa94-tr.pdf) == Description == Support Tree Conjugate Gradients (STCG) == Approximate? == Approximate Approximation Factor: ? == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1995 == Reference == https://www.cs.cmu.edu/~glmiller/Publications/Papers/GrMiZa94-tr.pdf")
• 07:55, 10 April 2023 Admin talk contribs created page David (Square Matrix LU Decomposition LU Decomposition) (Created page with "== Time Complexity == $O(n \log n)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference ==")
• 07:55, 10 April 2023 Admin talk contribs created page Closed formula (Square Matrix LU Decomposition LU Decomposition) (Created page with "== Time Complexity == $O(n \log n)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1975 == Reference ==")
• 07:54, 10 April 2023 Admin talk contribs created page Hirschberg's algorithm (Edit sequence Sequence Alignment) (Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(n)$ words (https://dl.acm.org/doi/10.1145/360825.360861) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1975 == Reference == https://dl.acm.org/doi/10.1145/360825.360861")
• 07:54, 10 April 2023 Admin talk contribs created page Masek; Patterson (Edit distance Sequence Alignment) (Created page with "== Time Complexity == $O(mn / log(n))$ == Space Complexity == $O(n)$ words (https://www.sciencedirect.com/science/article/pii/0022000080900021) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1980 == Reference == https://www.sciencedirect.com/science/article/pii/0022000080900021")
• 07:53, 10 April 2023 Admin talk contribs created page No-Steal, Force (Created page with "{{DISPLAYTITLE:No-Steal, Force (Recovery)}} == Description == Recovery is the process of reverting back to a safe state prior to a system failure. With a No-Steal/Force policy, the recovery algorithm will never write uncommited data to memory, but will force all commits to memory. == Related Problems == Related: Steal, No-Force == Parameters == $n$: number of transactions before crash == Table of Algorithms == Currently no algorithms in our database for t...")
• 07:53, 10 April 2023 Admin talk contribs created page Steal, No-Force (Created page with "{{DISPLAYTITLE:Steal, No-Force (Recovery)}} == Description == Recovery is the process of reverting back to a safe state prior to a system failure. With a Steal/No-Force policy, the recovery algorithm will write possibly uncommited data to memory, while not forcing all commits to memory. == Related Problems == Related: No-Steal, Force == Parameters == $n$: number of transactions before crash == Table of Algorithms == {| class="wikitable sortable" style="t...")
• 07:53, 10 April 2023 Admin talk contribs created page Unweighted Interval Scheduling, Online (Created page with "{{DISPLAYTITLE:Unweighted Interval Scheduling, Online (Interval Scheduling)}} == Description == Given are $n$ intervals of the form $(s_j , f_j)$ with $s_j < f_j$, for $j = 1, \ldots , n$. These intervals are the jobs that require uninterrupted processing during that interval. We will assume (without loss of generality) that the $s_j$’s and the $f_j$’s are nonnegative integers. We say that two intervals (or jobs) overlap if their intersection is nonempty, otherwise...")
• 07:52, 10 April 2023 Admin talk contribs created page Root Computation with continuous first derivative (Created page with "{{DISPLAYTITLE:Root Computation with continuous first derivative (Root Computation)}} == Description == Given a real function with continuous first derivative, compute one of the roots. == Related Problems == Related: General Root Computation == Parameters == $\epsilon$: (additive) tolerance error $a, b$: endpoint values, with $b>a$ $n_{max}$: maximum number of iterations == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;"...")
• 07:52, 10 April 2023 Admin talk contribs created page General Root Computation (Created page with "{{DISPLAYTITLE:General Root Computation (Root Computation)}} == Description == Given a real continuous function, compute one of the roots. == Related Problems == Related: Root Computation with continuous first derivative == Parameters == $\epsilon$: (additive) tolerance error $a, b$: endpoint values, with $b>a$ $n_{max}$: maximum number of iterations == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name...")
• 14:52, 15 February 2023 Admin talk contribs created page Reduction from OV to Disjunctive Reachability Queries in MDPs (Created page with "FROM: OV TO: Disjunctive Reachability Queries in MDPs == Description == == Implications == assume: Strong Triangle<br/>then: there is no $O(m^{2-\epsilon})$ or $O((k \cdot m)^{1-\epsilon})$ algorithm, for any $\epsilon > {0}$ for target. == Year == 2016 == Reference == Chatterjee, Krishnendu, et al. "Model and objective separation with conditional lower bounds: Disjunction is harder than conjunction." Proceedings of the 31st Annual ACM/IEEE Symposium...")
• 11:28, 15 February 2023 Admin talk contribs created page File:AST to Code Translation - Arithmetic Expression Binary Tree - Time.png
• 11:28, 15 February 2023 Admin talk contribs uploaded File:AST to Code Translation - Arithmetic Expression Binary Tree - Time.png
• 11:28, 15 February 2023 Admin talk contribs created page File:Linear System - Toeplitz Matrix - Space.png
• 11:28, 15 February 2023 Admin talk contribs created page File:Clock Synchronization in Distributed Systems - Space.png
• 11:28, 15 February 2023 Admin talk contribs uploaded File:Linear System - Toeplitz Matrix - Space.png
• 11:28, 15 February 2023 Admin talk contribs uploaded File:Clock Synchronization in Distributed Systems - Space.png
• 11:28, 15 February 2023 Admin talk contribs created page File:Line segment intersection - Reporting all intersection points, convex polygons - Pareto Frontier.png
• 11:28, 15 February 2023 Admin talk contribs uploaded File:Line segment intersection - Reporting all intersection points, convex polygons - Pareto Frontier.png
• 11:28, 15 February 2023 Admin talk contribs created page File:Maximum Likelihood Parameters - Time.png
• 11:28, 15 February 2023 Admin talk contribs created page File:Maximum Subarray Problem - Space.png
• 11:28, 15 February 2023 Admin talk contribs created page File:LU Decomposition - Space.png
• 11:28, 15 February 2023 Admin talk contribs created page File:Maximum Likelihood Methods in Unknown Latent Variables - Pareto Frontier.png
• 11:28, 15 February 2023 Admin talk contribs created page File:Graph Coloring - 3-Graph Coloring - Space.png
• 11:28, 15 February 2023 Admin talk contribs uploaded File:LU Decomposition - Space.png
• 11:28, 15 February 2023 Admin talk contribs uploaded File:Maximum Subarray Problem - Space.png
• 11:28, 15 February 2023 Admin talk contribs uploaded File:Maximum Likelihood Parameters - Time.png
• 11:28, 15 February 2023 Admin talk contribs uploaded File:Graph Coloring - 3-Graph Coloring - Space.png
• 11:28, 15 February 2023 Admin talk contribs uploaded File:Maximum Likelihood Methods in Unknown Latent Variables - Pareto Frontier.png
• 11:28, 15 February 2023 Admin talk contribs created page File:Clique Problems - Enumerating Maximal Cliques, arbitrary graph - Time.png
• 11:28, 15 February 2023 Admin talk contribs uploaded File:Clique Problems - Enumerating Maximal Cliques, arbitrary graph - Time.png
• 11:28, 15 February 2023 Admin talk contribs created page File:Maximum Flow - Integer Maximum Flow - Time.png
• 11:28, 15 February 2023 Admin talk contribs created page File:The Set-Covering Problem - Time.png
• 11:28, 15 February 2023 Admin talk contribs uploaded File:Maximum Flow - Integer Maximum Flow - Time.png
• 11:28, 15 February 2023 Admin talk contribs created page File:Line Clipping - Time.png
• 11:28, 15 February 2023 Admin talk contribs uploaded File:The Set-Covering Problem - Time.png

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