Knuth-Morris-Pratt (KMP) Algorithm
A string searching algorithm.
Aman Mehara
Continuous Knapsack Problem
Also known as the fractional knapsack problem.
Continuous knapsack problem can be solved by a greedy algorithm.
0/1 Knapsack Problem
Longest Common Subsequence
Subset Sum Problem
A special case of 0/1 Knapsack Problem.
Given a finite set \(S = \{ s \in \mathbb{Z}_+\}\) and an integer \(t < 0\), is there a subset
Partition Problem
A special case of Subset Problem.
Levenshtein Distance
#include <algorithm>
#include <vector>
class LevenshteinDistance {
std::vector<char> sequence1_;
std::vector<char> sequence2_;
public:
LevenshteinDistance(std::vector<char>& sequence1, std::vector<char>& sequence2) {
sequence1_ = sequence1;
sequence2_ = sequence2;
}
int Distance();
};
int LevenshteinDistance::Distance() {
int sequence1_size
Quadratic Equations
When \(a \ne 0\) , there are two solutions to \(ax^2 + bx + c = 0\) and they are
\[x = {-b \pm \sqrt{b^2-4ac} \over 2a}.\]
Discriminant: \(D = b^2-4ac\)
If \(\alpha\) and \(\beta\) are the roots of quadratic equation (\(ax^2 + bx + c = 0\)), then:
* \(\alpha + \beta = -{b \over
The Coin Change Problem
The coin change problem is a classic dynamic programming problem (unbounded knapsack problem) which can be solved recursively.
N = Coins with different denominations
D = Array of denominations
S = Total amount to make
C = Number of Combinations
Recursive Formula:
C(N, S) = C(N - 1, S) + C(N, S -
Hello World
This blog runs on DigitalOcean and is powered by Ghost.