User contributions for Admin

15 February 2023

• 11:2111:21, 15 February 2023 diff hist +505‎ N 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..."
• 11:2111:21, 15 February 2023 diff hist +475‎ N 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."
• 11:2111:21, 15 February 2023 diff hist +464‎ N 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."
• 11:2111:21, 15 February 2023 diff hist +1,548‎ N 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 |..."
• 11:2111:21, 15 February 2023 diff hist +2,119‎ N (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..."
• 11:2111:21, 15 February 2023 diff hist +1,123‎ N 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..."
• 11:2111:21, 15 February 2023 diff hist +2,203‎ N 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..."
• 11:2111:21, 15 February 2023 diff hist +1,822‎ N 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..."
• 11:2111:21, 15 February 2023 diff hist +2,709‎ Discrete Fourier Transform ‎No edit summary
• 11:2111:21, 15 February 2023 diff hist +1,729‎ N 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..."
• 11:2111:21, 15 February 2023 diff hist +1,632‎ N 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..."
• 11:2111:21, 15 February 2023 diff hist +1,512‎ N 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..."
• 11:2111:21, 15 February 2023 diff hist +344‎ N 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."
• 11:2111:21, 15 February 2023 diff hist +733‎ N 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..."
• 11:2111:21, 15 February 2023 diff hist +1,699‎ N 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"..."
• 11:2111:21, 15 February 2023 diff hist +30‎ N Huffman Tree Problem ‎ Redirected page to Huffman Encoding current Tag: New redirect
• 11:2111:21, 15 February 2023 diff hist −323‎ Huffman Encoding ‎No edit summary
• 11:2111:21, 15 February 2023 diff hist +2,095‎ N 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..."
• 11:2111:21, 15 February 2023 diff hist +48‎ N OBST ‎ Redirected page to Optimal Binary Search Tree Problem current Tag: New redirect
• 11:2111:21, 15 February 2023 diff hist +687‎ N 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..."
• 11:2111:21, 15 February 2023 diff hist +1,408‎ N 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..."
• 11:2111:21, 15 February 2023 diff hist +1,883‎ N 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..."
• 11:2111:21, 15 February 2023 diff hist +1,814‎ N 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..."
• 11:2111:21, 15 February 2023 diff hist +659‎ N 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..."
• 11:2111:21, 15 February 2023 diff hist +1,092‎ N 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..."
• 11:2111:21, 15 February 2023 diff hist +1,539‎ N 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..."
• 11:2111:21, 15 February 2023 diff hist +29‎ N Loop Detection ‎ Redirected page to Cycle Detection current Tag: New redirect
• 11:2111:21, 15 February 2023 diff hist +29‎ N Cycle Finding ‎ Redirected page to Cycle Detection current Tag: New redirect
• 11:2011:20, 15 February 2023 diff hist +1,456‎ Cycle Detection ‎No edit summary
• 11:2011:20, 15 February 2023 diff hist +3,859‎ N Inexact Laplacian Solver ‎ Created page with "{{DISPLAYTITLE:Inexact Laplacian Solver (SDD Systems Solvers)}} == Description == This problem refers to solving equations of the form $Lx = b$ where $L$ is a Laplacian of a graph. In other words, this is solving equations of the form $Ax = b$ for a SDD matrix $A$. This variation of the problem permits some error. == Related Problems == Related: Exact Laplacian Solver == Parameters == No parameters found. == Table of Algorithms == {| class="wikitable sort..."
• 11:2011:20, 15 February 2023 diff hist +36‎ N Symmetric Diagonally Dominant System Solvers ‎ Redirected page to Exact Laplacian Solver current Tag: New redirect
• 11:2011:20, 15 February 2023 diff hist +1,517‎ N Exact Laplacian Solver ‎ Created page with "{{DISPLAYTITLE:Exact Laplacian Solver (SDD Systems Solvers)}} == Description == This problem refers to solving equations of the form $Lx = b$ where $L$ is a Laplacian of a graph. In other words, this is solving equations of the form $Ax = b$ for a SDD matrix $A$. This variation of the problem requires an exact solution with no error. == Related Problems == Related: Inexact Laplacian Solver == Parameters == <pre>n: dimension of matrix</pre> == Table of Algor..."
• 11:2011:20, 15 February 2023 diff hist +1,631‎ Mutual Exclusion ‎No edit summary
• 11:2011:20, 15 February 2023 diff hist +1,331‎ N Key Exchange ‎ Created page with "{{DISPLAYTITLE:Key Exchange (Key Exchange)}} == Description == Key exchange (also key establishment) is a method in cryptography by which cryptographic keys are exchanged between two parties, allowing use of a cryptographic algorithm. == Parameters == <pre>n: maximum size of numbers (prime, parameters, keys), in bits</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approxima..."
• 11:2011:20, 15 February 2023 diff hist +1,608‎ N Planar Bipartite Graph Perfect Matching ‎ Created page with "{{DISPLAYTITLE:Planar Bipartite Graph Perfect Matching (Maximum Cardinality Matching)}} == Description == The goal of maximum cardinality matching is to find a matching with as many edges as possible (equivalently: a matching that covers as many vertices as possible). Here, the graph is a planar bipartite graph. == Related Problems == Generalizations: Bipartite Graph MCM Related: General Graph MCM == Parameters == <pre>V: number of vertices E: number of..."
• 11:2011:20, 15 February 2023 diff hist +1,988‎ N General Graph MCM ‎ Created page with "{{DISPLAYTITLE:General Graph MCM (Maximum Cardinality Matching)}} == Description == The goal of maximum cardinality matching is to find a matching with as many edges as possible (equivalently: a matching that covers as many vertices as possible). Here, the graph can be any general graph. == Related Problems == Subproblem: Bipartite Graph MCM Related: Planar Bipartite Graph Perfect Matching == Parameters == <pre>V: number of vertices E: number of edges</p..."
• 11:2011:20, 15 February 2023 diff hist +3,168‎ N Bipartite Graph MCM ‎ Created page with "{{DISPLAYTITLE:Bipartite Graph MCM (Maximum Cardinality Matching)}} == Description == The goal of maximum cardinality matching is to find a matching with as many edges as possible (equivalently: a matching that covers as many vertices as possible). Here, the graph is bipartite. == Related Problems == Generalizations: General Graph MCM Subproblem: Planar Bipartite Graph Perfect Matching == Parameters == <pre>V: number of vertices E: number of edges</pre>..."
• 11:2011:20, 15 February 2023 diff hist +1,499‎ Multiplication ‎No edit summary
• 11:2011:20, 15 February 2023 diff hist −177‎ NFA to DFA conversion ‎No edit summary
• 11:2011:20, 15 February 2023 diff hist +675‎ N Convex Polyhedral Window ‎ Created page with "{{DISPLAYTITLE:Convex Polyhedral Window (Line Clipping)}} == Description == Line clipping is the process of removing lines or portions of lines outside an area of interest. Typically; any line or part thereof which is outside of the viewing area is removed. Here, the viewing area is a convex polyhedron. == Related Problems == Subproblem: Convex Polygonal Window Related: Rectangular Window == Parameters == <pre>n: number of lines p: number of faces on pol..."
• 11:2011:20, 15 February 2023 diff hist +1,062‎ N Convex Polygonal Window ‎ Created page with "{{DISPLAYTITLE:Convex Polygonal Window (Line Clipping)}} == Description == Line clipping is the process of removing lines or portions of lines outside an area of interest. Typically; any line or part thereof which is outside of the viewing area is removed. Here, the viewing area is a convex polygon. == Related Problems == Generalizations: Convex Polyhedral Window Subproblem: Rectangular Window == Parameters == <pre>n: number of lines p: number of edges o..."
• 11:2011:20, 15 February 2023 diff hist +1,882‎ N Rectangular Window ‎ Created page with "{{DISPLAYTITLE:Rectangular Window (Line Clipping)}} == Description == Line clipping is the process of removing lines or portions of lines outside an area of interest. Typically; any line or part thereof which is outside of the viewing area is removed. Here, the viewing area is rectangular. == Related Problems == Generalizations: Convex Polygonal Window Related: Convex Polyhedral Window == Parameters == <pre>n: number of lines</pre> == Table of Algorithm..."
• 11:2011:20, 15 February 2023 diff hist +274‎ Joins ‎No edit summary
• 11:2011:20, 15 February 2023 diff hist +1,539‎ N Edit Sequence, constant-size alphabet ‎ Created page with "{{DISPLAYTITLE:Edit Sequence, constant-size alphabet (Sequence Alignment)}} == Description == Given two strings, determine the shortest sequence of edits required to transform one of the strings into the other. Assume we have a constant-size alphabet. == Related Problems == Generalizations: Edit Distance, constant-size alphabet == Parameters == <pre>n, m: lengths of input strings; assume n≥m</pre> == Table of Algorithms == {| class="wikitable sortable"..."
• 11:2011:20, 15 February 2023 diff hist +605‎ N Edit Distance, constant-size alphabet ‎ Created page with "{{DISPLAYTITLE:Edit Distance, constant-size alphabet (Sequence Alignment)}} == Description == Given two strings, determine the minimum number of edits required to transform one of the strings into the other. Assume we have a constant-size alphabet. == Related Problems == Subproblem: Edit Sequence, constant-size alphabet == Parameters == <pre>n, m: lengths of input strings; assume n≥m</pre> == Table of Algorithms == Currently no algorithms in our database..."
• 11:2011:20, 15 February 2023 diff hist +1,736‎ N Multiple String Search ‎ Created page with "{{DISPLAYTITLE:Multiple String Search (String Search)}} == Description == Multiple string search algorithms try to find a place where one or several strings (also called patterns) are found within a larger string or text. == Related Problems == Related: Single String Search == Parameters == <pre>$m$: longest pattern length $n$: length of searchable text $s$: size of the alphabet $k$: number of patterns to search for $z$: number of matches</pre> == Table of A..."
• 11:2011:20, 15 February 2023 diff hist +4,917‎ N Single String Search ‎ Created page with "{{DISPLAYTITLE:Single String Search (String Search)}} == Description == Single string search algorithms try to find a place where a string (also called a pattern) is found within a larger string or text. == Related Problems == Related: Multiple String Search == Parameters == <pre>$m$: pattern length $n$: length of searchable text $s$: size of the alphabet</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%"..."
• 11:2011:20, 15 February 2023 diff hist +4,278‎ Informed Search ‎No edit summary
• 11:2011:20, 15 February 2023 diff hist +2,396‎ N Square Matrix LU Decomposition ‎ Created page with "{{DISPLAYTITLE:Square Matrix LU Decomposition (LU Decomposition)}} == Description == Lower–upper (LU) decomposition or factorization factors a matrix as the product of a lower triangular matrix and an upper triangular matrix. In this specific case, the input is a square $n \times n$ matrix == Related Problems == Generalizations: Rectangular Matrix LU Decomposition == Parameters == <pre>$n$: dimension of square matrix</pre> == Table of Algorithms == {| cl..."
• 11:2011:20, 15 February 2023 diff hist +1,289‎ N Rectangular Matrix LU Decomposition ‎ Created page with "{{DISPLAYTITLE:Rectangular Matrix LU Decomposition (LU Decomposition)}} == Description == Lower–upper (LU) decomposition or factorization factors a matrix as the product of a lower triangular matrix and an upper triangular matrix. In the general case, the input is an $m \times n$ matrix. == Related Problems == Subproblem: Square Matrix LU Decomposition == Parameters == <pre>$m$: number of rows in input matrix $n$: number of columns in input matrix $l$: numb..."