Ex No:1 IMPLEMENTATION OF TOWER OF HANOI

Aim: To implement the tower of Hanoi program.

Program code:
#include<stdio.h>
#include<conio.h>
void TOH(int n,char x,char y,char z);
void main()
{
int n;
printf("\nEnter number of plates:");
scanf("%d",&n);
TOH(n,'A','B','C');
getch();
}
void TOH(int n,char x,char y,char z)
{
if(n>0)
{
TOH(n-1,x,z,y);
printf("\n%c ->%c",x,y);
TOH(n-1,z,y,x);
}
}
Output:
Ex:2 IMPLEMENT NTH FIBONACCI TERM USING RECURSION & ITERATION.

Aim: To implement nth fibonacci term using recursion and iteration

Program code:
#include<stdio.h>
#include<conio.h>
void main()
{
int n,i,c,a=0,b=1;
printf("\nEnter number :");
scanf("%d",&n);
if (n<0)
printf("\n Enter an integer>=0");
else
{
printf("\n The fibonacci series is given by");
printf("\n%d", a);
printf("\n%d", b);
for (i=2; i<n; i++)
{
c=a+b;
printf("\n%d", c);
a=b;
b=c;
}
}
getch();
}
Output:

Ex:03 IMPLEMENT BIN PACKING

Aim: To Implement Bin Packing
Program code:
#include<stdio.h>
void binPacking(int *a, int size, int n) {
int binCount = 1, i;
int s = size;
 for (i = 0; i < n; i++) {
if (s - *(a + i) > 0) {
s -= *(a + i);
continue;
} else {
binCount++;
s = size;
i--;
}
}

printf("Number of bins required: %d", binCount);

}

int main(int argc, char **argv) {

printf("Enter the number of items in Set: ");
int n;
int a[n], i;
int size;
scanf("%d", &n);
printf("Enter %d items:", n);

for (i = 0; i < n; i++)

scanf("%d", &a[i]);
printf("Enter the bin size: ");
scanf("%d", &size);
binPacking(a, size, n);
return 0;
}
Output:
Ex:4 IMPLEMENT FRACTIONAL KNAPSACK USING GREEDY METHOD

Aim: To Implement Fractional Knapsack using greedy method

Program code:
#include <bits/stdc++.h>

using namespace std;

// Structure for an item which stores weight and

// corresponding value of Item
struct Item {
int value, weight;

// Constructor
Item(int value, int weight)
{
this->value=value;
this->weight=weight;
}
};

// Comparison function to sort Item according to val/weight

// ratio
bool cmp(struct Item a, struct Item b)
{
double r1 = (double)a.value / (double)a.weight;
double r2 = (double)b.value / (double)b.weight;
return r1 > r2;
}

// Main greedy function to solve problem

double fractionalKnapsack(int W, struct Item arr[], int n)
{
// sorting Item on basis of ratio
sort(arr, arr + n, cmp);

// Uncomment to see new order of Items with their

// ratio
/*
for (int i = 0; i < n; i++)
{
cout << arr[i].value << " " << arr[i].weight << " :
"
<< ((double)arr[i].value / arr[i].weight) <<
endl;
 }
*/

int curWeight = 0; // Current weight in knapsack

double finalvalue = 0.0; // Result (value in Knapsack)

// Looping through all Items

for (int i = 0; i < n; i++) {
// If adding Item won't overflow, add it completely
if (curWeight + arr[i].weight <= W) {
curWeight += arr[i].weight;
finalvalue += arr[i].value;
}

// If we can't add current Item, add fractional part

// of it
else {
int remain = W - curWeight;
finalvalue += arr[i].value
* ((double)remain
/ (double)arr[i].weight);
break;
}
}

// Returning final value

return finalvalue;
}

// Driver code
int main()
{
int W = 50; // Weight of knapsack
Item arr[] = { { 60, 10 }, { 100, 20 }, { 120, 30 } };

int n = sizeof(arr) / sizeof(arr[0]);

// Function call
cout << "Maximum value we can obtain = "
<< fractionalKnapsack(W, arr, n);
return 0;
}
Output:

Ex:5 IMPLEMENT TRAVELLING SALESMAN PROBLEM

Aim: To Implement Travelling Salesman Problem

Program code:
#include <bits/stdc++.h>
using namespace std;
#define V 4

// implementation of traveling Salesman Problem

int travllingSalesmanProblem(int graph[][V], int s)
{
// store all vertex apart from source vertex
vector<int> vertex;
for (int i = 0; i < V; i++)
if (i != s)
vertex.push_back(i);

// store minimum weight Hamiltonian Cycle.

int min_path = INT_MAX;
do {

// store current Path weight(cost)

int current_pathweight = 0;

// compute current path weight

 int k = s;
for (int i = 0; i < vertex.size(); i++) {
current_pathweight += graph[k][vertex[i]];
k = vertex[i];
}
current_pathweight += graph[k][s];

// update minimum
min_path = min(min_path, current_pathweight);

} while (
next_permutation(vertex.begin(), vertex.end()));

return min_path;
}

// Driver Code
int main()
{
// matrix representation of graph
int graph[][V] = { { 0, 10, 15, 20 },
{ 10, 0, 35, 25 },
{ 15, 35, 0, 30 },
{ 20, 25, 30, 0 } };
int s = 0;
cout << travllingSalesmanProblem(graph, s) << endl;
return 0;
}

Output:
Ex:6 IMPLEMENT MINIMUM SPANNING TREE

Aim: To Implement Minimum Spanning Tree

Program code:

// 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;
parent[0] = -1; // First node is always root of MST

// 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 code
int main()
{
/* Let us create the following graph
23
 (0)--(1)--(2)
|/\|
6| 8/ \5 |7
|/\|
(3)-------(4)
9 */
int graph[V][V] = { { 0, 2, 0, 6, 0 },
{ 2, 0, 3, 8, 5 },
{ 0, 3, 0, 0, 7 },
{ 6, 8, 0, 0, 9 },
{ 0, 5, 7, 9, 0 } };

// Print the solution

primMST(graph);

return 0;
}

Output:

Ex:07 IMPLEMENT SHORTEST PATH ALGORITHM

Aim: To Implement Shortest path algorithm

Program code:

#include <limits.h>
#include <stdio.h>
// Number of vertices in the graph
#define V 9

// A utility function to find the vertex with minimum distance value, from
// the set of vertices not yet included in shortest path tree
int minDistance(int dist[], bool sptSet[])
{
// Initialize min value
int min = INT_MAX, min_index;

for (int v = 0; v < V; v++)

if (sptSet[v] == false && dist[v] <= min)
min = dist[v], min_index = v;

return min_index;
}

// A utility function to print the constructed distance array

void printSolution(int dist[])
{
printf("Vertex \t\t Distance from Source\n");
for (int i = 0; i < V; i++)
printf("%d \t\t %d\n", i, dist[i]);
}

// Function that implements Dijkstra's single source shortest path algorithm

// for a graph represented using adjacency matrix representation
void dijkstra(int graph[V][V], int src)
{
int dist[V]; // The output array. dist[i] will hold the shortest
// distance from src to i

bool sptSet[V]; // sptSet[i] will be true if vertex i is included in shortest

// path tree or shortest distance from src to i is finalized

// Initialize all distances as INFINITE and stpSet[] as false

for (int i = 0; i < V; i++)
dist[i] = INT_MAX, sptSet[i] = false;

// Distance of source vertex from itself is always 0

dist[src] = 0;

// Find shortest path for all vertices

for (int count = 0; count < V - 1; count++) {
// Pick the minimum distance vertex from the set of vertices not
// yet processed. u is always equal to src in the first iteration.
 int u = minDistance(dist, sptSet);

// Mark the picked vertex as processed

sptSet[u] = true;

// Update dist value of the adjacent vertices of the picked vertex.

for (int v = 0; v < V; v++)

// Update dist[v] only if is not in sptSet, there is an edge from

// u to v, and total weight of path from src to v through u is
// smaller than current value of dist[v]
if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX
&& dist[u] + graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}

// print the constructed distance array

printSolution(dist);
}

// driver program to test above function

int main()
{
/* Let us create the example graph discussed above */
int graph[V][V] = { { 0, 4, 0, 0, 0, 0, 0, 8, 0 },
{ 4, 0, 8, 0, 0, 0, 0, 11, 0 },
{ 0, 8, 0, 7, 0, 4, 0, 0, 2 },
{ 0, 0, 7, 0, 9, 14, 0, 0, 0 },
{ 0, 0, 0, 9, 0, 10, 0, 0, 0 },
{ 0, 0, 4, 14, 10, 0, 2, 0, 0 },
{ 0, 0, 0, 0, 0, 2, 0, 1, 6 },
{ 8, 11, 0, 0, 0, 0, 1, 0, 7 },
{ 0, 0, 2, 0, 0, 0, 6, 7, 0 } };

dijkstra(graph, 0);

return 0;
}
Output:

Ex:08 IMPLEMENT NETWORK FLOW ALGORITHM

Aim: To Implement Network Flow algorithm

Program code:
#include <iostream>
#include <limits.h>
#include <queue>
#include <string.h>
using namespace std;

// Number of vertices in given graph

#define V 6

/* Returns true if there is a path from source 's' to sink

't' in residual graph. Also fills parent[] to store the
path */
bool bfs(int rGraph[V][V], int s, int t, int parent[])
{
// Create a visited array and mark all vertices as not
// visited
bool visited[V];
memset(visited, 0, sizeof(visited));

// Create a queue, enqueue source vertex and mark source

// vertex as visited
queue<int> q;
 q.push(s);
visited[s] = true;
parent[s] = -1;

// Standard BFS Loop

while (!q.empty()) {
int u = q.front();
q.pop();

for (int v = 0; v < V; v++) {

if (visited[v] == false && rGraph[u][v] > 0) {
// If we find a connection to the sink node,
// then there is no point in BFS anymore We
// just have to set its parent and can return
// true
if (v == t) {
parent[v] = u;
return true;
}
q.push(v);
parent[v] = u;
visited[v] = true;
}
}
}

// We didn't reach sink in BFS starting from source, so

// return false
return false;
}

// Returns the maximum flow from s to t in the given graph

int fordFulkerson(int graph[V][V], int s, int t)
{
int u, v;

// Create a residual graph and fill the residual graph

// with given capacities in the original graph as
// residual capacities in residual graph
int rGraph[V]
[V]; // Residual graph where rGraph[i][j]
// indicates residual capacity of edge
// from i to j (if there is an edge. If
// rGraph[i][j] is 0, then there is not)
for (u = 0; u < V; u++)
for (v = 0; v < V; v++)
rGraph[u][v] = graph[u][v];
 int parent[V]; // This array is filled by BFS and to
// store path

int max_flow = 0; // There is no flow initially

// Augment the flow while tere is path from source to

// sink
while (bfs(rGraph, s, t, parent)) {
// Find minimum residual capacity of the edges along
// the path filled by BFS. Or we can say find the
// maximum flow through the path found.
int path_flow = INT_MAX;
for (v = t; v != s; v = parent[v]) {
u = parent[v];
path_flow = min(path_flow, rGraph[u][v]);
}

// update residual capacities of the edges and

// reverse edges along the path
for (v = t; v != s; v = parent[v]) {
u = parent[v];
rGraph[u][v] -= path_flow;
rGraph[v][u] += path_flow;
}

// Add path flow to overall flow

max_flow += path_flow;
}

// Return the overall flow

return max_flow;
}

// Driver program to test above functions

int main()
{
// Let us create a graph shown in the above example
int graph[V][V]
= { { 0, 16, 13, 0, 0, 0 }, { 0, 0, 10, 12, 0, 0 },
{ 0, 4, 0, 0, 14, 0 }, { 0, 0, 9, 0, 0, 20 },
{ 0, 0, 0, 7, 0, 4 }, { 0, 0, 0, 0, 0, 0 } };

cout << "The maximum possible flow is "

<< fordFulkerson(graph, 0, 5);

return 0;
}

Output:

Ex:09 IMPLEMENT APPROXIMATION ALGORITHMS

Aim: To Implement Approximation algorithms

Program code:
#include<iostream>
#include <list>
using namespace std;

// This class represents a undirected graph using adjacency list

class Graph
{
int V; // No. of vertices
list<int> *adj; // Pointer to an array containing adjacency lists
public:
Graph(int V); // Constructor
void addEdge(int v, int w); // function to add an edge to graph
void printVertexCover(); // prints vertex cover
};

Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}

void Graph::addEdge(int v, int w)

{
adj[v].push_back(w); // Add w to v’s list.
adj[w].push_back(v); // Since the graph is undirected
}

// The function to print vertex cover

void Graph::printVertexCover()
{
// Initialize all vertices as not visited.
bool visited[V];
for (int i=0; i<V; i++)
visited[i] = false;

list<int>::iterator i;

// Consider all edges one by one

for (int u=0; u<V; u++)
{
// An edge is only picked when both visited[u] and visited[v]
// are false
if (visited[u] == false)
{
// Go through all adjacents of u and pick the first not
// yet visited vertex (We are basically picking an edge
// (u, v) from remaining edges.
for (i= adj[u].begin(); i != adj[u].end(); ++i)
{
int v = *i;
if (visited[v] == false)
{
// Add the vertices (u, v) to the result set.
// We make the vertex u and v visited so that
// all edges from/to them would be ignored
visited[v] = true;
visited[u] = true;
break;
}
}
}
}

// Print the vertex cover

for (int i=0; i<V; i++)
if (visited[i])
 cout << i << " ";
}

// Driver program to test methods of graph class

int main()
{
// Create a graph given in the above diagram
Graph g(7);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(3, 4);
g.addEdge(4, 5);
g.addEdge(5, 6);

g.printVertexCover();

return 0;
}

Output: