The Knuth–Morris–Pratt string searching algorithm (or KMP algorithm) searches for occurrences of a “word” W within a main “text string” S by employing the observation that when a mismatch occurs, the word itself embodies sufficient information to determine where the next match could begin, thus bypassing re-examination of previously matched characters.
Continue reading Program to Implement KMP Algorithm in JavaCategory Archives: AOAD
Program to Implement K-Naive Algorithm in Java
Java Program for Longest Common Subsequence (LCS) Problem
The longest common subsequence (LCS) problem is the problem of finding the longest subsequence common to all sequences in a set of sequences (often just two sequences).
Continue reading Java Program for Longest Common Subsequence (LCS) ProblemImplementation of Graph Coloring Algorithm in Java
Graph Coloring is a way of coloring the vertices of a undirected graph such that no two adjacent vertices share the same color.
Continue reading Implementation of Graph Coloring Algorithm in JavaImplementing Sum of Subset by Backtracking in Java
Subset sum problem is to find subset of elements that are selected from a given set whose sum adds up to a given number K.
Continue reading Implementing Sum of Subset by Backtracking in JavaProgram for Implementation of N-Queen problem in Java
The n queens puzzle is the problem of placing eight chess queens on an n×n chessboard so that no two queens threaten each other. Thus, a solution requires that no two queens share the same row, column, or diagonal.
Continue reading Program for Implementation of N-Queen problem in JavaImplementing 0-1 Knapsack in Java
The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a mass and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.
In 0-1 Knapsack, the restriction is that, one cannot select fraction of any item. He/She must select either whole item or try with alternate one.
Continue reading Implementing 0-1 Knapsack in Java