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 of shortest path using greedy method.
9 Implementation of dynamic programming approach for Longest Common
Subsequence.
10 Implementation of dynamic programming approach for shortest path problem (using
multistage graph).
11 Implementation of dynamic programming approach for knapsack problem.
12 Implementation of Breadth First Search (BFS).
13 Implementation of Depth First Search (DFS).
1. Problem Name: Implementation of recursive algorithm for calculating Fibonacci
numbers.
Source Code:
#include<iostream>
using namespace std;
int fibonacci(int n) {
// Base cases: Fibonacci(0) = 0, Fibonacci(1) = 1
if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
}
// Recursive case: Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2)
return fibonacci(n - 1) + fibonacci(n - 2);
}
int main() {
int num;
cout << "Enter the number of Fibonacci numbers to generate: ";
cin >> num;
cout << "Fibonacci Series: ";
for (int i = 0; i < num; ++i) {
cout << fibonacci(i) << " ";
}
return 0;
}

Input Sample:
Enter the number of Fibonacci numbers to generate: 5

Output Sample:
Fibonacci Series: 0 1 1 2 3
2. Problem Name: Implementation of binary search algorithm.
Source Code:
#include<bits/stdc++.h>
using namespace std;
int binsearch (int a[],int left,int right,int x)
{
if(right>=left)
{
int mid=(left+right)/2;
if (a[mid]==x)
return mid;
if(a[mid]>x)
return binsearch (a,left,mid-1,x);
else
return binsearch (a,mid+1,right,x);
}
return -1;
}
int main()
{
int a[1000]={0},n,x;
cout<<"How many numbers are input: ";
cin>>n;
cout<<"Enter these value: ";
for(int i=0;i<n;i++)
{
cin>>a[i];
}
cout<<"Enter the searching item: ";
cin>>x;
sort(a,a+n);
int ans=binsearch (a,0,n-1,x);
if(ans==-1)
cout<<"Item is not found"<<endl;
else
cout<<"Position of the item is "<<ans+1<<endl;
return 0;
}

Input Sample:
How many numbers are input: 5
Enter these value: 2 5 3 0 2
Enter the searching item: 0
Position of the item is 1
Output Sample:
Position of the item is 1
3. Problem Name: Implementation of merge sort algorithm.
Source Code:
#include<iostream>
using namespace std;
int ar[1000];
int merge(int ar[],int start ,int mid, int en);
int divide(int a[],int start,int en)
{
int mid;
if(en<=start)
return 0;
else {
mid=(start+en)/2;
divide(ar,start,mid);
divide(ar,mid+1,en);
merge(ar,start,mid,en);
}
}
int merge(int ar[],int start, int mid, int en)
{
int i,j,k,index=0,temp[1000];
i=start;
j=mid+1;
while(i<=mid && j<=en)
{
if(ar[i]<ar[j])
temp[index++]=ar[i++];
else
temp[index++]=ar[j++];
}
while(i<=mid)
{
temp[index++]=ar[i++];
}
while(j<=en)
{
temp[index++]=ar[j++];
}
for(i=start,k=0;i<=en;i++)
{
ar[i]=temp[k++];
}
}
int main()
{
int n;
 cout<<"Enter the number of elements: ";
cin>>n;
cout<<"Enter the elements: "<<endl;
for(int i=1;i<=n;i++)
cin>>ar[i];
divide(ar,1,n);
cout<<"Sorted elements: ";
for(int i=1;i<=n;i++)
cout<<ar[i]<<" ";
cout<<endl;
return 0;
}

Input Sample:
Enter the number of elements: 5
Enter the elements:
54 23 65 12 43
Sorted elements: 12 23 43 54 65

Output Sample:
Sorted elements: 12 23 43 54 65

4. Problem Name: Implementation of quick sort algorithm.

Source Code:
#include <iostream>
using namespace std;

int partition(int arr[], int left, int right) {

int pivot = arr[right];
int store = left - 1;

for (int i = left; i < right; i++) {

if (arr[i] < pivot) {
swap(arr[i], arr[store + 1]);
store++;
}
}

swap(arr[right], arr[store + 1]);

return store + 1;
}

void quickSort(int arr[], int left, int right) {

if (left < right) {
int pivot = partition(arr, left, right);
quickSort(arr, left, pivot - 1);
 quickSort(arr, pivot + 1, right);
}
}

int main() {
int size;
cout << "Enter the size of the array: ";
cin >> size;

int arr[size];
cout << "Enter the elements of the array: ";
for (int i = 0; i < size; i++) {
cin >> arr[i];
}

cout << "Original array: ";

for (int i = 0; i < size; i++) {
cout << arr[i] << " ";
}
cout << endl;

quickSort(arr, 0, size - 1);

cout << "Sorted array: ";

for (int i = 0; i < size; i++) {
cout << arr[i] << " ";
}
cout << endl;

return 0;
}

Input Sample:
Enter the size of the array: 5
Enter the elements of the array: 23 54 17 98 34

Output Sample:
Original array: 23 54 17 98 34
Sorted array: 17 23 34 54 98

5. Problem Name: Implementation greedy method for machine scheduling.

Source Code:
#include <iostream>

using namespace std;

class Machine {
public:
int machineId;
int startTime;
int endTime;
};

int main() {
const int NUM_MACHINES = 7;
Machine machines[NUM_MACHINES];

// Input machine details

for (int i = 0; i < NUM_MACHINES; i++) {
cout << "Enter details for Machine " << (i + 1) << ":\n";
machines[i].machineId = i + 1;

cout << "Start Time: ";

cin >> machines[i].startTime;

cout << "End Time: ";

cin >> machines[i].endTime;

cout << "\n";

}

// Sort machines based on start time

for (int i = 0; i < NUM_MACHINES - 1; i++) {
for (int j = 0; j < NUM_MACHINES - i - 1; j++) {
if (machines[j].startTime > machines[j + 1].startTime) {
Machine temp = machines[j];
machines[j] = machines[j + 1];
machines[j + 1] = temp;
}
}
}

// Display scheduled machines

cout << "\nScheduled Machines:\n";
for (int i = 0; i < NUM_MACHINES; i++) {
cout << "Machine " << machines[i].machineId << ": ";
cout << "Start Time: " << machines[i].startTime << ", ";
cout << "End Time: " << machines[i].endTime << "\n";
}

return 0;
}
 Input Sample:
Enter details for Machine 1:
Start Time: 2
End Time: 5

Enter details for Machine 2:

Start Time: 3
End Time: 4

Enter details for Machine 3:

Start Time: 2
End Time: 3

Enter details for Machine 4:

Start Time: 1
End Time: 4

Enter details for Machine 5:

Start Time: 4
End Time: 6

Enter details for Machine 6:

Start Time: 1
End Time: 0

Enter details for Machine 7:

Start Time: 2
End Time: 4

Output Sample:
Scheduled Machines:
Machine 4: Start Time: 1, End Time: 4
Machine 6: Start Time: 1, End Time: 0
Machine 1: Start Time: 2, End Time: 5
Machine 3: Start Time: 2, End Time: 3
Machine 7: Start Time: 2, End Time: 4
Machine 2: Start Time: 3, End Time: 4
Machine 5: Start Time: 4, End Time: 6

6. Problem Name: Implementation greedy method for Container loading.

Source Code:
#include <iostream>
#include <vector>
#include <algorithm>

struct Item {
 int id;
int weight;
};

bool compareItems(const Item& item1, const Item& item2) {

return [Link] > [Link];
}

std::vector<std::vector<int>> loadContainers(const std::vector<Item>& items, int

containerCapacity) {
std::vector<std::vector<int>> containers;
std::vector<int> currentContainer;

int currentWeight = 0;
for (const Item& item : items) {
if (currentWeight + [Link] <= containerCapacity) {
currentContainer.push_back([Link]);
currentWeight += [Link];
} else {
containers.push_back(currentContainer);
[Link]();
currentContainer.push_back([Link]);
currentWeight = [Link];
}
}

if (![Link]()) {
containers.push_back(currentContainer);
}

return containers;
}

int main() {
int numItems;
std::cout << "Enter the number of items: ";
std::cin >> numItems;

std::vector<Item> items(numItems);
std::cout << "Enter the details for each item (id, weight):" << std::endl;
for (int i = 0; i < numItems; i++) {
std::cout << "Item " << i + 1 << ": ";
std::cin >> items[i].id >> items[i].weight;
}

int containerCapacity;
 std::cout << "Enter the capacity of each container: ";
std::cin >> containerCapacity;

// Sort the items in descending order of weights

std::sort([Link](), [Link](), compareItems);

std::vector<std::vector<int>> containers = loadContainers(items, containerCapacity);

std::cout << "Container Loading:" << std::endl;

for (int i = 0; i < [Link](); i++) {
std::cout << "Container " << i + 1 << ": ";
for (int itemId : containers[i]) {
std::cout << itemId << " ";
}
std::cout << std::endl;
}

return 0;
}

Input Sample:
Enter the number of items: 5
Enter the details for each item (id, weight):
Item 1: 1 15
Item 2: 2 10
Item 3: 3 35
Item 4: 4 25
Item 5: 5 5
Enter the capacity of each container: 35
Output Sample:
Container Loading:
Container 1: 3
Container 2: 4
Container 3: 1 2 5

7. Problem Name: Implementation greedy method for knapsack problem.

Source Code:
#include <iostream>
#include <vector>
#include <algorithm>

struct Item {
int id;
int value;
int weight;
double valuePerWeight;
};

bool compareItems(const Item& item1, const Item& item2) {

return [Link] > [Link];
}

double knapsackGreedy(std::vector<Item>& items, int capacity) {

double totalValue = 0.0;
int currentWeight = 0;

for (Item& item : items) {

if (currentWeight + [Link] <= capacity) {
currentWeight += [Link];
totalValue += [Link];
} else {
double remainingCapacity = capacity - currentWeight;
totalValue += (remainingCapacity / [Link]) * [Link];
break;
}
}

return totalValue;
}

int main() {
int numItems;
std::cout << "Enter the number of items: ";
std::cin >> numItems;

std::vector<Item> items(numItems);
std::cout << "Enter the details for each item (id, value, weight):" << std::endl;
for (int i = 0; i < numItems; i++) {
std::cout << "Item " << i + 1 << ": ";
std::cin >> items[i].id >> items[i].value >> items[i].weight;
items[i].valuePerWeight = static_cast<double>(items[i].value) / items[i].weight;
}

int knapsackCapacity;
std::cout << "Enter the capacity of the knapsack: ";
std::cin >> knapsackCapacity;

std::sort([Link](), [Link](), compareItems);

double totalValue = knapsackGreedy(items, knapsackCapacity);

std::cout << "Total value obtained: " << totalValue << std::endl;
 return 0;
}

Input Sample:
Enter the number of items: 3
Enter the details for each item (id, value, weight):
Item 1: 1 5 60
Item 2: 2 4 55
Item 3: 3 49 65
Enter the capacity of the knapsack: 100

Output Sample:
Total value obtained: 51.9167
8. Problem Name: Implementation of shortest path using greedy method.
Source Code:
#include <iostream>
#include <vector>
#include <queue>
#include <limits>

#define INF std::numeric_limits<int>::max()

struct Edge {
int destination;
int weight;
};

typedef std::vector<std::vector<Edge>> Graph;

std::vector<int> dijkstra(const Graph& graph, int source) {

int numVertices = [Link]();
std::vector<int> distances(numVertices, INF);
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>,
std::greater<std::pair<int, int>>> pq;

distances[source] = 0;
[Link](std::make_pair(0, source));

while (![Link]()) {
int u = [Link]().second;
[Link]();

for (const Edge& edge : graph[u]) {

int v = [Link];
int weight = [Link];
 if (distances[u] + weight < distances[v]) {
distances[v] = distances[u] + weight;
[Link](std::make_pair(distances[v], v));
}
}
}

return distances;
}

int main() {
int numVertices, numEdges;
std::cout << "Enter the number of vertices: ";
std::cin >> numVertices;
std::cout << "Enter the number of edges: ";
std::cin >> numEdges;

Graph graph(numVertices);

std::cout << "Enter the edges (source, destination, weight):" << std::endl;
for (int i = 0; i < numEdges; i++) {
int source, destination, weight;
std::cin >> source >> destination >> weight;

graph[source].push_back({destination, weight});
}

int source;
std::cout << "Enter the source vertex: ";
std::cin >> source;

std::vector<int> distances = dijkstra(graph, source);

std::cout << "Shortest distances from the source vertex " << source << ":" << std::endl;
for (int i = 0; i < numVertices; i++) {
std::cout << "Vertex " << i << ": ";
if (distances[i] == INF) {
std::cout << "Not reachable" << std::endl;
} else {
std::cout << distances[i] << std::endl;
}
}

return 0;
}
 Input Sample:
Enter the number of vertices: 5
Enter the number of edges: 7
Enter the edges (source, destination, weight):
014
021
131
145
212
231
343
Enter the source vertex: 0
Output Sample:
Shortest distances from the source vertex 0:
Vertex 0: 0
Vertex 1: 3
Vertex 2: 1
Vertex 3: 2
Vertex 4: 5

9. Problem Name: Implementation of dynamic programming approach for Longest

Common Subsequence.
Source Code:
#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;
}

Input Sample:
Enter string 1: ashikur
Enter string 2: shakib

Output Sample:
Length of the Longest Common Subsequence: 3

10. Problem Name: Implementation of dynamic programming approach for shortest path
problem (using multistage graph).
Source Code:
#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;
}

Input Sample:
Enter the number of vertices: 9
Enter the number of edges: 14
Enter the edges (source destination weight):
012
024
131
143
232
241
353
362
452
463
574
583
671
682
Enter the source vertex: 0
Enter the destination vertex: 8
Output Sample:
Shortest path length from source to destination: 9
11. Problem Name: Implementation of dynamic programming approach for knapsack
problem.
Source Code:
#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;
}

Input Sample:
Enter the knapsack capacity: 5
Enter the number of items: 4
Enter the values and weights of the items:
Item 1:
Value: 4
Weight: 3
Item 2:
Value: 3
Weight: 2
Item 3:
Value: 6
Weight: 5
Item 4:
Value: 5
Weight: 4

Output Sample:
Maximum Profit: 7

12. Problem Name: Implementation of Breadth First Search (BFS).

Source Code:
#include<iostream>
using namespace std;

int adj[100][100]={0};
int visited[100]={0};
int queue[100];
int front = -1, rear = -1;

void BFS(int start, int numV)

{
visited[start] = 1;
rear=rear+1;
queue[rear] = start;
 while(front != rear)
{
front=front+1;
int current = queue[front];
cout<<current;

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

{
if(adj[current][i] == 1 && visited[i] == 0)
{
visited[i] = 1;
rear=rear+1;
queue[rear] = i;
}
}
}
}

int main()
{
int V, E;
cout<<"Enter the number of vertices : ";
cin>>V;
cout<<"Enter the number of edges: ";
cin>>E;

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

{
int u, v;
cout<<"Enter edge "<<i+1<<": ";
cin>>u>>v;
adj[u][v] = 1;
adj[v][u] = 1;
}
int start;
cout<<"Enter the starting vertex: ";
cin>>start;

cout<<"BFS Traversal : ";

BFS(start,V);
return 0;
}

Input Sample:
Enter the number of vertices : 6
 Enter the number of edges: 8
Enter edge 1: 0
1
Enter edge 2: 1 2
Enter edge 3: 0 2
Enter edge 4: 0 4
Enter edge 5: 1 4
Enter edge 6: 4 3
Enter edge 7: 5 4
Enter edge 8: 2 3
Enter the starting vertex: 0

Output Sample:
BFS Traversal : 012435

13. Problem Name: Implementation of Depth First Search (DFS).

Source Code:
#include <iostream>
using namespace std;

int graph[100][100]={0};
int visited[100]={0};
int start,i;
int N;

void DFS(int node)

{
visited[node] = 1;
cout<<node;

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

{
if (graph[node][i] == 1 && visited[i] == 0)
{
DFS(i);
}
}
}

int main()
{
int E,u,v;

cout<<"Enter number of nodes: ";

cin>>N;
 cout<<"Enter number of Edges: ";
cin>>E;

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

{
cout<<"Enter edge "<<i+1<<": ";
cin>>u>>v;
graph[u][v] = 1;
graph[v][u] = 1;
}

cout<<"Enter starting node: ";

cin>>start;

DFS(start);

return 0;
}

Input Sample:
Enter the number of vertices: 6
Enter the number of edges: 8
Enter the edges (source, destination):
01
02
04
12
14
23
34
45
Enter the starting vertex for DFS: 0

Output Sample:
Depth-First Traversal starting from vertex 0: 0 1 2 3 4 5