User contributions for Admin
Jump to navigation
Jump to search
15 February 2023
- 10:2710:27, 15 February 2023 diff hist +41 N DNF-SAT Redirected page to Disjunctive Normal Form SAT current Tag: New redirect
- 10:2710:27, 15 February 2023 diff hist +764 N Disjunctive Normal Form SAT Created page with "{{DISPLAYTITLE:Disjunctive Normal Form SAT (Boolean Satisfiability)}} == Description == DNF-SAT restricts the boolean formula to disjunctive normal form (DNF), meaning it is the OR of ANDs. == Related Problems == Generalizations: SAT Related: Conjunctive Normal Form SAT, 1-in-3SAT, Monotone 1-in-3SAT, Monotone Not-Exactly-1-in-3SAT, All-Equal-SAT, Not-All-Equal 3-SAT (NAE 3SAT), Monotone Not-All-Equal 3-SAT (Monotone NAE 3SAT), k-S..."
- 10:2710:27, 15 February 2023 diff hist +41 N CNF-SAT Redirected page to Conjunctive Normal Form SAT current Tag: New redirect
- 10:2710:27, 15 February 2023 diff hist +9,087 N Conjunctive Normal Form SAT Created page with "{{DISPLAYTITLE:Conjunctive Normal Form SAT (Boolean Satisfiability)}} == Description == CNF-SAT restricts the boolean formula to conjunctive normal form (CNF), meaning it is the AND of ORs. == Related Problems == Generalizations: SAT Subproblem: All-Equal-SAT, k-SAT, XOR-SAT, Horn SAT, MaxSAT Related: Disjunctive Normal Form SAT, 1-in-3SAT, Monotone 1-in-3SAT, Monotone Not-Exactly-1-in-3SAT, Not-All-Equal 3-SAT (NAE 3S..."
- 10:2710:27, 15 February 2023 diff hist +17 N Boolean Satisfiability Redirected page to SAT current Tag: New redirect
- 10:2710:27, 15 February 2023 diff hist +822 N SAT Created page with "{{DISPLAYTITLE:SAT (Boolean Satisfiability)}} == Description == Boolean satisfiability problems involve determining if there is an assignment of variables that satisfies a given boolean formula. == Related Problems == Subproblem: Conjunctive Normal Form SAT, Disjunctive Normal Form SAT Related: Disjunctive Normal Form SAT, 1-in-3SAT, Monotone 1-in-3SAT, Monotone Not-Exactly-1-in-3SAT, All-Equal-SAT, Not-All-Equal 3-SAT (NAE 3SAT), [..."
- 10:2710:27, 15 February 2023 diff hist +31 N Chromatic Polynomial Created page with "#REDIRECT #k-Graph Coloring" current
- 10:2610:26, 15 February 2023 diff hist +987 N 5-Graph Coloring Created page with "{{DISPLAYTITLE:5-Graph Coloring (Graph Coloring)}} == Description == In this case, we wish to determine whether or not a graph is 5-colorable. == Related Problems == Generalizations: k-Graph Coloring Related: Chromatic Number, 2-Graph Coloring, 3-Graph Coloring, 4-Graph Coloring, #k-Graph Coloring, #2-Graph Coloring, #3-Graph Coloring, #4-Graph Coloring, #5-Graph Coloring == Parameters == <pre>n: number of vertices m: numb..."
- 10:2610:26, 15 February 2023 diff hist +2,060 N 4-Graph Coloring Created page with "{{DISPLAYTITLE:4-Graph Coloring (Graph Coloring)}} == Description == In this case, we wish to determine whether or not a graph is 4-colorable. == Related Problems == Generalizations: k-Graph Coloring Related: Chromatic Number, 2-Graph Coloring, 3-Graph Coloring, 5-Graph Coloring, #k-Graph Coloring, #2-Graph Coloring, #3-Graph Coloring, #4-Graph Coloring, #5-Graph Coloring == Parameters == <pre>n: number of vertices m: numb..."
- 10:2610:26, 15 February 2023 diff hist +3,681 N 3-Graph Coloring Created page with "{{DISPLAYTITLE:3-Graph Coloring (Graph Coloring)}} == Description == In this case, we wish to determine whether or not a graph is 3-colorable. == Related Problems == Generalizations: k-Graph Coloring Related: Chromatic Number, 2-Graph Coloring, 4-Graph Coloring, 5-Graph Coloring, #k-Graph Coloring, #2-Graph Coloring, #3-Graph Coloring, #4-Graph Coloring, #5-Graph Coloring == Parameters == <pre>n: number of vertices m: numb..."
- 10:2610:26, 15 February 2023 diff hist +876 N 2-Graph Coloring Created page with "{{DISPLAYTITLE:2-Graph Coloring (Graph Coloring)}} == Description == In this case, we wish to determine whether or not a graph is 2-colorable. == Related Problems == Generalizations: k-Graph Coloring Related: Chromatic Number, 3-Graph Coloring, 4-Graph Coloring, 5-Graph Coloring, #k-Graph Coloring, #2-Graph Coloring, #3-Graph Coloring, #4-Graph Coloring, #5-Graph Coloring == Parameters == <pre>n: number of vertices m: numb..."
- 10:2610:26, 15 February 2023 diff hist +1,007 N Chromatic Number 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:2610:26, 15 February 2023 diff hist +1,257 N K-Graph Coloring 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:2610:26, 15 February 2023 diff hist +3,342 N Link Analysis 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:2610:26, 15 February 2023 diff hist +470 N 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 == No parameters found. == Table of Algorithms == Currently no algorithms in our database for the given problem." current
- 10:2610:26, 15 February 2023 diff hist +554 N 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 == No parameters found. == Table of Algorithms == Currently no algorithms in our database for the given problem..." current
- 10:2610:26, 15 February 2023 diff hist +2,238 N Online 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:2610:26, 15 February 2023 diff hist +999 N Offline 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:2610:26, 15 February 2023 diff hist +1,495 N Dining Philosophers Problem 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:2610:26, 15 February 2023 diff hist +754 N Deadlock Avoidance 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:2610:26, 15 February 2023 diff hist +68 N Weighted Activity Selection Problem Redirected page to Weighted Interval Schedule Maximization Problem (ISMP) current Tag: New redirect
- 10:2610:26, 15 February 2023 diff hist +529 N Weighted Interval Schedule Maximization Problem (ISMP) 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:2610:26, 15 February 2023 diff hist +1,502 N Unweighted Interval Scheduling 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:2610:26, 15 February 2023 diff hist +37 N GCD Redirected page to Greatest Common Divisor current Tag: New redirect
- 10:2610:26, 15 February 2023 diff hist +210 Greatest Common Divisor No edit summary
- 10:2610:26, 15 February 2023 diff hist +711 N Polynomial Interpolation 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:2610:26, 15 February 2023 diff hist +1,401 N Block Ciphers 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:2610:26, 15 February 2023 diff hist +1,396 N Solutions to Nonlinear Equations 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:2610:26, 15 February 2023 diff hist +1,029 N Secret Sharing 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:2610:26, 15 February 2023 diff hist +1,908 N Unkeyed Hash Functions 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:2610:26, 15 February 2023 diff hist +1,062 N Keyed Hash Functions 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:2610:26, 15 February 2023 diff hist +670 N Volterra Equations 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..." current
- 10:2610:26, 15 February 2023 diff hist +691 N Fredholm Equations 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%"..." current
- 10:2610:26, 15 February 2023 diff hist +40 N The Frequent $k$-mers Problem Redirected page to The Frequent Words Problem current Tag: New redirect
- 10:2610:26, 15 February 2023 diff hist +1,261 N The Frequent Words Problem 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:2610:26, 15 February 2023 diff hist +1,798 N Tower of Hanoi 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:2610:26, 15 February 2023 diff hist +1,200 N Frequent Words with Mismatches Problem 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:2610:26, 15 February 2023 diff hist +683 N Median String Problem with Binary Alphabets 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:2610:26, 15 February 2023 diff hist +684 N Median String Problem with Bounded Alphabets 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:2610:26, 15 February 2023 diff hist +1,364 N Median String Problem with Unbounded Alphabets 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:2610:26, 15 February 2023 diff hist +788 N N-Queens Completion 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:2610:26, 15 February 2023 diff hist +515 N Constructing Solutions 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:2610:26, 15 February 2023 diff hist +1,244 N Counting Solutions 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:2610:26, 15 February 2023 diff hist +876 N Turnpike Problem 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:2610:26, 15 February 2023 diff hist +1,384 N Change-Making Problem 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:2510:25, 15 February 2023 diff hist +4,320 N Transitive Reduction Problem of Directed Graphs 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:2510:25, 15 February 2023 diff hist +2,003 N Self-Balancing Trees Search 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:2510:25, 15 February 2023 diff hist +1,826 N Self-Balancing Trees Deletion 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:2510:25, 15 February 2023 diff hist +1,838 N Self-Balancing Trees Insertion 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:2510:25, 15 February 2023 diff hist +2,017 N Self-Balancing Trees Creation 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)$ |..."