Serial Index

No.
1 Implementation of recursive algorithm for calculating Fibonacci numbers
2 Implementation of binary search algorithm.
3 Implementation of merge sort algorithm.
4 Implementation of quick sort algorithm.
5 Implementation greedy method for machine scheduling.
6 Implementation greedy method for Container loading.
7 Implementation greedy method for knapsack problem.
8 Implementation Minimum-Cost spanning tree problem(prim’s algorithm)
9 Implementation Minimum-Cost spanning tree problem(Kruskal algorithm)
10 Implement of single source shortest path problem using greedy method
11 Implementation of dynamic programming approach for Longest Common
Subsequence.
12 Implementation of dynamic programming approach for shortest path
problem (using multistage graph).
13 Implementation of dynamic programming approach for knapsack
problem.
14 Implementation of Breadth First Search (BFS).
15 Implementation of Depth First Search (DFS).
Report-1 : Implementation of recursive algorithm for calculating Fibonacci
numbers.

#include <bits/stdc++.h>
using namespace std;

int recurse(int n)
{
if (n<= 1)
return n;
else
return recurse(n - 1) + recurse(n - 2);
}

int main()
{
int n;
cin>>n; //n is the number of fibonacci
cout<<"The Fibonacci Numbers : ";
for(int i=0; i<n; i++)
{
cout<< recurse(i)<<" ";
}
return 0;
}

Report-2: Implementation of binary search algorithm.

#include <bits/stdc++.h>
using namespace std;
#define issorted is_sorted([Link](), [Link]())
int binarySearch(vector<int>&ar,int l,int r,int x) //binary searching
{
while (l<=r)
{
int m =(r + l) / 2;
if (ar[m] < x)
l = m + 1;
else if(ar[m] > x)
r = m - 1;
else
return m+1;
}
return 0;
}

// Driver code
int main()
{
int n,m;
cin>>n>>m;//n is the array size and m is the search value
vector<int>arr(n);
for(int i=0; i<n; i++)// create array
cin>>arr[i];
if(!issorted)
sort([Link](), [Link]());

int result = binarySearch(arr, 0, n - 1,m);

(result)?cout << "Element is present at index " << result<<endl:

cout << "Element is not present in array";
return 0;
}

Report-3: Implementation of merge sort algorithm

#include <bits/stdc++.h>
using namespace std;
int ar[1000];
int b[1000];
void merge(int lt, int mid, int rt) //marge function
{
int i= lt, j=mid+1,k= lt;
while(i<=mid&&j<=rt)
{
if( ar[i]<= ar[j])
{
b[k]= ar[i];
k++;
i++;
}
else
{
b[k]= ar[j];
j++;
k++;
}
}

if(i>mid)
{
while(j<=rt)
{
b[k]= ar[j];
 k++;
j++;
}
}
else
{
while(i<=mid)
{
b[k]= ar[i];
k++;
i++;
}
}

for(int i= lt; i<=rt; i++)

{
ar[i]=b[i];
}

void mergeSort(int low, int high) // margesort function

{
if (low<high)
{
int mid =(low + high ) /2;
mergeSort(low, mid);
mergeSort(mid+1,high);
merge(low, mid, high);
}
}

// Driver code
int main()
{
ios::sync_with_stdio(0);
[Link](0);
[Link](0);
int n; //n is the array size
cin>>n;
for(int i=0; i<n; i++) //create array
cin>>ar[i];
mergeSort(0,n-1); //marge function call
for(int i=0; i<n; i++) //print after marge sort array
cout<<ar[i]<<" ";
cout<<endl;
return 0;
}
Report-4: Implementation of quick sort algorithm.

#include <bits/stdc++.h>
using namespace std;
int ar[1000];
int b[1000];
int partition(int st, int ed)
{
int pivot = ar[st];
int i = st, j = ed;
while (i<j)
{
while (ar[i]<=pivot)
{
i++;
}

while (ar[j] > pivot)

{
j--;
}

if (i < j)
{
int temp=ar[i];
ar[i]=ar[j];
ar[j]=temp;
}
}
int temp=ar[st];
ar[st]=ar[j];
ar[j]=temp;
return j;
}

void quickSort(int st, int ed) //quicksort function

{
if(st<ed)
{
int p= partition(st, ed);
quickSort(st, p);
quickSort(p+1,ed);
}
}

// Driver code
int main()
{
ios::sync_with_stdio(0);
[Link](0);
[Link](0);
int n; //n is the array size
cin>>n;
for(int i=0; i<n; i++) //create array
cin>>ar[i];
quickSort(0,n-1);
for(int i=0; i<n; i++) //print array after quicksort
cout<<ar[i]<<" ";
cout<<endl;
return 0;
}

Report-5: Implementation greedy method for machine scheduling

#include <bits/stdc++.h>
using namespace std;
vector<int>vis;
vector<pair<int,int> >pr;

int machine()
{
vis.push_back(pr[0].second);
int ans=1,i=1;
while(i!=[Link]())
{
int j=0,p=false;;
while(j!=[Link]())
{
if(pr[i].first>=vis[j])
{
vis[j]=pr[i].second;
p=true;
break;
}
j++;
}
if(!p)
{
ans+=1;
vis.push_back(pr[i].second);
}
i++;
}
return ans;
}

void optimal()
{
int n; // n is the number of work
cin>>n;

for(int i=0; i<n; i++) //create work array

{
int a,b; //a is the start time,b isthe end
cin>>a>>b;
pr.push_back({a,b});
}

sort([Link](),[Link]());
int ans=machine();
cout<<"The Machine number is : ";
cout<<ans<<endl;
}

int main()
{
ios::sync_with_stdio(0);
[Link](0);
[Link](0);
optimal();
return 0;
}

Report-6: Implementation greedy method for Container loading.

#include <bits/stdc++.h>
using namespace std;
vector<int> v;

int containerloading(int n, int h)

{
int i=0,sol=0;
while(i!=n&&v[i]<=h)
{
sol++;
h-=v[i];
i++;
}
return sol;
}
void solution()
{
//n is the number of container
//m is capacity
int n, m;
cin>>n>>m;
for(int i=0; i<n; i++)
{
int a;
cin>>a;
v.push_back(a);
}
if(!is_sorted([Link](),[Link]()))
sort([Link](),[Link]());
int ans=containerloading(n, m);
cout<<ans<<endl;
}

int main()
{
ios::sync_with_stdio(0);
[Link](0);
[Link](0);
solution();
return 0;
}

Report-7: Implementation greedy method for knapsack problem.

#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int> >pw;
float ans=0.0;

void knapsack(int n,int h)

{
vector<pair<float,int>> pwf;
for(int i = 0; i < n; i++)
{
pwf.push_back({(float)pw[i].first/pw[i].second, i});
}
sort([Link](),[Link]()); // reverse sort pdf
int i=0,ind=pwf[0].second;
while(i<n&&pw[ind].second<=h)
{
h-= pw[ind].second;
ans+= pw[ind].first;
 i++;
ind = pwf[i].second;
}
if(i<n)
ans+=pw[ind].first*(float(h)/float(pw[ind].second));
}

void optimal()
{
int n,m; //n is the number of product and array
cin>>n>>m; //m is capacity
for(int i=0; i<n; i++)
{
int a,b; // a is the product value
cin>>a>>b; // b is the product weight
pw.push_back({a,b});
}

knapsack(n,m);
cout<<"The optimal value is ";
cout<<ans<<endl;
}

int main()
{
ios::sync_with_stdio(0);
[Link](0);
[Link](0);
optimal();
return 0;
}

Report-8: Implementation Minimum-Cost spanning tree problem(prim’s algorithm)

#include<bits/stdc++.h>
using namespace std;

// Function to find the MST using adjacency cost matrix representation

void prims(vector<vector<int>> &grp,int n)
{
vector<int> near(n,0), key(n,999);
vector<bool> vis(n,false);

key[0] =0; // Include first vertex in MST by setting its key vaue to 0.
// First node is always root of MST

// The MST will have maximum V-1 vertices

 for (int i= 0; i< n- 1; i++)
{
// Finding the minimum key vertex from the
//set of vertices not yet included in MST
int mn = 999, u; // 999 represents an Infinite value
for (int j= 0; j < n; j++)
{
if (!vis[j] && key[j] < mn)
{
// vertex should not be visited
mn = key[j];
u = j;
}
}
vis[u] = true; // Add the minimum key vertex to the MST
// Update key and parent arrays
for (int k = 0; k < n; k++)
{
if (grp[u][k] && !vis[k] && grp[u][k] < key[k])
{
near[k] = u;
key[k] = grp[u][k];
}
}
}

// print the final MST

int minCost=0;
cout<<"Edge \tWeight\n";
for (int i = 1; i< n; i++)
{
cout<<near[i]<<" - "<<i<<" \t"<<grp[i][near[i]]<<" \n";
minCost+=grp[i][near[i]];
}
cout<<"Total cost is "<<minCost<<endl;
}

// main function
int main()
{
int m;// Number of vertices in the graph
cin>>m;
vector<vector<int>> adj(m,vector<int> (m));
for (int i=0; i<m; i++)
{
for(int j=0; j<m; j++)
{
cin>>adj[i][j];
 }
}
prims(adj, m);

return 0;
}

Report-9: Implementation Minimum-Cost spanning tree problem(Kruskal algorithm)

#include <bits/stdc++.h>
using namespace std;
vector<pair<int,pair<int,int>>> edg;
vector<int> par,vis;

int find(int p)
{
if (par[p] == -1)
return p;
return par[p]=find(par[p]);
}

void Union(int x, int y)

{
int s1 = find(x);
int s2= find(y);
if(s1!=s2)
{
if (vis[s1] < vis[s2])
{
par[s1] = s2;
}
else if(vis[s1]>vis[s2])
{
par[s2] = s1;
}
else
{
par[s2] = s1;
vis[s1] += 1;
}
}
}

void kruskals(int n)
{
 for(int i=0;i<n;i++) // Initialize the par and vis
{
par.push_back(-1);
vis.push_back(1);
}

int ans = 0;

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

{
int w = edg[i].first;
int x = edg[i].[Link];
int y = edg[i].[Link];

// Take this edge in MST if it does

// not forms a cycle
if (find(x) != find(y))
{
ans += w;
Union(x,y);
cout << x << " -- " << y << " == " << w<< endl;
}
}
cout << "Minimum Cost Spanning Tree: " << ans;
}

// Driver code
int main()
{
int n;
cin>>n; // n is the number of edges
for(int i=0; i<n; i++)
{
int a,b,c;
cin>>a>>b>>c; // a is node,b is adjacent node and c is edge
edg.push_back({c, {a, b}});
}
sort([Link](),[Link]());
kruskals(n);

return 0;
}

Report-10: Implement of single source shortest path problem using greedy method

#include <bits/stdc++.h>
using namespace std;
void shortpth(vector<vector<int>> &grp, int src,int lt,int n)
{
vector<int> dist(n);
vector<bool> S(n,flase);
// Initialize all distances as source vertex value and stpSet[] as
// false
for (int i = 0; i< n; i++)
{
dist[i] = grp[src][i];
}
// Distance of source vertex from itself is always 0
dist[src] = 0;

// Find shortest path for all vertices

for (int i= 0; i<n-1; i++)
{
// A utility function to find the vertex with minimum
int mn = INT_MAX, u;
for (int k = 0; k< n; k++)
{
if (S[k] == false && dist[k] <= mn)
mn = dist[k],
u = k;
}
// Mark the picked vertex as processed
S[u] = true;
for (int j= 0; j<n ; j++)
{
if(!S[j] && dist[u] != INT_MAX && dist[u] + grp[u][j] < dist[j])
dist[j] = dist[u] + grp[u][j];
}
}

cout<<endl;
cout << "Vertex \t Distance from Source : ";
cout << dist[lt-1] << endl;
}

// driver's code
int main()
{
int m,p,ed;//m=vertex num,p=source,en=last vertex
cin>>m>>p>>ed;
/* Let us create the example graph discussed above */
vector<vector<int>> v(m,vector<int> (m));
for(int i=0; i<m; i++)
{
 for(int j=0; j<m; j++)
{
cin>>v[i][j];
}
}
// Function call
shortpth(v, p-1, ed, m);
return 0;
}

Report-11: Implementation of dynamic programming approach for Longest Common

Subsequence

#include <iostream>
#include <cstring>
using namespace std;
int LCS(string str1, string str2)
{
int m = [Link]();
int n = [Link]();
int c[m + 1][n + 1];
for (int i = 0; i <= m; i++)
c[i][0] = 0;
for (int j = 0; j <= n; j++)
c[0][j] = 0;
for (int i = 1; i <= m; i++)
{
for (int j = 1; j <= n; j++)
{
if (str1[i - 1] == str2[j - 1])
c[i][j] = c[i - 1][j - 1] + 1;
else
c[i][j] = max(c[i][j - 1], c[i - 1][j]);
}
}
return c[m][n];
}
int main()
{
string str1, str2;
cout << "Enter string 1: ";
cin >> str1;
cout << "Enter string 2: ";
cin >> str2;
int length = LCS(str1, str2);
cout << "Length of the Longest Common Subsequence: " << length << endl;
return 0;
}

Report-12: Implementation of dynamic programming approach for shortest path

problem (using multistage graph).

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;
const int INF = INT_MAX; // Infinity value
struct Edge {
int source;
int destination;
int weight;
Edge(int src, int dest, int w) : source(src), destination(dest), weight(w) {}
};
int shortestPathMultistage(const vector<Edge>& edges, int n, int source, int destination)
{
vector<int> dp(n, INF); // DP array to store shortest path lengths
dp[source] = 0; // Distance from source to itself is 0
// Sort edges based on source vertex
vector<Edge> sortedEdges = edges;
sort([Link](), [Link](), [](const Edge& a, const Edge& b) {
return [Link] < [Link];
});
// Iterate through the stages in a top-down manner
for (int k = source + 1; k < n; k++) {
// Iterate through all edges in the sorted list
for (const Edge& edge : sortedEdges) {
int u = [Link];
int v = [Link];
int w = [Link];
// Check if the edge belongs to stage k
if (u == k) {
// Calculate potential cost of the path from source to u and then to v
int potentialCost = dp[u] + w;
// Update dp[v] if the potential cost is smaller
if (potentialCost < dp[v]) {
dp[v] = potentialCost;
}
}
}
}
return dp[destination]; // Shortest path length from source to destination
}
int main() {
 int n; // Number of vertices in the multistage graph
cout << "Enter the number of vertices: ";
cin >> n;
int m; // Number of edges
cout << "Enter the number of edges: ";
cin >> m;
vector<Edge> edges;
cout << "Enter the edges (source destination weight):\n";
for (int i = 0; i < m; i++) {
int source, destination, weight;
cin >> source >> destination >> weight;
edges.emplace_back(source, destination, weight);
}
int source, destination;
cout << "Enter the source vertex: ";
cin >> source;
cout << "Enter the destination vertex: ";
cin >> destination;
int shortestPathLength = shortestPathMultistage(edges, n, source, destination);
if (shortestPathLength == INF) {
cout << "No path exists from source to destination.\n";
} else {
cout << "Shortest path length from source to destination: " << shortestPathLength
<< endl;
}
return 0;
}

Report-13: Implementation of dynamic programming approach for knapsack problem

#include <iostream>
#include <vector>
#include <algorithm>
struct Item
{
int value;
int weight;
};
int knapsack(int capacity, const std::vector<Item>& items)
{
int numItems = [Link]();
std::vector<std::vector<int>> dp(numItems + 1, std::vector<int>(capacity + 1, 0));
for (int i = 1; i <= numItems; i++)
{
for (int j = 1; j <= capacity; j++)
{
if (items[i - 1].weight <= j)
 {
dp[i][j] = std::max(dp[i - 1][j], items[i - 1].value + dp[i - 1][j - items[i -
1].weight]);
}
else
{
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[numItems][capacity];
}
int main()
{
int capacity;
std::cout << "Enter the knapsack capacity: ";
std::cin >> capacity;
int numItems;
std::cout << "Enter the number of items: ";
std::cin >> numItems;
std::vector<Item> items(numItems);
std::cout << "Enter the values and weights of the items:" << std::endl;
for (int i = 0; i < numItems; i++)
{
std::cout << "Item " << i + 1 << ":" << std::endl;
std::cout << "Value: ";
std::cin >> items[i].value;
std::cout << "Weight: ";
std::cin >> items[i].weight;
}
int maxProfit = knapsack(capacity, items);
std::cout << "Maximum Profit: " << maxProfit << std::endl;
return 0;
}

Report-14: Implementation of Breadth First Search (BFS).

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

void bfs(vector<vector<int>> &adj, int st,vector<bool> &vis)

{
queue<int> q;
vis[st] = true;
[Link](st);
while (![Link]())
 {
int ct= [Link]();
[Link]();
cout << ct << " ";
for (int u : adj[ct])
{

if (!vis[u])
{
vis[u] = true;
[Link](u);
}
}
}
}

int main()
{
// n is the Number of vertices in the graph
int n,m;
cin>>n>>m;
// m is the starting path
vector<vector<int> > adj(n);
for(int i=0; i<n; i++)
{
int x,y;
cin>>x>>y; // x is node ,y is adjacent node
adj[x].push_back(y);
}
vector<bool> vis(n,false);
bfs(adj,m, vis);
return 0;
}

Report-15: Implementation of Depth First Search (DFS).

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
vector<int> stt;
void dfs(vector<vector<int>>& adj, int st,vector<bool>&vis)
{
vis[st] = true;
stt.push_back(st);
for (int u : adj[st])
{
if (!vis[u])
 {
dfs(adj,u, vis);
}
}
}

void solvent()
{
// Number of vertices in the graph
int n,m;
cin>>n>>m;
// Adjacency list representation of the graph
vector<vector<int> > adj(n);

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

{
int x, y;
cin>>x>>y; // x is node ,y is adjacent node
adj[x].push_back(y);
}

vector<bool> vis(n,false);
dfs(adj,m,vis);
for(int i=0; i<[Link](); i++)
cout<<stt[i]<<" ";
cout<<endl;
}

int main()
{
solvent();
return 0;
}