All public logs

Jump to navigation Jump to search

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).

Logs
(newest | oldest) View ( | ) (20 | 50 | 100 | 250 | 500)
  • 10:22, 15 February 2023 Admin talk contribs created page Exact GED (Created page with "{{DISPLAYTITLE:Exact GED (Graph Edit Distance Computation)}} == Description == The GED of two graphs is defined as the minimum cost of an edit path between them, where an edit path is a sequence of edit operations (inserting, deleting, and relabeling vertices or edges) that transforms one graph into another. Exact GED computes the GED exactly. == Related Problems == Related: Inexact GED == Parameters == <pre>V: number of vertices in the larger of the two grap...")
  • 10:22, 15 February 2023 Admin talk contribs created page Lowest Common Ancestors with Linking and Cutting (Created page with "{{DISPLAYTITLE:Lowest Common Ancestors with Linking and Cutting (Lowest Common Ancestor)}} == Description == Given a collection of rooted trees, answer queries of the form, "What is the nearest common ancestor of vertices $x$ and $y$?" In this version of the problem, the queries are on-line. Interspersed with the queries are on-line commands of two types: $link(x, y)$, where $y$ but not necessarily $x$ is a tree root, and $cut (x)$, where $x$ is not a root. The effect...")
  • 10:22, 15 February 2023 Admin talk contribs created page Lowest Common Ancestor with Linking (Created page with "{{DISPLAYTITLE:Lowest Common Ancestor with Linking (Lowest Common Ancestor)}} == Description == Given a collection of rooted trees, answer queries of the form, "What is the nearest common ancestor of vertices $x$ and $y$?" In this version of the problem, the queries are on-line. Interspersed with the queries are on-line commands $link(x, y)$ such that $y$, but not necessarily $x$, is a tree root. The effect of a command $link(x, y)$ is to combine the trees containing $...")
  • 10:22, 15 February 2023 Admin talk contribs created page Lowest Common Ancestor with Linking Roots (Created page with "{{DISPLAYTITLE:Lowest Common Ancestor with Linking Roots (Lowest Common Ancestor)}} == Description == Given a collection of rooted trees, answer queries of the form, "What is the nearest common ancestor of vertices $x$ and $y$?" In this version of the problem, The queries are given on-line. Interspersed with the queries are on-line commands of the form $link(x, y)$ where $x$ and $y$ are tree roots. The effect of a command $link(x, y)$ is to combine the trees containing...")
  • 10:22, 15 February 2023 Admin talk contribs created page Lowest Common Ancestor with Static Trees (Created page with "{{DISPLAYTITLE:Lowest Common Ancestor with Static Trees (Lowest Common Ancestor)}} == Description == Given a collection of rooted trees, answer queries of the form, "What is the nearest common ancestor of vertices $x$ and $y$?" In this version of the problem, the collection of trees is static but the queries are given on-line. That is, each query must be answered before the next one is known. == Related Problems == Generalizations: Lowest Common Ancestor Relate...")
  • 10:22, 15 February 2023 Admin talk contribs created page Off-Line Lowest Common Ancestor (Created page with "{{DISPLAYTITLE:Off-Line Lowest Common Ancestor (Lowest Common Ancestor)}} == Description == Given a collection of rooted trees, answer queries of the form, "What is the nearest common ancestor of vertices $x$ and $y$?" In this version of the problem, the collection of trees is static and the entire sequence of queries is specified in advance. == Related Problems == Generalizations: Lowest Common Ancestor Related: Lowest Common Ancestor with Static Trees, ...")
  • 10:22, 15 February 2023 Admin talk contribs created page Nearest Common Ancestor (Redirected page to Lowest Common Ancestor) Tag: New redirect
  • 10:22, 15 February 2023 Admin talk contribs created page Lowest Common Ancestor (Created page with "{{DISPLAYTITLE:Lowest Common Ancestor (Lowest Common Ancestor)}} == Description == Given a collection of rooted trees, answer queries of the form, "What is the nearest common ancestor of vertices $x$ and $y$?" == Related Problems == Subproblem: Off-Line Lowest Common Ancestor, Lowest Common Ancestor with Static Trees, Lowest Common Ancestor with Linking Roots, Lowest Common Ancestor with Linking, Lowest Common Ancestors with Linking and Cutting...")
  • 10:22, 15 February 2023 Admin talk contribs created page Cyclic Nontrivial SCCs DFA Minimization (Created page with "{{DISPLAYTITLE:Cyclic Nontrivial SCCs DFA Minimization (DFA Minimization)}} == Description == Given an finite deterministic automaton (DFA) from a class $C$ of DFAs, whose nontrivial SCCs are cyclic, determine its minimal automaton given by the equivalence relation on states. == Related Problems == Generalizations: DFA Minimization Related: Acyclic DFA Minimization == Parameters == <pre>$n$: number of states $d$: number of transitions $k$: size of alphab...")
  • 10:22, 15 February 2023 Admin talk contribs created page Acyclic DFA Minimization (Created page with "{{DISPLAYTITLE:Acyclic DFA Minimization (DFA Minimization)}} == Description == Given an acyclic finite deterministic automaton (DFA) from a class $C$ of DFAs, determine its minimal automaton given by the equivalence relation on states. == Related Problems == Generalizations: DFA Minimization Related: Cyclic Nontrivial SCCs DFA Minimization == Parameters == <pre>$n$: number of states $d$: number of transitions $k$: size of alphabet</pre> == Table of Algo...")
  • 10:22, 15 February 2023 Admin talk contribs created page Variance Calculations (Created page with "{{DISPLAYTITLE:Variance Calculations (Variance Calculations)}} == Description == Given a set of n (real/integer) numbers, compute the variance (sample or population). Of interest is streaming algorithms and numerical stability. == Parameters == <pre>n: number of values</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference |- | Naïve...")
  • 10:22, 15 February 2023 Admin talk contribs created page Voronoi Diagrams (Created page with "{{DISPLAYTITLE:Voronoi Diagrams (Voronoi Diagrams)}} == Description == Given a set of n points in 2-dimensional space, compute the Voronoi diagram with the n points as seeds. == Parameters == <pre>n: number of points</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference |- | Fortune's algorithm (Voronoi Diagrams Voronoi Diagrams)|For...")
  • 10:22, 15 February 2023 Admin talk contribs created page Global Register Allocation (Created page with "{{DISPLAYTITLE:Global Register Allocation (Register Allocation)}} == Description == Register allocation is the process of mapping the unlimited number of symbolic registers assumed in the intermediate language into the limited real machine registers. Global register allocation deals with the allocation of registers in code containing branches (http://www.cs.ucr.edu/~gupta/research/Publications/Comp/p370-gupta.pdf). == Related Problems == Related: Local Register A...")
  • 10:22, 15 February 2023 Admin talk contribs created page Local Register Allocation (Created page with "{{DISPLAYTITLE:Local Register Allocation (Register Allocation)}} == Description == Register allocation is the process of mapping the unlimited number of symbolic registers assumed in the intermediate language into the limited real machine registers. Local register allocation deals with the allocation of registers in straight-line code segments (http://www.cs.ucr.edu/~gupta/research/Publications/Comp/p370-gupta.pdf). == Related Problems == Related: Global Register...")
  • 10:22, 15 February 2023 Admin talk contribs created page Cardinality Estimation (Created page with "{{DISPLAYTITLE:Cardinality Estimation (Cardinality Estimation)}} == Description == Given a multiset of (possibly hashed) values, estimate the number of distinct elements of the multiset. Of interest is minimizing storage usage. == Parameters == <pre>N: number of values in multiset n: cardinality of multiset (not known)</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approxi...")
  • 10:21, 15 February 2023 Admin talk contribs created page Maximum Likelihood Parameters (Created page with "{{DISPLAYTITLE:Maximum Likelihood Parameters (Maximum Likelihood Parameters)}} == Description == In these algorithms, the goal is to estimate hyperparameters using maximum likelihood. == Parameters == No parameters found. == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference |- | Expectation–maximization (EM) algorithm ( Maximum Likeliho...")
  • 10:21, 15 February 2023 Admin talk contribs created page K-ANNS (Redirected page to K Approximate Nearest Neighbors Search) Tag: New redirect
  • 10:21, 15 February 2023 Admin talk contribs created page K Approximate Nearest Neighbors Search (Created page with "{{DISPLAYTITLE:k Approximate Nearest Neighbors Search (Nearest Neighbor Search)}} == Description == Within a dataset of $n$ points, find approximately the $k$ closest points to a specified point. == Related Problems == Generalizations: k Nearest Neighbors Search == Parameters == <pre>n: number of points in dataset k: number of neighbors to find</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem.")
  • 10:21, 15 February 2023 Admin talk contribs created page K-NNS (Redirected page to K Nearest Neighbors Search) Tag: New redirect
  • 10:21, 15 February 2023 Admin talk contribs created page K Nearest Neighbors Search (Created page with "{{DISPLAYTITLE:k Nearest Neighbors Search (Nearest Neighbor Search)}} == Description == Within a dataset of $n$ points, find the $k$ closest points to a specified point. == Related Problems == Subproblem: k Approximate Nearest Neighbors Search == Parameters == <pre>n: number of points in dataset k: number of neighbors to find</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem.")
  • 10:21, 15 February 2023 Admin talk contribs created page Root Computation (Created page with "{{DISPLAYTITLE:Root Computation (Root Computation)}} == Description == Given a real continuous function, compute one of the roots. == Parameters == No parameters found. == Table of Algorithms == Currently no algorithms in our database for the given problem.")
  • 10:21, 15 February 2023 Admin talk contribs created page Eigenpair closest to mu (Created page with "{{DISPLAYTITLE:Eigenpair closest to mu (Eigenvalues (Iterative Methods))}} == Description == Given an $n \times n$ matrix $A$, find the eigenpair (eigenvalue and associated eigenvector) of $A$ with the eigenvalue closest to $\mu$. == Related Problems == Generalizations: Any Eigenpair Related: All Eigenvalues, Any Eigenvalue, All Eigenpairs, Eigenpair with the Largest Eigenvalue == Parameters == No parameters found. == Table of Algorithms ==...")
  • 10:21, 15 February 2023 Admin talk contribs created page Eigenpair with the Largest Eigenvalue (Created page with "{{DISPLAYTITLE:Eigenpair with the Largest Eigenvalue (Eigenvalues (Iterative Methods))}} == Description == Given an $n \times n$ matrix $A$, find the eigenpair (eigenvalue and associated eigenvector) of $A$ with the largest eigenvalue. == Related Problems == Generalizations: Any Eigenpair Related: All Eigenvalues, Any Eigenvalue, All Eigenpairs, Eigenpair closest to mu == Parameters == No parameters found. == Table of Algorithms == {| clas...")
  • 10:21, 15 February 2023 Admin talk contribs created page Any Eigenpair (Created page with "{{DISPLAYTITLE:Any Eigenpair (Eigenvalues (Iterative Methods))}} == Description == Given an $n \times n$ matrix $A$, find any eigenpair (eigenvalue and associated eigenvector) of $A$. == Related Problems == Subproblem: Any Eigenvalue, All Eigenpairs, Eigenpair with the Largest Eigenvalue, Eigenpair closest to mu Related: All Eigenvalues, All Eigenpairs, Eigenpair with the Largest Eigenvalue, Eigenpair closest to mu == Parameters...")
  • 10:21, 15 February 2023 Admin talk contribs created page All Eigenpairs (Created page with "{{DISPLAYTITLE:All Eigenpairs (Eigenvalues (Iterative Methods))}} == Description == Given an $n \times n$ matrix $A$, find all eigenpairs (eigenvalues and associated eigenvectors) of $A$. == Related Problems == Generalizations: Any Eigenpair Related: All Eigenvalues, Any Eigenvalue, Eigenpair with the Largest Eigenvalue, Eigenpair closest to mu == Parameters == No parameters found. == Table of Algorithms == Currently no algorithms in our d...")
  • 10:21, 15 February 2023 Admin talk contribs created page Any Eigenvalue (Created page with "{{DISPLAYTITLE:Any Eigenvalue (Eigenvalues (Iterative Methods))}} == Description == Given an $n \times n$ matrix $A$, find any eigenvalue of $A$. == Related Problems == Generalizations: Any Eigenpair Subproblem: All Eigenvalues Related: All Eigenpairs, Eigenpair with the Largest Eigenvalue, Eigenpair closest to mu == Parameters == No parameters found. == Table of Algorithms == Currently no algorithms in our database for the given problem.")
  • 10:21, 15 February 2023 Admin talk contribs created page All Eigenvalues (Created page with "{{DISPLAYTITLE:All Eigenvalues (Eigenvalues (Iterative Methods))}} == Description == Given an $n \times n$ matrix $A$, find all eigenvalues of $A$. == Related Problems == Generalizations: Any Eigenvalue Related: All Eigenpairs, Any Eigenpair, Eigenpair with the Largest Eigenvalue, Eigenpair closest to mu == Parameters == No parameters found. == Table of Algorithms == Currently no algorithms in our database for the given problem.")
  • 10:21, 15 February 2023 Admin talk contribs created page Line Simplification (Created page with "{{DISPLAYTITLE:Line Simplification (Line Simplification)}} == Description == Line simplification is the process of taking a line/curve as represented by a list of points and reducing the number of points needed to accurately represent the given line. == Parameters == No parameters found. == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference |...")
  • 10:21, 15 February 2023 Admin talk contribs created page (3-Dimensional, i.e. project onto a 2D plane) (Created page with "{{DISPLAYTITLE:(3-Dimensional, i.e. project onto a 2D plane) (Shown Surface Determination)}} == Description == This is the process of identifying what surfaces and parts of surfaces can be seen from a particular viewing angle. Given a set of obstacles in the Euclidean space, two points in the space are said to be visible to each other, if the line segment that joins them does not intersect any obstacles. == Parameters == <pre>n: number of polygons p: number of pixel...")
  • 10:21, 15 February 2023 Admin talk contribs created page Polygon Clipping with Convex Clipping Polygon (Created page with "{{DISPLAYTITLE:Polygon Clipping with Convex Clipping Polygon (Polygon Clipping)}} == Description == Here, the clipping polygon is restricted to being convex. == Related Problems == Generalizations: Polygon Clipping with Arbitrary Clipping Polygon == Parameters == No parameters found. == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference...")
  • 10:21, 15 February 2023 Admin talk contribs created page Polygon Clipping with Arbitrary Clipping Polygon (Created page with "{{DISPLAYTITLE:Polygon Clipping with Arbitrary Clipping Polygon (Polygon Clipping)}} == Description == Clipping is an essential part of image synthesis. Traditionally, polygon clipping has been used to clip out the portions of a polygon that lie outside the window of the output device to prevent undesirable effects. In the recent past polygon clipping is used to render 3D images through hidden surface removal and to produce high-quality surface details using techniques...")
  • 10:21, 15 February 2023 Admin talk contribs created page Line Drawing (Created page with "{{DISPLAYTITLE:Line Drawing (Line Drawing)}} == Description == Given a line segment with endpoints $(x_0, y_0), (x_1, y_1)$ and a discrete graphical medium (like pixel-based displays and printers), draw/approximate the line segment on the medium, potentially with antialiasing. == Parameters == <pre>n: number of pixels the line goes through</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Tim...")
  • 10:21, 15 February 2023 Admin talk contribs created page Constructing Eulerian Trails in a Graph (Created page with "{{DISPLAYTITLE:Constructing Eulerian Trails in a Graph (Constructing Eulerian Trails in a Graph)}} == Description == In graph theory, an Eulerian trail (or Eulerian path) is a trail in a finite graph that visits every edge exactly once (allowing for revisiting vertices). Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail that starts and ends on the same vertex. == Parameters == No parameters found. == Table of Algorithms == {| class="wikitable...")
  • 10:21, 15 February 2023 Admin talk contribs created page Bipartite Maximum-Weight Matching (Created page with "{{DISPLAYTITLE:Bipartite Maximum-Weight Matching (Maximum-Weight Matching)}} == Description == In computer science, the maximum weight matching problem is the problem of finding, in a weighted graph, a matching in which the sum of weights is maximized. Here, the graph must be bipartite. == Related Problems == Generalizations: Maximum-Weight Matching == Parameters == <pre>n: number of vertices m: number of edges N: largest weight magnitude</pre> == Table of A...")
  • 10:21, 15 February 2023 Admin talk contribs created page Maximum-Weight Matching (Created page with "{{DISPLAYTITLE:Maximum-Weight Matching (Maximum-Weight Matching)}} == Description == In computer science, the maximum weight matching problem is the problem of finding, in a weighted graph, a matching in which the sum of weights is maximized. Here, the graph is unrestricted; i.e. can be any general graph. == Related Problems == Subproblem: Bipartite Maximum-Weight Matching == Parameters == <pre>n: number of vertices m: number of edges N: largest weight magnit...")
  • 10:21, 15 February 2023 Admin talk contribs created page N-Player (Created page with "{{DISPLAYTITLE:n-Player (Nash Equilibria)}} == Description == Here, given the payoff matrices for an $n$-player game, determine a Nash equilibrium. == Related Problems == Subproblem: 2-Player == Parameters == <pre>n: number of players</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem.")
  • 10:21, 15 February 2023 Admin talk contribs created page 2-Player (Created page with "{{DISPLAYTITLE:2-Player (Nash Equilibria)}} == Description == In game theory, the Nash equilibrium, named after the mathematician John Forbes Nash Jr., is a proposed solution of a non-cooperative game involving two or more players in which each player is assumed to know the equilibrium strategies of the other players, and no player has anything to gain by changing only his own strategy. As an algorithmic problem, given the payoff matrices for a bimatrix game, determine...")
  • 10:21, 15 February 2023 Admin talk contribs created page Alphabetic Tree Problem (Created page with "{{DISPLAYTITLE:Alphabetic Tree Problem (Optimal Binary Search Trees)}} == Description == A variant of the OBST problem is when only the gaps have nonzero access probabilities, and is called the optimal alphabetic tree problem. == Related Problems == Generalizations: Optimal Binary Search Tree Problem Related: Approximate OBST, Huffman Encoding == Parameters == <pre>n: number of elements</pre> == Table of Algorithms == {| class="wikitable sortable"...")
  • 10:21, 15 February 2023 Admin talk contribs created page Huffman Tree Problem (Redirected page to Huffman Encoding) Tag: New redirect
  • 10:21, 15 February 2023 Admin talk contribs created page Approximate OBST (Created page with "{{DISPLAYTITLE:Approximate OBST (Optimal Binary Search Trees)}} == Description == Suppose we are given $n$ keys and the probabilities of accessing each key and those occurring in the gap between two successive keys. The approximate optimal binary search tree problem is to construct a binary search tree on these $n$ keys, whose expected access time is within an approximation factor of the optimal time. == Related Problems == Generalizations: Optimal Binary Search T...")
  • 10:21, 15 February 2023 Admin talk contribs created page OBST (Redirected page to Optimal Binary Search Tree Problem) Tag: New redirect
  • 10:21, 15 February 2023 Admin talk contribs created page Optimal Binary Search Tree Problem (Created page with "{{DISPLAYTITLE:Optimal Binary Search Tree Problem (Optimal Binary Search Trees)}} == Description == Suppose we are given $n$ keys and the probabilities of accessing each key and those occurring in the gap between two successive keys. The optimal binary search tree problem is to construct a binary search tree on these $n$ keys that minimizes the expected access time. == Related Problems == Subproblem: Approximate OBST, Huffman Encoding, Alphabetic Tree Pr...")
  • 10:21, 15 February 2023 Admin talk contribs created page All Permutations (Created page with "{{DISPLAYTITLE:All Permutations (All Permutations)}} == Description == Generate all permuttaions of the characters/elements in a string/array. == Parameters == <pre>n: number of elements</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference |- | Steinhaus–Johnson–Trotter algorithm (All Permutations All Permutations)|Steinhaus–J...")
  • 10:21, 15 February 2023 Admin talk contribs created page Minimum value in each row of an implicitly-defined totally monotone matrix (Created page with "{{DISPLAYTITLE:Minimum value in each row of an implicitly-defined totally monotone matrix (Minimum value in each row of an implicitly-defined totally monotone matrix)}} == Description == Given a totally monotone matrix $A$ whose entries $A(i, j)$ are implicitly defined by some function $f(i, j)$ (assume $f$ takes constant time to evaluate for all relevant $(i, j)$), determine the minimum value in each row. == Parameters == <pre>n, m: dimensions of matrix; assume m...")
  • 10:21, 15 February 2023 Admin talk contribs created page Gröbner Bases (Created page with "{{DISPLAYTITLE:Gröbner Bases (Gröbner Bases)}} == Description == In mathematics, and more specifically in computer algebra, computational algebraic geometry, and computational commutative algebra, a Gröbner basis is a particular kind of generating set of an ideal in a polynomial ring $K(x_1, \ldots ,x_n)$ over a field $K$. As an algorithmic problem, given a set of polynomials in $K(x_1, \ldots,x_n)$, determine a Gröbner basis. == Parameters == <pre>n: number of...")
  • 10:21, 15 February 2023 Admin talk contribs created page Convex Optimization (Non-linear) (Created page with "{{DISPLAYTITLE:Convex Optimization (Non-linear) (Convex Optimization (Non-linear))}} == Description == Convex optimization is a subfield of mathematical optimization that studies the problem of minimizing convex functions over convex sets. == Parameters == No parameters found. == Table of Algorithms == Currently no algorithms in our database for the given problem. == Time Complexity graph == 1000px == Space...")
  • 10:21, 15 February 2023 Admin talk contribs created page Cyclic Permutations (Created page with "{{DISPLAYTITLE:Cyclic Permutations (Generating Random Permutations)}} == Description == Given an input string/array, generate a single random cyclic permutation of the characters/elements of the string/array. == Related Problems == Related: General Permutations == Parameters == <pre>n: number of elements</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approximation...")
  • 10:21, 15 February 2023 Admin talk contribs created page General Permutations (Created page with "{{DISPLAYTITLE:General Permutations (Generating Random Permutations)}} == Description == Given an input string/array, generate a single random permutation of the characters/elements of the string/array. == Related Problems == Related: Cyclic Permutations == Parameters == <pre>n: number of elements</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approximation Factor...")
  • 10:21, 15 February 2023 Admin talk contribs created page Loop Detection (Redirected page to Cycle Detection) Tag: New redirect
  • 10:21, 15 February 2023 Admin talk contribs created page Cycle Finding (Redirected page to Cycle Detection) Tag: New redirect
(newest | oldest) View ( | ) (20 | 50 | 100 | 250 | 500)
Retrieved from "https://algorithm-wiki.csail.mit.edu/wiki/Special:Log/Admin"