1. C++ Programming examples on “Set Cover”
Backtracking is a general algorithm for finding all solutions to some computational problems. Set cover problem is a classical question in combinatorics, computer science and complexity theory. This section contains a C++ programs to find the optimal solution and smallest vertices using backtracking, implements boolean logic minimization, greedy approach and set cover problems.
C++ Program to Find the Smallest Set of Vertices that will Cover Each Edge atleast once
C++ Program to Find an Optimal Solution for Set Cover Problem Using Backtracking
C++ Program to Use Integer Programming Formula to Solve the Set Cover Problem
C++ Program to Solve Set Cover Problem assuming at max 2 Elements in a Subset
C++ Program to Implement Boolean Logic Minimization Using Set Cover Problem
C++ Program to Use Greedy Approach to Solve Set Cover Problem
2. C++ Programming examples on “Set Packing”
Heuristic is a technique designed for solving a problem more quickly when classic methods are too slow, or for finding an approximate solution when classic methods fail to find any exact solution. The C++ programs in this section deals with implementation of exhaustive search and heuristic approaches for set packing.
C++ Program to Implement Exhaustive Search Algorithm for Set Packing
C++ Program to Implement Heuristic Approach to Solve Set Packing
C++ 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. C++ Programming examples on “String Matching”
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 searches for occurrences of a word within a main text string. Rabin-Karp Algorithm is a string that uses hashing to find any one of a set of pattern strings in a text. Boyer-Moore algorithm is considered as the most efficient string-matching algorithm in usual applications. This algorithm scans the characters of the pattern from right to left beginning with the rightmost one. The bitap algorithm is an approximate string matching algorithm, algorithm tells whether a given text contains a substring which is approximately equal to a given pattern. The C++ programs in this section demonstrates the implementation of string search algorithm for short text sizes, knuth-morris-pratt algorithm, z algorithm, aho-corasick and boyer-moore algorithm for string matching, rabin-karp method and naive for string matching, commentz-walter algorithm, zhu–takaoka string matching algorithm, string matching using string library and vectors.
4. C++ Programming examples on “Approximate String Matching”
Wagner–Fischer algorithm is a dynamic programming algorithm that measures the Levenshtein distance between two strings of characters. The C++ programs in this section deals with the implementation of algorithms like bit parallel algorithm, hirschberg’s clever recursive, brute-force approach, levenshtein distance computing algorithm, wagner and fisher algorithms for approximate string matching.
C++ Program to Use Dynamic Programming to Solve Approximate String Matching
C++ Program to Implement Bit Parallel Algorithm for approximate String Matching
C++ Program to Implement Hirschberg’s Clever Recursive Algorithm
C++ Program to Implement Brute-Force Approach for Approximate String Matching
C++ Program to Implement Levenshtein Distance Computing Algorithm
C++ Program to Implement Wagner and Fisher Algorithm for online String Matching
5. C++ Programming examples on “Cryptography”
Caesar Cipher Encryption algorithm is the simplest of all, where every character of the message is replaced by its next 3rd character. Playfair cipher Input is not case sensitive and works only for characters from ‘a’ to ‘z’ and ‘A’ to ‘Z’, White spaces are ignored. One time pad cipher Input is not case sensitive and works only for all characters, White spaces are not ignored but are produced as random characters in the decoded message. RSA is one of the first practicable public-key cryptosystems and is widely used for secure data transmission. Hill cipher is a polygraphic substitution cipher based on linear algebra. Substitution cipher is a method of encoding by which units of plaintext are replaced with ciphertext, according to a regular system. The C++ programs in this section deals with the implementation of caesar cipher, playfair cipher, one time pad algorithm, md5 algorithm, rsa algorithm, monoalphabetic cypher, hill cypher, vigenere and affine cipher.
C++ Program to Implement Caesar Cypher
C++ Program to Enode a Message Using Playfair Cipher
C++ Program to Decode a Message Encoded Using Playfair Cipher
C++ Program to Implement the One Time Pad Algorithm
C++ Program to Implement the MD5 Algorithm
C++ Program to Implement the RSA Algorithm
C++ Program to Implement the Checksum Method for Small String Messages and Detect If the Received message is same as the Transmitted
C++ Program to Implement the Monoalphabetic Cypher
C++ Program to Implement the Hill Cypher
C++ Program to Implement the Vigenere Cypher
C++ Program to Perform Cryptography Using Transposition Technique
C++ Program to Implement Affine Cipher
6. C++ Programming examples on “Finite State Machine Minimization”
DFA is a finite state machine that accepts/rejects finite strings of symbols and has a unique transition from each state on each input symbol. NFA is a finite state machine where from each state and a given input symbol, the automaton may move to several possible next states. The following section contains C++ programs on Finite State Machine Minimization, deterministic finite automata, construction of DFA and NFA for a given expressions.
C++ Program to Minimize the Number of States in a Deterministic Finite Automata
C++ Program to Construct DFA from NFA
C++ Program to Construct NFA for a Given Expression
7. C++ Programming examples on “Longest Common SubString/SubSequence”
Kadane algorithm is to used to obtain the maximum subarray sum from an array of integers. The longest common subsequence problem is to find the longest subsequence common to all sequences in a set of sequences. This section contains a C++ programs to find the longest subsequence, prefix matching and shortest super sequence in sequences.
C++ Program to Implement Kadane’s Algorithm
C++ Program to Find the Longest Subsequence Common to All Sequences in a Set of Sequences
C++ Program to Find the Longest Increasing Subsequence of a Given Sequence
C++ Program to Find the Longest Prefix Matching of a Given Sequence
C++ Program to Find the Shortest Supersequence that Contains Two or more Sequences as Subsequences