Experiment 1
#include
using namespace std;
int factorial(int);
int main()
{
int result,n;
cout<<"Enter a non-negative number: ";
cin>>n;
result = factorial(n);
cout<<"-------------------------------"<1)
{
return n*factorial(n-1);
}
else
{
return 1;
}
Experiment 2
#include
using namespace std;
int main ()
{
int arr[100], st, mid, end, i, num, tgt;
cout << " Define the size of the array: " << endl;
cin >> num;
cout << " Enter the values in sorted array either ascending or descending order: " << endl;
for (i = 0; i < num; i++)
{
cout << " arr [" << i << "] = ";
cin >> arr[i];
}
st = 0;
end = num - 1;
cout << " Define a value to be searched from sorted array: " << endl;
cin >> tgt;
while ( st <= end)
{
mid = ( st + end ) / 2;
if (arr[mid] == tgt)
{
cout << " Element is found at index " << (mid + 1);
exit (0);
}
else if ( tgt > arr[mid])
{
st = mid + 1;
}
else if ( tgt < arr[mid])
{
end = mid - 1;
}
}
cout << " Number is not found. " << endl;
return 0;
}
Experiment 3
#include
using namespace std;
int partition(int arr[], int start, int end)
{
int pivot = arr[start];
int count = 0;
for (int i = start + 1; i <= end; i++) {
if (arr[i] <= pivot)
count++;
}
int pivotIndex = start + count;
swap(arr[pivotIndex], arr[start]);
int i = start, j = end;
while (i < pivotIndex && j > pivotIndex) {
while (arr[i] <= pivot) {
i++;
}
while (arr[j] > pivot) {
j--;
}
if (i < pivotIndex && j > pivotIndex) {
swap(arr[i++], arr[j--]);
}
}
return pivotIndex;
}
void quickSort(int arr[], int start, int end)
{
if (start >= end)
return;
int p = partition(arr, start, end);
quickSort(arr, start, p - 1);
quickSort(arr, p + 1, end);
}
int main()
{
int arr[] = { 9, 3, 4, 2, 1, 8 };
int n = 6;
quickSort(arr, 0, n - 1);
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}
Experiment 4
#include
#include
#include
#define V 5
int minKey(int key[], bool mstSet[])
{
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;
}
int printMST(int parent[], int graph[V][V])
{
printf("Edge \tWeight\n");
for (int i = 1; i < V; i++)
printf("%d - %d \t%d \n", parent[i], i, graph[i][parent[i]]);
}
void primMST(int graph[V][V])
{
int parent[V]; // Array to store constructed MST
int key[V]; // Key values used to pick minimum weight edge in cut
bool mstSet[V]; // To represent set of vertices included in MST
for (int i = 0; i < V; i++) // Initialize all keys as INFINITE
key[i] = INT_MAX, mstSet[i] = false;
key[0] = 0;
parent[0] = -1; // First node is always root of MST
for (int count = 0; count < V - 1; count++) // The MST will have V vertices
{
int u = minKey(key, mstSet);
mstSet[u] = true; // Add the picked vertex to the MST Set
for (int v = 0; v < V; v++)
if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v])
parent[v] = u, key[v] = graph[u][v];
}
printMST(parent, graph); // print the constructed MST
}
int main()
{
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 } };
primMST(graph); // Print the solution
return 0;
}
Experiment 5
#include
using namespace std;
class Graph
{a int V;
list *adj;
public:
Graph(int V);
void addEdge(int v, int w, int weight);
int findShortestPath(int s, int d);
int printShortestPath(int parent[], int s, int d);
};
Graph::Graph(int V)
{
this->V = V;
adj = new list[2*V];
}
void Graph::addEdge(int v, int w, int weight)
{ if (weight==2)
{
adj[v].push_back(v+V);
adj[v+V].push_back(w);
}
else
adj[v].push_back(w);
}
int Graph::printShortestPath(int parent[], int s, int d)
{
static int level = 0;
if (parent[s] == -1)
{
cout << "Shortest Path between " << s << " and "
<< d << " is " << s << " ";
return level;
}
printShortestPath(parent, parent[s], d);
level++;
if (s < V)
cout << s << " ";
return level;
}
int Graph::findShortestPath(int src, int dest)
{
bool *visited = new bool[2*V];
int *parent = new int[2*V];
for (int i = 0; i < 2*V; i++)
{
visited[i] = false;
parent[i] = -1;
}
list queue;
visited[src] = true;
queue.push_back(src);
list::iterator i;
while (!queue.empty())
{
int s = queue.front();
if (s == dest)
return printShortestPath(parent, s, dest);
queue.pop_front();
for (i = adj[s].begin(); i != adj[s].end(); ++i)
{
if (!visited[*i])
{
visited[*i] = true;
queue.push_back(*i);
parent[*i] = s;
}
}
}
}
int main() {
int V = 4;
Graph g(V);
g.addEdge(0, 1, 2);
g.addEdge(0, 2, 2);
g.addEdge(1, 2, 1);
g.addEdge(1, 3, 1);
g.addEdge(2, 0, 1);
g.addEdge(2, 3, 2);
g.addEdge(3, 3, 2);
int src = 0, dest = 3;
cout << "\nShortest Distance between " << src
<< " and " << dest << " is "
<< g.findShortestPath(src, dest);
return 0;}
Experiment 6
#include
using namespace std;
int max(int a, int b)
{ return (a > b) ? a : b; }
int knapSack(int W, int wt[], int val[], int n)
{
if (n == 0 || W == 0)
return 0;
if (wt[n - 1] > W)
return knapSack(W, wt, val, n - 1);
else
return max(
val[n - 1]
+ knapSack(W - wt[n - 1], wt, val, n - 1),
knapSack(W, wt, val, n - 1));
}
int main()
{
int profit[] = { 60, 100, 120 };
int weight[] = { 10, 20, 30 };
int W = 50;
int n = sizeof(profit) / sizeof(profit[0]);
cout<<"total profit of knapsack is:"<< knapSack(W, weight, profit, n);
return 0;
}
Experiment 8
#include
#define N 4
using namespace std;
void printSolution(int board[N][N])
{
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
if(board[i][j])
cout << "Q ";
else cout<<". ";
printf("\n");
}
}
bool isSafe(int board[N][N], int row, int col)
{
int i, j;
for (i = 0; i < col; i++)
if (board[row][i])
return false;
for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
if (board[i][j])
return false;
for (i = row, j = col; j >= 0 && i < N; i++, j--)
if (board[i][j])
return false;
return true;
}
bool solveNQUtil(int board[N][N], int col)
{
if (col >= N)
return true;
for (int i = 0; i < N; i++) {
if (isSafe(board, i, col)) {
board[i][col] = 1;
if (solveNQUtil(board, col + 1))
return true;
board[i][col] = 0;
}
}
return false;
}
bool solveNQ()
{
int board[N][N] = { { 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 } };
if (solveNQUtil(board, 0) == false) {
cout << "Solution does not exist";
return false;
}
printSolution(board);
return true;
}
int main()
{
solveNQ();
return 0;
}
Experiment 10
#include
using namespace std;
#define d 256
void search(char pat[], char txt[], int q)
{
int M = strlen(pat);
int N = strlen(txt);
int i, j;
int p = 0;
int t = 0;
int h = 1;
for (i = 0; i < M - 1; i++)
h = (h * d) % q;
for (i = 0; i < M; i++) {
p = (d * p + pat[i]) % q;
t = (d * t + txt[i]) % q;
}
for (i = 0; i <= N - M; i++) {
if (p == t) {
for (j = 0; j < M; j++) {
if (txt[i + j] != pat[j]) {
break;
}
}
if (j == M)
cout << "Pattern found at index " << i
<< endl;
}
if (i < N - M) {
t = (d * (t - txt[i] * h) + txt[i + M]) % q;
if (t < 0)
t = (t + q);
}
}
}
int main()
{
char txt[] = "GEEKS FOR GEEKS";
char pat[] = "GEEK";
int q = INT_MAX;
search(pat, txt, q);
return 0;
}
Experiment 9 (DFS/BFS)
#include <bits/stdc++.h>
#include<queue>
using namespace std;
int V = 5;
vector<int>adj[5];
bool visited [5];
void addEdge(vector<int>
adj[], int u, int v)
{
adj[u].push_back(v);
adj[v].push_back(u);
}
void bfs (int node)
{
queue<int> q;
q.push(node);
visited[node] = true;
cout<<node<<"
";
while(!q.empty())
{
int curr = q.front();
q.pop();
for (int child : adj [curr])
{
if(!visited[child])
{
q.push(child);
visited[child] = true;
cout<<child<<"
";
}
}
}
}
// Driver code
int main()
{
addEdge(adj, 0, 1);
addEdge(adj, 0, 4);
addEdge(adj, 1, 2);
addEdge(adj, 1, 3);
addEdge(adj, 1, 4);
addEdge(adj, 2, 3);
addEdge(adj, 3, 4);
cout<<"The breadth
first search of the given values is as follows: ";
bfs(0);
return 0;
Experiment 7 (Shortest path )
#include <iostream>
using namespace std;
int min(int, int);
int a[10][10],i,j,k,n;
int min(int a, int b)
{
if(a<b)
return a;
else
return b;
}
int main() {
cout<<"Enter n =
";
cin>>n;
cout<<"Enter matrix
= ";
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
cin>>a[i][j];
if(a[i][j]==0){
a[i][j]=999;}
}
}
for(k=1;k<=n;k++)
{ for(i=1;i<=n;i++)
{ for(j=1;j<=n;j++)
{
if(i==j){
a[i][j]=0;}
else
{
a[i][j]= min(a[i][j],
(a[i][k]+a[k][j]));}
}
}
}
cout<<"\n";
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
cout<<a[i][j]<<"
";}
cout<<"\n";}
return 0;
}
