New pages
Jump to navigation
Jump to search
(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)
- 10:26, 15 February 2023 Chromatic Number (hist | edit) [709 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Chromatic Number (Graph Coloring)}} == Description == In this case, we wish to compute the chromatic number of a graph; that is, the smallest number of colors needed to color the graph. == Related Problems == Related: k-Graph Coloring, 2-Graph Coloring, 3-Graph Coloring, 4-Graph Coloring, 5-Graph Coloring, #k-Graph Coloring, #2-Graph Coloring, #3-Graph Coloring, #4-Graph Coloring, #5-Graph Coloring == Parameter...")
- 10:26, 15 February 2023 K-Graph Coloring (hist | edit) [962 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:k-Graph Coloring (Graph Coloring)}} == Description == Graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In this case, the number of colors we have is given as an input. == Related Problems == Subproblem: 2-Graph Coloring, 3-Graph Coloring, 4-Graph Coloring, 5-Graph Coloring, #k-Graph Coloring Related: Chromati...")
- 10:26, 15 February 2023 Link Analysis (hist | edit) [3,244 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Link Analysis (Link Analysis)}} == Description == Unlike "flat" document collections, the World Wide Web is hypertext and provides considerable auxiliary information on top of the text of the web pages, such as link structure and link text. With link analysis, we take advantage of the link structure of the Web to produce a global "importance" ranking of every web page that helps search engines and users quickly make sense of the vast heterogeneity of the...")
- 10:26, 15 February 2023 No-Steal/Force (hist | edit) [470 bytes] Admin (talk | contribs) (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 == No parameters found. == Table of Algorithms == Currently no algorithms in our database for the given problem.")
- 10:26, 15 February 2023 Steal/No-Force (hist | edit) [554 bytes] Admin (talk | contribs) (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 == No parameters found. == Table of Algorithms == Currently no algorithms in our database for the given problem...")
- 10:26, 15 February 2023 Online (hist | edit) [2,107 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Online (Page Replacements)}} == Description == When page fault occurs during the program execution, operating systems use page replacement algorithms to select a victim page from primary memory and makes room for the required page. == Related Problems == Related: Offline == Parameters == No parameters found. == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Ap...")
- 10:26, 15 February 2023 Offline (hist | edit) [866 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Offline (Page Replacements)}} == Description == When page fault occurs during the program execution, operating systems use page replacement algorithms to select a victim page from primary memory and makes room for the required page. == Related Problems == Related: Online == Parameters == No parameters found. == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Ap...")
- 10:26, 15 February 2023 Dining Philosophers Problem (hist | edit) [1,486 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Dining Philosophers Problem (Deadlock Avoidance)}} == Description == There are $n$ philosophers numbered 0 through $n-1$, seated around a circle table. Their only problem--besides philosophy--is that the dish served is a very difficult kind of spaghetti, that has to be eaten with two forks. There are two forks next to each plate, so that presents no difficulty: as a consequence, however, no two neighbors may be eating simultaneously. The philosophers' li...")
- 10:26, 15 February 2023 Deadlock Avoidance (hist | edit) [748 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Deadlock Avoidance (Deadlock Avoidance)}} == Description == A deadlock means that the processing of some parts, once started, cannot finish because each of these parts requests for its advancement some resource(s) currently held by some other part(s) in this set. In a deadlock avoidance approach, the controller must ensure that the granting of resources to any process will lead to a resulting state which is “safe,” i.e., a state from which all the p...")
- 10:26, 15 February 2023 Weighted Interval Schedule Maximization Problem (ISMP) (hist | edit) [567 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Weighted Interval Schedule Maximization Problem (ISMP) (Interval Scheduling)}} == Description == In Weighted Interval Scheduling, each interval has an associated weight. The goal is to maximize the weights of the accepted (and not interrupted) intervals. == Related Problems == Related: Unweighted Interval Scheduling == Parameters == <pre>n: number of tasks (intervals) k: number of machines (resources)</pre> == Table of Algorithms == Currentl...")
- 10:26, 15 February 2023 Unweighted Interval Scheduling (hist | edit) [2,931 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Unweighted Interval Scheduling (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 they ar...")
- 10:26, 15 February 2023 Polynomial Interpolation (hist | edit) [1,549 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Polynomial Interpolation (Polynomial Interpolation)}} == Description == Given a finite number of points $x_1, \ldots , x_n$, some real constants $y_1, \ldots , y_n$ and a subspace $V$ of $\Pi^d$, find a polynomial $p \in V$, such that $p(x_j) = y_j$, $j = 1, ... , n$ == Parameters == <pre>n: number of points d: dimension of space</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem. == Time Complexity grap...")
- 10:26, 15 February 2023 Block Ciphers (hist | edit) [1,395 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Block Ciphers (Block Ciphers)}} == Description == A block cipher is a pair of functions $E: \{0, 1\}^k \times \{0, 1\}^n \rightarrow \{0, 1\}^n$ and $D: \{0, 1\}^k \times \{0, 1\}^n \rightarrow \{0, 1\}^n$ that encode and decode a length $n$ string with a length $k$ key. == Parameters == <pre>n: text length (block size) k: key length</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Ye...")
- 10:26, 15 February 2023 Solutions to Nonlinear Equations (hist | edit) [1,307 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Solutions to Nonlinear Equations (Solutions to Nonlinear Equations)}} == Description == Compute the solutions to a given nonlinear equation of the form $f(x) = 0$. == Parameters == No parameters found. == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference |- | Bisection method (Solutions to Nonlinear Equations Solutions to N...")
- 10:26, 15 February 2023 Secret Sharing (hist | edit) [1,127 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Secret Sharing (Secret Sharing)}} == Description == Secret Sharing is the splitting up of a secret amongst a group such that no individual can learn the entire secret alone, but when a sufficient amount of the group comes together with their parts of the secret, they can reconstruct the secret. == Parameters == <pre>n: size of the group the secret is being shared with</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:...")
- 10:26, 15 February 2023 Unkeyed Hash Functions (hist | edit) [1,908 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Unkeyed Hash Functions (One-Way Hash Functions)}} == Description == A hash function, otherwise known as a one-way hash function, takes an arbitrary message of arbitrary length and creates an output (a hash) of a fixed length. The main characteristics of a cryptographic hash function are that given a message, it is easy to compute the hash; given the hash, it is difficult to compute the message; and that given a message, it is difficult to find a differen...")
- 10:26, 15 February 2023 Keyed Hash Functions (hist | edit) [1,062 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Keyed Hash Functions (One-Way Hash Functions)}} == Description == A hash function, otherwise known as a one-way hash function, takes an arbitrary message of arbitrary length and creates an output (a hash) of a fixed length. The main characteristics of a cryptographic hash function are that given a message, it is easy to compute the hash; given the hash, it is difficult to compute the message; and that given a message, it is difficult to find a different...")
- 10:26, 15 February 2023 Volterra Equations (hist | edit) [670 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Volterra Equations (Integral Equations)}} == Description == Integral equations are equations where an unknown function appears under an integral sign. Volterra equations have one limit of integration fixed while the other is a variable. == Related Problems == Related: Fredholm Equations == Parameters == No parameters found. == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Ti...")
- 10:26, 15 February 2023 Fredholm Equations (hist | edit) [691 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Fredholm Equations (Integral Equations)}} == Description == Integral equations are equations where an unknown function appears under an integral sign. Fredholm equations have both limits of integration fixed, and there are three types of Fredholm equations. == Related Problems == Related: Volterra Equations == Parameters == No parameters found. == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%"...")
- 10:26, 15 February 2023 The Frequent Words Problem (hist | edit) [1,059 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:The Frequent Words Problem (The Frequent Words Problem)}} == Description == Given a string of length $n$ and in input integer $k$, determine the most frequent $k$-mers in the string, i.e. the most frequent words of length $k$. == Parameters == <pre>n: length of string k: length of words sigma: size of alphabet</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! A...")
- 10:26, 15 February 2023 Tower of Hanoi (hist | edit) [1,595 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Tower of Hanoi (Tower of Hanoi)}} == Description == The Tower of Hanoi puzzle consists of $n$ discs, no two of the same size, stacked on $p \geq 3$ vertical pegs, in such a way that no disc lies on top of a smaller disc. A permissible $move$ is to take the top disc from one of the pegs and move it to one of the other pegs, as long as it is not placed on top of a smaller disc. Initially, they are all stacked on the first peg. The goal is to end up with th...")
- 10:26, 15 February 2023 Frequent Words with Mismatches Problem (hist | edit) [995 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Frequent Words with Mismatches Problem (Frequent Words with Mismatches Problem)}} == Description == Given two strings, determine the most frequent substring with at most $k$ mismatches, where mismatches are not counted towards the length of the substring. == Parameters == <pre>n: length of string k: length of words d: number of allowed mismatches sigma: size of alphabet</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-alig...")
- 10:26, 15 February 2023 Median String Problem with Binary Alphabets (hist | edit) [674 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Median String Problem with Binary Alphabets (Median String Problem)}} == Description == Given a binary alphabet $\Sigma$, a set $W$ of strings over $\Sigma$, and the Levenshtein distance between strings, find a string over $\Sigma$ that minimizes the sum of distances to the strings of $W$. == Related Problems == Related: Median String Problem with Unbounded Alphabets, Median String Problem with Bounded Alphabets == Parameters == <pre>n: num...")
- 10:26, 15 February 2023 Median String Problem with Bounded Alphabets (hist | edit) [675 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Median String Problem with Bounded Alphabets (Median String Problem)}} == Description == Given a bounded alphabet $\Sigma$, a set $W$ of strings over $\Sigma$, and the Levenshtein distance between strings, find a string over $\Sigma$ that minimizes the sum of distances to the strings of $W$. == Related Problems == Related: Median String Problem with Unbounded Alphabets, Median String Problem with Binary Alphabets == Parameters == <pre>n: nu...")
- 10:26, 15 February 2023 Median String Problem with Unbounded Alphabets (hist | edit) [1,075 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Median String Problem with Unbounded Alphabets (Median String Problem)}} == Description == Given an unbounded alphabet $\Sigma$, a set $W$ of strings over $\Sigma$, and the Levenshtein distance between strings, find a string over $\Sigma$ that minimizes the sum of distances to the strings of $W$. == Related Problems == Related: Median String Problem with Bounded Alphabets, Median String Problem with Binary Alphabets == Parameters == <pre>n:...")
- 10:26, 15 February 2023 N-Queens Completion (hist | edit) [782 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:n-Queens Completion (n-Queens Problem)}} == Description == Given an $n \times n$ chessboard that already has $k$ queens on it, complete the board such that there are $n$ queens, all of which cannot attack each other. == Related Problems == Related: Counting Solutions, Constructing Solutions == Parameters == <pre>n: size of chessboard k: number of queens given</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-alig...")
- 10:26, 15 February 2023 Constructing Solutions (hist | edit) [506 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Constructing Solutions (n-Queens Problem)}} == Description == What are all of the ways can one put $n$ queens on an $n \times n$ chessboard so that no two queens attack each other? == Related Problems == Related: Counting Solutions, n-Queens Completion == Parameters == <pre>n: number of queens, size of chessboard</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem. == References/Citation == ht...")
- 10:26, 15 February 2023 Counting Solutions (hist | edit) [1,926 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Counting Solutions (n-Queens Problem)}} == Description == How many ways can one put $n$ queens on an $n \times n$ chessboard so that no two queens attack each other? In other words, how many points can be placed on an $n \times n$ grid so that no two are on the same row, column, or diagonal? == Related Problems == Related: Constructing Solutions, n-Queens Completion == Parameters == <pre>n: number of queens, size of chessboard</pre> == Tab...")
- 10:26, 15 February 2023 Turnpike Problem (hist | edit) [705 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Turnpike Problem (Turnpike Problem)}} == Description == Given $n$ points and $\binom{n}{2}$ distances, find each distance's corresponding pair of points. == 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 |- | Outside-In algorithm (Turnpike Problem Turnpike Problem)|Outside-...")
- 10:26, 15 February 2023 Change-Making Problem (hist | edit) [1,207 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Change-Making Problem (Change-Making Problem)}} == Description == Given an unlimited amount of coins of denominations $c_1, \ldots, c_n$, and a desired sum $S$, find the minimum number of coins necessary to make $S$. == Parameters == <pre>n: number of coin denominations S: sum to be made</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approximation Factor !!...")
- 10:25, 15 February 2023 Transitive Reduction Problem of Directed Graphs (hist | edit) [4,028 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Transitive Reduction Problem of Directed Graphs (Transitive Reduction Problem)}} == Description == A directed graph $G^t$ is said to be a transitive reduction of the directed graph $G$ provided that (i) $G$ has a directed path from vertex $u$ to vertex $v$ if and only if $G$ has a directed path from vertex $u$ to vertex $v$, and (ii) there is no graph with fewer arcs than $G^t$ satisfying condition (i). The problem asks to find such a graph $G^t$ for a g...")
- 10:25, 15 February 2023 Self-Balancing Trees Search (hist | edit) [1,814 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Self-Balancing Trees Search (Self-Balancing Trees Search)}} == Description == Search for a given element within a self-balancing tree. == Parameters == <pre>n: size of tree</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference |- | Hopcroft 2-3 Tree || 1970 || $O(logn)...")
- 10:25, 15 February 2023 Self-Balancing Trees Deletion (hist | edit) [1,633 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Self-Balancing Trees Deletion (Self-Balancing Trees Deletion)}} == Description == Delete a given element from a self-balancing tree. == Parameters == <pre>n: size of tree</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference |- | Hopcroft 2-3 Tree || 1970 || $O(logn)...")
- 10:25, 15 February 2023 Self-Balancing Trees Insertion (hist | edit) [1,643 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Self-Balancing Trees Insertion (Self-Balancing Trees Insertion)}} == Description == Insert a given element into a self-balancing tree. == Parameters == <pre>n: size of tree</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference |- | Hopcroft 2-3 Tree || 1970 || $O(lo...")
- 10:25, 15 February 2023 Self-Balancing Trees Creation (hist | edit) [1,834 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Self-Balancing Trees Creation (Self-Balancing Trees Creation)}} == Description == Create a self-balancing tree given a list of elements. == Parameters == <pre>n: size of tree</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference |- | AVL Tree || 1962 || $O(nlogn)$ || $O(n)$ |...")
- 10:25, 15 February 2023 Rod-Cutting Problem (hist | edit) [909 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Rod-Cutting Problem (Rod-Cutting Problem)}} == Description == Given a rod of length $n$, and prices $p_i$ for which one can sell a segment of the rod of length $i$ ($1 \leq i \leq n$), find the splitting of the rod for which one can earn the most money once they sell the rod segments produced. == Parameters == <pre>n: length of rod</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year...")
- 10:25, 15 February 2023 Discrete Logarithm Over Finite Fields (hist | edit) [2,884 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Discrete Logarithm Over Finite Fields (Logarithm Calculations)}} == Description == Let $F_{p^n}$ denote the finite field of $p^n$ elements, where $p$ is a prime. Let $x$ be a generator for the multiplicative group of $F_{p^n}$. The discrete logarithm problem over $F_{p^n}$ is to compute, for any given nonzero $h \in F_{p^n}$, the least nonnegative integer $e$ such that $x^e=h$. In this context we shall write $e=\log_x h$. == Parameters == <pre>n: numb...")
- 10:25, 15 February 2023 Sequence-To-Graph Alignment (hist | edit) [1,162 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Sequence-To-Graph Alignment (Sequence-to-Graph Alignment)}} == Description == This is pattern matching where you are given a pattern and a hypertext graph. The hypertext model is that the text forms a graph of $N$ nodes and $E$ edges, where a string is stored inside each node, and the edges indicate alternative texts that may follow the current node. The pattern is still a simple string of length $m$. It is also customary to transform this graph into a o...")
- 10:25, 15 February 2023 Integer Relation Among Integers (hist | edit) [790 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Integer Relation Among Integers (Integer Relation)}} == Description == Given a vector $x \in \mathbb{Z}^n$, find an integer relation, i.e. a non-zero vector $m \in \mathbb{Z}^n$ such that $<x, m> = 0$ == Related Problems == Generalizations: Integer Relation Among Reals == Parameters == <pre>n: dimensionality of vectors</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Ti...")
- 10:25, 15 February 2023 Integer Relation Among Reals (hist | edit) [785 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Integer Relation Among Reals (Integer Relation)}} == Description == Given a vector $x \in \mathbb{R}^n$, find an integer relation, i.e. a non-zero vector $m \in \mathbb{Z}^n$ such that $<x, m> = 0$ == Related Problems == Subproblem: Integer Relation Among Integers == Parameters == <pre>n: dimensionality of vectors</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !!...")
- 10:25, 15 February 2023 Determinant of Matrices with Integer Entries (hist | edit) [1,238 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Determinant of Matrices with Integer Entries (Determinant of Matrices with Integer Entries)}} == Description == Calculate the determinant of a given matrix with integer matrices. For such matrices, the determinant is also an integer. == Parameters == <pre>n: dimension of matrix</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! R...")
- 10:25, 15 February 2023 Undirected Wiener Index (hist | edit) [977 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Undirected Wiener Index (Wiener Index)}} == Description == Calculate the sum of the lengths of the shortest paths between all pairs of vertices in an undirected graph (typically in the chemical graph representing the non-hydrogen atoms in the molecule). == Related Problems == Related: Minimum Wiener Connector Problem == Parameters == <pre>n: number of vertices (number of non-hydrogen atoms in the molecule)</pre> == Table of Algorithms == Cur...")
- 10:25, 15 February 2023 Minimum Wiener Connector Problem (hist | edit) [629 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Minimum Wiener Connector Problem (Wiener Index)}} == Description == Given a connected graph $G = (V, E)$ and a set $Q \subseteq V$ of query vertices, find a subgraph of $G$ that connects all query vertices and has minimum Wiener index. == Related Problems == Related: Undirected Wiener Index == Parameters == <pre>n: number of vertices m: number of edges q: number of query vertices</pre> == Table of Algorithms == Currently no algorithms in our...")
- 10:25, 15 February 2023 Maximum Cut (hist | edit) [1,989 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Maximum Cut (Maximum Cut)}} == Description == Given a graph $G=(V, E)$ with edge weights $c_e > 0$ for all $e\in E$, find a cut $\delta(W)$ such that $c(\delta(W)):=\Sigma_{e\in \dela(W)} c_e$ is as large as possible. == Parameters == <pre>n: number of vertices m: number of edges</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approximation Factor !! Model !!...")
- 10:25, 15 February 2023 D-Neighborhood of a String (hist | edit) [978 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:d-Neighborhood of a String (d-Neighborhood of a String)}} == Description == Given a DNA string pattern and an integer $d$, find the collection of strings that are within a $d$-neighborhood of the given pattern. A $d$-neighborhood is the set of all $k$-mers whose Hamming distance from the pattern is at most $d$. == Parameters == <pre>n: length of string d: neighborhood distance threshold sigma: size of alphabet</pre> == Table of Algorithms == {| cla...")
- 10:25, 15 February 2023 SLAM Algorithms (hist | edit) [1,790 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:SLAM Algorithms (SLAM Algorithms)}} == Description == Simultaneous localization and mapping (SLAM) is the computational problem of constructing or updating a map of an unknown environment while simultaneously keeping track of an agent's location within it. == Parameters == No parameters found. == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approximation Factor !!...")
- 10:25, 15 February 2023 Occupancy Grid Mapping (hist | edit) [1,060 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Occupancy Grid Mapping (Occupancy Grid Mapping)}} == Description == Assuming a robot's pose is known, generate a occupancy grid mapping of the area. The occupancy grid is a multidimensional random field that maintains stochastic estimates of the occupancy state of the cells in a spatial lattice. To construct a sensor-derived map of the robot’s world, the cell state estimates are obtained by interpreting the incoming range readings using probabilistic s...")
- 10:25, 15 February 2023 Environment Mapping (hist | edit) [1,914 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Environment Mapping (Texture Mapping)}} == Description == Texture mapping means the mapping of a function onto a surface in 3D. The domain of the function can be one, two, or three dimensional, and it can be represented by either an array or a mathematical function. The source image (texture) is mapped onto a surface in 3D object space, which is then mapped to the destination image (screen) by the viewing projection. Texture space is labeled $(u, v)$, o...")
- 10:25, 15 February 2023 Rasterization (hist | edit) [908 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Rasterization (Rasterization)}} == Description == Raster-scan displays are most commonly driven by a frame buffer, a memory that stores the color value for every picture element on the screen and refreshes the display continuously. The process of generating these picture clement values from a geometric description of the image is known as rasterization. == Parameters == No parameters found. == Table of Algorithms == {| class="wikitable sortable" s...")
- 10:25, 15 February 2023 POMDPs (hist | edit) [2,598 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:POMDPs (POMDPs)}} == Description == At (discrete) time step $t$, the environment is assumed to be in some state $X_t$. The agent then performs an action (control) $A_t$, whereupon the environment (stochastically) changes to a new state $X_{t+1}$. The agent doesn’t see the environment state, but instead receives an observation $Y_t$, which is some (stochastic) function of $X_t$. (If $Y_t = X_t$, the POMDP reduces to a fully observed MDP.) In addition, t...")