DAA
PRIMS
// A C++ program for Prim's Minimum
// Spanning Tree (MST) algorithm. The program is
// for adjacency matrix representation of the graph
#include <bits/stdc++.h>
using namespace std;
// Number of vertices in the graph
#define V 5
// A utility function to find the vertex with
// minimum key value, from the set of vertices
// not yet included in MST
int minKey(int key[], bool mstSet[])
{
// Initialize min value
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++)
if (mstSet[v] == false && key[v] < min)
min = key[v], min_index = v;
return min_index;
}
// A utility function to print the
// constructed MST stored in parent[]
void printMST(int parent[], int graph[V][V])
{
cout << "Edge \tWeight\n";
for (int i = 1; i < V; i++)
cout << parent[i] << " - " << i << " \t"
<< graph[i][parent[i]] << " \n";
}
// Function to construct and print MST for
// a graph represented using adjacency
// matrix representation
void primMST(int graph[V][V])
{
// Array to store constructed MST
int parent[V];
// Key values used to pick minimum weight edge in cut
int key[V];
// To represent set of vertices included in MST
bool mstSet[V];
// Initialize all keys as INFINITE
for (int i = 0; i < V; i++)
key[i] = INT_MAX, mstSet[i] = false;
// Always include first 1st vertex in MST.
// Make key 0 so that this vertex is picked as first
// vertex.
key[0] = 0;
// First node is always root of MST
parent[0] = -1;
// The MST will have V vertices
for (int count = 0; count < V - 1; count++) {
// Pick the minimum key vertex from the
// set of vertices not yet included in MST
int u = minKey(key, mstSet);
// Add the picked vertex to the MST Set
mstSet[u] = true;
// Update key value and parent index of
// the adjacent vertices of the picked vertex.
// Consider only those vertices which are not
// yet included in MST
for (int v = 0; v < V; v++)
// graph[u][v] is non zero only for adjacent
// vertices of m mstSet[v] is false for vertices
// not yet included in MST Update the key only
// if graph[u][v] is smaller than key[v]
if (graph[u][v] && mstSet[v] == false
&& graph[u][v] < key[v])
parent[v] = u, key[v] = graph[u][v];
}
// Print the constructed MST
printMST(parent, graph);
}
// Driver's code
int main()
{
int graph[V][V] = { { 0, 4, 0, 1, 0 },-
{ 2, 0, 6, 8, 5 },
{ 0, 7, 0, 0, 4 },
{ 2, 8, 0, 0, 9 },
{ 0, 5, 6, 8, 0 } };
// Print the solution
primMST(graph);
return 0;
}
---------------------------------------------------------------------------
ACTIVITY CABS
#include<iostream>
using namespace std;
// Prints a maximum set of activities that can be done by a single
// person, one at a time.
// n --> Total number persons
// s[] --> An array that contains start time of all person
// f[] --> An array that contains finish time of all persons
int printMaxcabs(int s[], int f[], int n)
{
int i, j, count =1;
printf ("No of person selected \n");
// The first activity always gets selected
i = 0;
printf("%d ", i);
// Consider rest of the activities
for (j = 1; j < n; j++)
{
// If this activity has start time greater than or
// equal to the finish time of previously selected
// activity, then select it
if (s[j] >= f[i])
{
printf ("%d ", j);
i = j;
count++;
}
}
return count;
}
int main()
{
int s[30],f[30], n
;
cout<<"\n Enter the number of person :";
cin>>n;
for (int i=0;i<n;i++)
{
cout<<"\n Start time for "<<i<<" person :";
cin>>s[i];
cout<<"\n Finish time for "<<i<<" person :";
cin>>f[i];
}
int result= printMaxcabs(s, f, n);
cout<<"\n Number of Cabs required :"<<result;
return 0;
}
-------------------------------------------------------------------------------------
RABIN KARP
/* Following program is a C++ implementation of Rabin Karp
Algorithm given in the CLRS book */
#include <bits/stdc++.h>
using namespace std;
// d is the number of characters in the input alphabet
#define d 256
/* pat -> pattern
txt -> text
q -> A prime number
*/
void search(char pat[], char txt[], int q)-
{
int M = strlen(pat);
int N = strlen(txt);
int i, j;
int p = 0; // hash value for pattern
int t = 0; // hash value for txt
int h = 1;
// The value of h would be "pow(d, M-1)%q"
for (i = 0; i < M - 1; i++)
h = (h * d) % q;
// Calculate the hash value of pattern and first
// window of text
for (i = 0; i < M; i++) {
p = (d * p + pat[i]) % q;
t = (d * t + txt[i]) % q;
}
// Slide the pattern over text one by one
for (i = 0; i <= N - M; i++) {
// Check the hash values of current window of text
// and pattern. If the hash values match then only
// check for characters one by one
if (p == t) {
/* Check for characters one by one */
for (j = 0; j < M; j++) {
if (txt[i + j] != pat[j]) {
break;
}
}
// if p == t and pat[0...M-1] = txt[i, i+1,
// ...i+M-1]
if (j == M)
cout << "Pattern found at index " << i
<< endl;
}
// Calculate hash value for next window of text:
// Remove leading digit, add trailing digit
if (i < N - M) {
t = (d * (t - txt[i] * h) + txt[i + M]) % q;
// We might get negative value of t, converting
// it to positive
if (t < 0)
t = (t + q);
}
}
}
/* Driver code */
int main()
{
char txt[] = "i never learned to read your mind , never learned to read my mind";
char pat[] = "mind";
// we mod to avoid overflowing of value but we should
// take as big q as possible to avoid the collison
int q = INT_MAX;
// Function Call
search(pat, txt, q);
return 0;
}
// This is code is contributed by rathbhupendra
-------------------------------------------------------------------------------------
HUFFMAN
#include <bits/stdc++.h>
using namespace std;
struct MinHeapNode
{
char d;
unsigned frequency;
MinHeapNode *lChild, *rChild;
//constructor
MinHeapNode(char d, unsigned frequency)
{
lChild = rChild = NULL;
this->d = d;
this->frequency = frequency;
}
};
//function to compare
struct compare
{
bool operator()(MinHeapNode *l, MinHeapNode *r)
{
return (l->frequency > r->frequency);
}
};
void printCodes(struct MinHeapNode *root, string str)
{
if (!root)
return;
if (root->d != '$')
cout << root->d << ": " << str << "\n";
printCodes(root->lChild, str + "0");
printCodes(root->rChild, str + "1");
}
void HuffmanCodes(char d[], int frequency[], int size)
{
struct MinHeapNode *lChild, *rChild, *top;
priority_queue<MinHeapNode *, vector<MinHeapNode *>, compare> minHeap;
for (int i = 0; i < size; ++i)
minHeap.push(new MinHeapNode(d[i], frequency[i]));
while (minHeap.size() != 1)
{
lChild = minHeap.top();
minHeap.pop();
rChild = minHeap.top();
minHeap.pop();
top = new MinHeapNode('$', lChild->frequency + rChild->frequency);
top->lChild = lChild;
top->rChild = rChild;
minHeap.push(top);
}
printCodes(minHeap.top(), "");
}
int main()
{
char arr[] = {'a', 'b', 'c', 'd', 'e', 'f'};
int frequency[] = {5, 9, 12, 13, 16, 45};
int size = sizeof(arr) / sizeof(arr[0]);
HuffmanCodes(arr, frequency, size);
return 0;
}
-------------------------------------------------------------------------------------
TSP
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 4;
const int INF = 1e9;
int dist[N][N] = {{0, 10, 15, 20},
{10, 0, 35, 25},
{15, 35, 0, 30},
{20, 25, 30, 0}};
int tsp(int start, int visited, int current, int cnt, int path[]) {
if(cnt == N) { // all cities visited
return dist[current][start];
}
int ans = INF;
for(int i = 0; i < N; i++) {
if(!(visited & (1<<i))) { // if i-th city is not visited
path[cnt] = i;
ans = min(ans, dist[current][i] + tsp(start, visited | (1<<i), i, cnt+1, path));
}
}
return ans;
}
int main() {
int path[N];
int ans = INF;
int start = 0; // starting city
for(int i = 0; i < N; i++) {
path[0] = i; // set first city in path
ans = min(ans, dist[start][i] + tsp(start, 1<<i, i, 1, path));
}
cout << "Minimum distance: " << ans << endl;
cout << "Path: ";
cout <<endl<< start <<" " ; // add starting city at the end
for(int i = 0; i < N; i++) {
cout << path[i] << " ";
}
return 0;
}
----------------------------------------------------------------------------------
COINS CHANGING
#include<bits/stdc++.h>
using namespace std;
const int INF = 100000;
//k is number of denominations of the coin or length of d
int dynamic(int d[], int n, int k) {
int M[n+1];
M[0] = 0;
int S[n+1];
S[0] = 0;
int i, j;
for(j=1; j<=n; j++) {
int minimum = INF;
int coin=0;
for(i=1; i<=k; i++) {
if(j >= d[i]) {
if((1+M[j-d[i]]) < minimum) {
minimum = 1+M[j-d[i]];
coin = i;
}
}
}
M[j] = minimum;
S[j] = coin;
}
int l = n;
while(l>0) {
printf("\n Coins used are : %d\n",d[S[l]]);
l = l-d[S[l]];
}
return 0;
}
int greedy(int coins[], int num, int amount)
{
int coin_counter = 0;
int j = num - 1;
sort(coins, coins + num);
while(amount != 0)
{
if(amount >= coins[j])
{
coin_counter++;
cout << "\nCoin " << coins[j] << " used\n";
amount = amount - coins[j];
}
else
{
j--;
}
}
return coin_counter;
}
/*
int dynamic(int coins[], int n, int amount) {
int dp[amount + 1];
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
dp[i] = INT_MAX;
for (int j = 0; j < n; j++) {
if (coins[j] <= i && dp[i - coins[j]] != INT_MAX) {
dp[i] = min(dp[i], dp[i - coins[j]] + 1);
}
if(dp[i] == coins[j])
{
cout << "\nCoin " << coins[j] << " used\n";
}
}
}
return dp[amount];
}
*/
int main() {
int choice;
do {
cout << "1. Dynamic Programming approach\n";
cout << "2. Greedy approach\n";
cout << "3. Exit\n";
cout << "Enter your choice: ";
cin >> choice;
switch (choice) {
case 1: {
int n, amount;
cout << "Enter the number of coins denominations: ";
cin >> n;
int coins[n];
cout << "Enter the coins denominations: ";
for (int i = 0; i < n; i++) {
cin >> coins[i];
}
cout << "Enter the amount: ";
cin >> amount;
dynamic(coins, amount, n);
cout<<endl;
break;
}
case 2: {
int n, amount;
cout << "Enter the number of coins denominations: ";
cin >> n;
int coins[n];
cout << "Enter the coins denominations: ";
for (int i = 0; i < n; i++) {
cin >> coins[i];
}
cout << "Enter the amount: ";
cin >> amount;
cout << "Minimum number of coins required using Greedy Approach: " << greedy(coins, n, amount) << endl;
break;
}
case 3: {
cout<<"Exiting ! byee ! "<<endl;
break;
}
default: {
cout << "Invalid choice! Please try again.\n";
}
}
} while (choice != 3);
return 0;
}
--------------------------------------------------------------------------------------------
KRURKSHAL
// C++ program for Kruskal's algorithm to find Minimum
// Spanning Tree of a given connected, undirected and
// weighted graph
#include<bits/stdc++.h>
using namespace std;
// Creating shortcut for an integer pair
typedef pair<int, int> iPair;
// Structure to represent a graph
struct Graph
{
int V, E;
vector< pair<int, iPair> > edges;
// Constructor
Graph(int V, int E)
{
this->V = V;
this->E = E;
}
// Utility function to add an edge
void addEdge(int u, int v, int w)
{
edges.push_back({w, {u, v}});
}
// Function to find MST using Kruskal's
// MST algorithm
int kruskalMST();
};
// To represent Disjoint Sets
struct DisjointSets
{
int *parent, *rnk;
int n;
// Constructor.
DisjointSets(int n)
{
// Allocate memory
this->n = n;
parent = new int[n+1];
rnk = new int[n+1];
// Initially, all vertices are in
// different sets and have rank 0.
for (int i = 0; i <= n; i++)
{
rnk[i] = 0;
//every element is parent of itself
parent[i] = i;
}
}
// Find the parent of a node 'u'
// Path Compression
int find(int u)
{
/* Make the parent of the nodes in the path
from u--> parent[u] point to parent[u] */
if (u != parent[u])
parent[u] = find(parent[u]);
return parent[u];
}
// Union by rank
void merge(int x, int y)
{
x = find(x), y = find(y);
/* Make tree with smaller height
a subtree of the other tree */
if (rnk[x] > rnk[y])
parent[y] = x;
else // If rnk[x] <= rnk[y]
parent[x] = y;
if (rnk[x] == rnk[y])
rnk[y]++;
}
};
/* Functions returns weight of the MST*/
int Graph::kruskalMST()
{
int mst_wt = 0; // Initialize result
// Sort edges in increasing order on basis of cost
sort(edges.begin(), edges.end());
// Create disjoint sets
DisjointSets ds(V);
// Iterate through all sorted edges
vector< pair<int, iPair> >::iterator it;
for (it=edges.begin(); it!=edges.end(); it++)
{
int u = it->second.first;
int v = it->second.second;
int set_u = ds.find(u);
int set_v = ds.find(v);
// Check if the selected edge is creating
// a cycle or not (Cycle is created if u
// and v belong to same set)
if (set_u != set_v)
{
// Current edge will be in the MST
// so print it
cout << u << " - " << v << endl;
// Update MST weight
mst_wt += it->first;
// Merge two sets
ds.merge(set_u, set_v);
}
}
return mst_wt;
}
// Driver program to test above functions
int main()
{
/* Let us create above shown weighted
and undirected graph */
int V = 9, E = 14;
Graph g(V, E);
// making above shown graph
g.addEdge(0, 2, 4);
g.addEdge(0, 5, 8);
g.addEdge(1, 2, 8);
g.addEdge(1, 7, 11);
g.addEdge(2, 8, 7);
g.addEdge(2, 3, 2);
g.addEdge(2, 5, 4);
g.addEdge(3, 4, 9);
g.addEdge(3, 5, 14);
g.addEdge(4, 3, 10);
g.addEdge(5, 6, 2);
g.addEdge(6, 7, 1);
g.addEdge(6, 2, 6);
g.addEdge(7, 8, 7);
cout << "Edges of MST are \n";
int mst_wt = g.kruskalMST();
cout << "\nWeight of MST is " << mst_wt;
return 0;
}
--------------------------------------------------------------------------------------------
BOYE MOOREE
/* C++ Program for Bad Character Heuristic of Boyer
Moore String Matching Algorithm */
#include <bits/stdc++.h>
using namespace std;
# define NO_OF_CHARS 256
// The preprocessing function for Boyer Moore's
// bad character heuristic
void badCharHeuristic( string str, int size,
int badchar[NO_OF_CHARS])
{
int i;
// Initialize all occurrences as -1
for (i = 0; i < NO_OF_CHARS; i++)
badchar[i] = -1;
// Fill the actual value of last occurrence
// of a character
for (i = 0; i < size; i++)
badchar[(int) str[i]] = i;
}
/* A pattern searching function that uses Bad
Character Heuristic of Boyer Moore Algorithm */
void search( string txt, string pat)
{
int m = pat.size();
int n = txt.size();
int badchar[NO_OF_CHARS];
/* Fill the bad character array by calling
the preprocessing function badCharHeuristic()
for given pattern */
badCharHeuristic(pat, m, badchar);
int s = 0; // s is shift of the pattern with
// respect to text
while(s <= (n - m))
{
int j = m - 1;
/* Keep reducing index j of pattern while
characters of pattern and text are
matching at this shift s */
while(j >= 0 && pat[j] == txt[s + j])
j--;
/* If the pattern is present at current
shift, then index j will become -1 after
the above loop */
if (j < 0)
{
cout << "pattern occurs at shift = " << s << endl;
/* Shift the pattern so that the next
character in text aligns with the last
occurrence of it in pattern.
The condition s+m < n is necessary for
the case when pattern occurs at the end
of text */
s += (s + m < n)? m-badchar[txt[s + m]] : 1;
}
else
/* Shift the pattern so that the bad character
in text aligns with the last occurrence of
it in pattern. The max function is used to
make sure that we get a positive shift.
We may get a negative shift if the last
occurrence of bad character in pattern
is on the right side of the current
character. */
s += max(1, j - badchar[txt[s + j]]);
}
}
/* Driver code */
int main()
{
string txt= "ABAAABCD";
string pat = "ABC";
search(txt, pat);
return 0;
}
// This code is contributed by rathbhupendra
-----------------------------------------------------------------------------------------------------
Min max using dc
#include<stdio.h>
#include<stdio.h>
int max, min;
int a[100];
void maxmin(int i, int j)
{
int max1, min1, mid;
if(i==j)
{
max = min = a[i];
}
else
{
if(i == j-1)
{
if(a[i] <a[j])
{
max = a[j];
min = a[i];
}
else
{
max = a[i];
min = a[j];
}
}
else
{
mid = (i+j)/2;
maxmin(i, mid);
max1 = max; min1 = min;
maxmin(mid+1, j);
if(max <max1)
max = max1;
if(min > min1)
min = min1;
}
}
}
int main ()
{
int i, num;
printf ("\nEnter the total number of numbers : ");
scanf ("%d",&num);
printf ("Enter the numbers : \n");
for (i=1;i<=num;i++)
scanf ("%d",&a[i]);
max = a[0];
min = a[0];
maxmin(1, num);
printf ("Minimum element in an array : %d\n", min);
printf ("Maximum element in an array : %d\n", max);
return 0;
}
--------------------------------------------------------------------------------------------
0/1 Greedy
#include <iostream>
using namespace std;
const int MAXN = 1000;
int n, m;
int w[MAXN], v[MAXN];
int knapsack() {
int ans = 0;
for (int i = 1; i <= n; i++) {
if (w[i] > m) break; // If the weight of the item exceeds the capacity of the knapsack, skip it
ans += v[i];
m -= w[i];
cout<< i <<" Item included ! "<<endl;
}
return ans;
}
int main() {
cout<<"Enter the no. of elements : ";
cin >> n;
for (int i = 1; i <= n; i++) {
cout<<"\nEnter the weight of "<<i<<" th element : ";
cin >> w[i];
cout<<"\nEnter the value of "<<i<<"th element : ";
cin>>v[i];
}
cout<<"\nEnter the maximum capacity of the knapsack : ";
cin>>m;
int ans = knapsack();
cout << "\n\nProfit is : "<< ans << endl;
return 0;
}
/*
#include <iostream>
using namespace std;
void knapSack(int W, int wt[], int val[], int n) {
int i, j, maxVal = 0, curW = 0;
for (i = 0; i < n; i++) {
if (curW + wt[i] <= W) {
curW += wt[i];
maxVal += val[i];
}
else {
int remain = W - curW;
maxVal += (remain * val[i]) / wt[i];
break;
}
}
cout << "Maximum value that can be put in a knapsack of capacity " << W << " is " << maxVal << endl;
}
int main() {
int val[] = { 60, 100, 120 };
int wt[] = { 10, 20, 30 };
int W = 50;
int n = sizeof(val) / sizeof(val[0]);
knapSack(W, wt, val, n);
return 0;
}
*/
--------------------------------------------------------------------------------------------
0/1 dynamic
#include <iostream>
using namespace std;
int knapSack(int W, int wt[], int val[], int n) {
int i, w;
int K[n + 1][W + 1];
for (i = 0; i <= n; i++) {
for (w = 0; w <= W; w++) {
if (i == 0 || w == 0)
K[i][w] = 0;
else if (wt[i - 1] <= w)
K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);
else
K[i][w] = K[i - 1][w];
}
}
return K[n][W];
}
int main() {
int val[] = { 60, 100, 120 };
int wt[] = { 10, 20, 30 };
int W = 50;
int n = sizeof(val) / sizeof(val[0]);
cout << "Maximum profit that can be gained in a knapsack of capacity " << W << " is " << knapSack(W, wt, val, n) << endl;
return 0;
}
--------------------------------------------------------------------------------------------
fractional knapsack..
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef struct {
int v;
int w;
float d;
} Item;
void input(Item items[],int sizeOfItems) {
cout << "Enter total "<< sizeOfItems <<" item's values and weight" <<
endl;
for(int i = 0; i < sizeOfItems; i++) {
cout << "Enter "<< i+1 << " V ";
cin >> items[i].v;
cout << "Enter "<< i+1 << " W ";
cin >> items[i].w;
}
}
void display(Item items[], int sizeOfItems) {
int i;
cout << "values: ";
for(i = 0; i < sizeOfItems; i++) {
cout << items[i].v << "\t";
}
cout << endl << "weight: ";
for (i = 0; i < sizeOfItems; i++) {
cout << items[i].w << "\t";
}
cout << endl;
}
bool compare(Item i1, Item i2) {
return (i1.d > i2.d);
}
float knapsack(Item items[], int sizeOfItems, int W) {
int i, j;
float totalValue = 0, totalWeight = 0;
for (i = 0; i < sizeOfItems; i++) {
items[i].d = (float)items[i].v / items[i].w; //typecasting done (v is int and w is also int so we get final value of d as int)
}
sort(items, items+sizeOfItems, compare);
/*
uncomment if u need to check the data after sortingis done
cout << "values : ";
for(i = 0; i < sizeOfItems; i++) {
cout << items[i].v << "\t";
}
cout << endl << "weights: ";
for (i = 0; i < sizeOfItems; i++) {
cout << items[i].w << "\t";
}
cout << endl << "ratio : ";
for (i = 0; i < sizeOfItems; i++) {
cout << items[i].d << "\t";
}
cout << endl;
*/
for(i=0; i<sizeOfItems; i++) {
if(totalWeight + items[i].w<= W) {
totalValue += items[i].v ;
totalWeight += items[i].w;
} else {
int wt = W-totalWeight;
totalValue += (wt * items[i].d);
totalWeight += wt;
break;
}
}
cout << "Total weight in bag " << totalWeight<<endl;
return totalValue;
}
int main() {
int W;
Item items[4];
input(items, 4);
cout << "Entered data \n";
display(items,4);
cout<< "Enter Knapsack weight \n";
cin >> W;
float mxVal = knapsack(items, 4, W);
cout << "Max value for "<< W <<" weight is "<< mxVal;
}
