1. Java Programming examples on “Set Cover”
Greedy algorithms construct the solution in multiple steps by making a locally optimal decision in each step. Backtracking is a general algorithm for finding all solutions to some computational problems. Backtracking is easily implemented as a recursive algorithm. The process of simplifying the algebraic expression of a boolean function is called minimization. This section contains Java programs on finding the optimal solution for set cover problem using backtracking, implementing boolean logic minimization, finding the smallest set of vertices, using integer programming formula and greedy approach to solve set cover problem.
Java Program to Find the Smallest Set of Vertices that will Cover Each Edge atleast once
Java Program to Find an Optimal Solution for Set Cover Problem Using Backtracking
Java Program to Use Integer Programming Formula to Solve the Set Cover Problem
Java Program to Solve Set Cover Problem assuming at max 2 Elements in a Subset
Java Program to Implement Boolean Logic Minimization Using Set Cover Problem
Java Program to Use Greedy Approach to Solve Set Cover Problem
2. Java Programming examples on “Set Packing”
Set packing is a classical NP-complete problem in computational complexity theory and combinatorics, and was one of Karp’s 21 NP-complete problems. Exhaustive search algorithm evaluates every solution generated by the given solution iterator and selects the best one. The Java programs in this section deals with the implementation of exhaustive search algorithm and heuristic approach to solve set packing.
Java Program to Implement Exhaustive Search Algorithm for Set Packing
Java Program to Implement Heuristic Approach to Solve Set Packing
Java Program to Check if a Set Packing is Possible of Size k for a Given Pair of Universe U and a Family S of Subsets of U (U,S)
3. Java Programming examples on “String Matching”
String matches() method tells whether or not this string matches the given regular expression. String matching algorithms try to find a place where one or several strings are found within a larger string or text. Knuth–Morris–Pratt string searching algorithm search for a pattern of length m in a text string of length n. The Boyer-Moore algorithm uses information gathered during the preprocess step to skip sections of the text, resulting in a lower constant factor than many other string algorithms. Naive String Matching algorithm is optimized for the cases when all characters of pattern are different. Aho-Corasick Algorithm is a kind of dictionary-matching algorithm that locates elements of a finite set of strings within an input text. It matches all patterns simultaneously. The grep command usually searches for a specified pattern match within a text file or series of text files. fgrep command searches files for one or more pattern arguments. Extended grep command accepts the full set of the regular expression capabilities. Commentz-Walter algorithm is a string searching algorithm, it can search for multiple patterns at once. The java programs in this section deals with the implementation of knuth-morris-pratt algorithm, aho-corasick, boyer-moore algorithm, rabin-karp method and naive for string matching, zhu–takaoka string matching algorithm, performs string matching using string library and vectors.
Java Program to Implement the String Search Algorithm for Short Text Sizes
Java Program to Implement Knuth-Morris-Pratt Algorithm for String Matching
Java Program to Implement Boyer-Moore Algorithm for String Matching
Java Program to Repeatedly Search the Same Text (such as Bible by building a Data Structure)
Java Program to Implement Aho-Corasick Algorithm for String Matching
Java Program to Implement the Program Used in grep/egrep/fgrep
Java Program to Implement Rabin-Karp Method for String Matching
Java Program to Perform Naive String Matching
Java Program to Perform Finite State Automaton based Search
Java Program to Implement Bitap Algorithm for String Matching
Java Program to Implement Commentz-Walter Algorithm
Java Program to Implement Zhu–Takaoka String Matching Algorithm
Java Program to Perform String Matching Using String Library
Java Program to Implement String Matching Using Vectors
4. Java Programming examples on “Approximate String Matching”
Approximate string matching is a variation of exact string matching that demands more complex algorithms. Hirschberg’s algorithm is a dynamic programming algorithm that finds the optimal sequence alignment between two strings. Brute-Force Approach checks whether every single character from the text to match against the pattern. Wagner–Fischer algorithm is a dynamic programming algorithm that measures the Levenshtein distance between two strings of characters. The Java programs in this section deals with the implementation of bit parallel algorithm and brute force approach for string matching, implementing hirschberg’s clever recursive, levenshtein distance computing algorithm, wagner and fisher algorithms for approximate string matching.
Java Program to Use Dynamic Programming to Solve Approximate String Matching
Java Program to Implement Bit Parallel Algorithm for approximate String Matching
Java Program to Implement Hirschberg’s Clever Recursive Algorithm
Java Program to Implement Brute-Force Approach for Approximate String Matching
Java Program to Implement Levenshtein Distance Computing Algorithm
Java Program to Implement Wagner and Fisher Algorithm for online String Matching
5. Java Programming examples on “Cryptography”
Playfair cipher or Playfair square is a manual symmetric encryption technique and was the first literal digraph substitution cipher. MD5 message-digest algorithm is a widely used cryptographic hash function producing a 128-bit hash value. RSA is one of the first practicable public-key cryptosystems and is widely used for secure data transmission. Java Cryptography API enables to encrypt and decrypt data in Java, as well as manage keys, sign and authenticate messages. The affine cipher is a type of monoalphabetic substitution cipher, wherein each letter in an alphabet is mapped to its numeric equivalent, encrypted using a simple mathematical function, and converted back to a letter. This section contains Java programs on caesar cypher, encoding and decoding a message using playfair cipher, implementing one time pad algorithm, implementing md5 and rsa algorithm, implementing hill, affine and vigenere cypher.
6. Java Programming examples on “Finite State Machine Minimization”
DFA is a finite state machine that accepts/rejects finite strings of symbols and only produces a unique computation of the automaton for each input string. NFA is a finite state machine where from each state and a given input symbol, the automaton may move to several possible next states. This section contains Java programs on constructing dfa and nfa for a given expression.
Java Program to Minimize the Number of States in a Deterministic Finite Automata
Java Program to Construct DFA from NFA
Java Program to Construct NFA for a Given Expression
7. Java Programming examples on “Longest Common SubString/SubSequence”
Kadane algorithm is to used to obtain the maximum subarray sum from an array of integers. This section contains Java programs on implementing kadane algorithm, finding the longest increasing subsequence and shortest super sequence in sequences.
Java Program to Implement Kadane’s Algorithm
Java Program to Find the Longest Subsequence Common to All Sequences in a Set of Sequences
Java Program to Find the Longest Increasing Subsequence of a Given Sequence
Java Program to Find the Shortest Supersequence that Contains Two or more Sequences as Subsequences