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.

# Category 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) Problem# Implementation 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 Java# Implementing 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 Java# Program 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.

# Implementing 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