13.

Given a (directed/undirected) graph, design an algorithm and implement it using a program

to find if a path exists between two given vertices or not. (Hint: use DFS)

Input Format:
Input will be the graph in the form of adjacency matrix or adjacency list.
Source vertex number and destination vertex number is also provided as an input.

Output Format:
Output will be 'Yes Path Exists' if path exists, otherwise print 'No Such Path Exists'.

Sample I/O Problem I:

Input: Output:
5 Yes Path Exists
01100
10111
11010
01101
01010
15

#include<stdio.h>
#define MAX 100
int adj[MAX][MAX];
int visited[MAX];
int n;
void create_graph();
void DFS(int v, int destination);
int main() {
int source, destination;
printf("Enter number of vertices : "); scanf("%d", &n);
create_graph();
printf("Enter source vertex : "); scanf("%d", &source);
printf("Enter destination vertex : "); scanf("%d", &destination);
DFS(source, destination);
if (visited[destination])
printf("Yes Path Exists\n");
else printf("No Such Path Exists\n");
return 0;
}
void DFS(int v, int destination) { int i;
visited[v] = 1;
for(i = 0; i < n; i++) {
if(adj[v][i] == 1 && visited[i] == 0)
DFS(i, destination);
}}
void create_graph() {
int i, max_edges, origin, destin;
printf("Enter adjacency matrix : \n");
for(i = 0; i < n; i++)
for(int j = 0; j < n; j++) { scanf("%d", &adj[i][j]); }
}
 14. Given a graph, design an algorithm and implement it using a program to find if a graph is
bipartite or not. (Hint: use BFS)

Input Format:
Input will be the graph in the form of adjacency matrix or adjacency list.

Output Format:
Output will be 'Yes Bipartite' if graph is bipartite, otherwise print 'Not Bipartite'.

Sample I/O Problem II:

Input: Output:
5 Not Bipartite
01100
10111
11010
01101
01010

#include <stdio.h>
#define MAX 100

int adj[MAX][MAX], color[MAX];

int n;

void create_graph();
int isBipartite(int v);

int main() {
printf("Enter number of vertices : ");
scanf("%d", &n);
create_graph();
int result = isBipartite(0);
if (result)
printf("Yes Bipartite\n");
else
printf("Not Bipartite\n");
return 0;
}

int isBipartite(int v) {
int i;
for (i = 0; i < n; i++)
color[i] = -1;

color[v] = 1;

int queue[MAX], front = -1, rear = -1;

queue[++rear] = v;

while (front != rear) {

v = queue[++front];

if (adj[v][v])
return 0;
 for (i = 0; i < n; i++) {
if (adj[v][i] && color[i] == -1) {
color[i] = 1 - color[v];
queue[++rear] = i;
} else if (adj[v][i] && color[i] == color[v])
return 0;
}
}
return 1;
}

void create_graph() {
int i, j;

printf("Enter adjacency matrix : \n");

for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
scanf("%d", &adj[i][j]);
}
}
}
 15. Given a directed graph, design an algorithm and implement it using a program to find
whether cycle exists in the graph or not.

Input Format:
Input will be the graph in the form of adjacency matrix or adjacency list.

Output Format:
Output will be 'Yes Cycle Exists' if cycle exists otherwise print 'No Cycle Exists'.

Sample I/O Problem III:

Input: Output:
5 No Cycle Exists
01100
00011
01010
00001
00000

#include <stdio.h>
#define MAX_NODES 100
int isCycle( int graph[MAX_NODES][MAX_NODES], int visited[MAX_NODES], int
recStack[MAX_NODES], int node, int numNodes ) {
if (!visited[node]) {
visited[node] = 1, recStack[node] = 1;
for (int neighbor = 0; neighbor < numNodes; ++neighbor) {
if (graph[node][neighbor] == 1) {
if (!visited[neighbor] && isCycle(graph, visited, recStack, neighbor, numNodes)) {
return 1; // Cycle found
} else if (recStack[neighbor]) {
return 1; // Cycle found
} } } }
recStack[node] = 0;
return 0; } // No cycle found
int hasCycle(int graph[MAX_NODES][MAX_NODES], int numNodes) {
int visited[MAX_NODES] = {0};
int recStack[MAX_NODES] = {0};
for (int node = 0; node < numNodes; ++node) {
if (!visited[node]) {
if (isCycle(graph, visited, recStack, node, numNodes)) {
return 1; } } // Cycle found
} return 0; } // No cycle found
int main() {
int numNodes;
printf("Enter the number of nodes: "); scanf("%d", &numNodes);
int adjacencyMatrix[MAX_NODES][MAX_NODES];
printf("Enter the adjacency matrix:\n");
for (int i = 0; i < numNodes; ++i)
for (int j = 0; j < numNodes; ++j) { scanf("%1d", &adjacencyMatrix[i][j]); }
if (hasCycle(adjacencyMatrix, numNodes)) printf("Yes Cycle Exists\n");
else printf("No Cycle Exists\n");
return 0; }
 16. Given a graph, Design an algorithm and implement it using a program to implement Floyd-
Warshall all pair shortest path algorithm.

Input Format:
The first line of input takes number of vertices in the graph.
Input will be the graph in the form of adjacency matrix or adjacency list. If a direct edge is not
present between any pair of vertex (u,v), then this entry is shown as AdjM[u,v] = INF.

Output Format:
Output will be shortest distance matrix in the form of V X V matrix, where each entry (u,v)
represents shortest distance between vertex u and vertex v.

Sample I/O Problem I:

Input: Output:
5 Shortest Distance Matrix:
01055INF 01015515
INF0555 INF0555
INF INF 0 INF 10 INF INF 0 15 10
INF INF INF 0 20 INF INF INF 0 20
INF INF INF 5 0 INF INF INF 5 0

#include <stdio.h>
#include <stdlib.h>

#define INF 99999

#define N 100
int min(int a, int b) {
return (a < b) ? a : b;
}
int main() {
int i, j, k, n;
printf("Enter the number of vertices: ");
scanf("%d", &n);
int graph[N][N];
printf("Enter the adjacency matrix (INF for no direct edge):\n");
for (i = 1; i <= n; ++i) {
for (j = 1; j <= n; ++j) {
scanf("%d", &graph[i][j]);
if (graph[i][j] == INF) {
graph[i][j] = INF;
}
}
}
// Floyd-Warshall Algorithm
for (k = 1; k <= n; ++k)
for (i = 1; i <= n; ++i)
for (j = 1; j <= n; ++j)
if (graph[i][k] != INF && graph[k][j] != INF)
graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);

// Output: Shortest distance matrix

printf("\nShortest Distance Matrix:\n");
for (i = 1; i <= n; ++i) {
for (j = 1; j <= n; ++j) {
if (graph[i][j] == INF) {
printf("INF ");
} else {
printf("%d ", graph[i][j]);
}
}
printf("\n");
}
return 0;
}
 17. Given a knapsack of maximum capacity w. N items are provided, each having its own value and
weight. You have to Design an algorithm and implement it using a program to find the list of the
selected items such that the final selected content has weight w and has maximum value. You can
take fractions of items,i.e. the items can be broken into smaller pieces so that you have to carry
only a fraction xi of item i, where 0 ≤xi≤ 1.

Input Format:
First input line will take number of items N which are provided.
Second input line will contain N space-separated array containing weights of all N items.
Third input line will contain N space-separated array containing values of all N items.
Last line of the input will take the maximum capacity w of knapsack.

Output Format:
First output line will give maximum value that can be achieved.
Next Line of output will give list of items selected along with their fraction of amount which has
been taken.

Sample I/O Problem II:

Input: Output:
6 Maximum value : 22.33
6103513 item-weight
621835 5-1
16 6-3
4-5
1-6
3-1

#include <stdio.h>
#include <stdlib.h>

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

int compareItems(const void *a, const void *b) {

return ((struct Item *)b)->valuePerWeight - ((struct Item *)a)->valuePerWeight;
}

void fractionalKnapsack(int n, int weights[], int values[], int maxCapacity) {

struct Item items[n];
for (int i = 0; i < n; ++i) {
items[i].weight = weights[i];
items[i].value = values[i];
items[i].valuePerWeight = (double)values[i] / weights[i];
items[i].index = i;
}

qsort(items, n, sizeof(struct Item), compareItems);

int currentWeight = 0;
double totalValue = 0.0;
double fractions[n];
 for (int i = 0; i < n; ++i) {
if (currentWeight + items[i].weight <= maxCapacity) {
fractions[items[i].index] = 1.0;
currentWeight += items[i].weight;
totalValue += items[i].value;
} else {
fractions[items[i].index] = (double)(maxCapacity - currentWeight) / items[i].weight;
totalValue += fractions[items[i].index] * items[i].value;
break;
}
}

printf("Maximum value: %lf\n", totalValue);

printf("Items selected with fractions:\n");

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

if (fractions[i] > 0) {
printf("Item %d: %lf of weight %d\n", i + 1, fractions[i], weights[i]);
}
}
}

int main() {
int n;
printf("Enter the number of items: ");
scanf("%d", &n);

int weights[n], values[n];

printf("Enter the weights of the items: ");

for (int i = 0; i < n; ++i) {
scanf("%d", &weights[i]);
}

printf("Enter the values of the items: ");

for (int i = 0; i < n; ++i) {
scanf("%d", &values[i]);
}

int maxCapacity;
printf("Enter the maximum capacity of the knapsack: ");
scanf("%d", &maxCapacity);

fractionalKnapsack(n, weights, values, maxCapacity);

return 0;
}
 18. Given a knapsack of maximum capacity w. N items are provided, each having its own value
and weight. Design an algorithm and implement it using a program to find the list of the
selected items such that the final selected content has weight <= w and has maximum value.
Here, you cannot break an item i.e. either pick the complete item or don't pick it. (0-1
property).

Input Format:
First line of input will provide number of items n.
Second line of input will take n space-separated integers describing weights for all
items. Third line of input will take n space-separated integers describing value for each
item. Last line of input will give the knapsack capacity.

Output Format:
Input: Output:
5 Value = 16
23346 Weights selected : 3 3 4
12594 Values of selected weights : 2 5 9
10
Output will be maximum value that can be achieved and list of items selected along with their
weight and value.

Sample I/O Problem I:

#include <stdio.h>

int max(int a, int b) {

return (a > b) ? a : b;
}

int knapsack(int W, int wt[], int val[], int n) {

int dp[n + 1][W + 1];

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

for (int j = 0; j <= W; j++) {
if (i == 0 || j == 0) {
dp[i][j] = 0;
} else if (wt[i - 1] <= j) {
dp[i][j] = max(val[i - 1] + dp[i - 1][j - wt[i - 1]], dp[i - 1][j]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}

int max_value = dp[n][W];

printf("Maximum value that can be achieved: %d\n", max_value);
printf("List of items selected along with their weight and value: \n");

int i = n, j = W;
while (i > 0 && j > 0) {
if (dp[i][j] != dp[i - 1][j]) {
printf("Item %d: Weight = %d, Value = %d\n", i, wt[i - 1], val[i - 1]);
j -= wt[i - 1];
}
i--;
}

return max_value;
}

int main() {
int n, W;
scanf("%d", &n);
int wt[n], val[n];

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

scanf("%d", &wt[i]);

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

scanf("%d", &val[i]);
 scanf("%d", &W);

knapsack(W, wt, val, n);

return 0;
}
 19.

#include <stdio.h>
#include <limits.h>

int MatrixChainOrder(int p[], int n) {

int m[n][n], i, j, k, L, q;
for (i = 1; i < n; i++)
m[i][i] = 0;
for (L = 2; L < n; L++) {
for (i = 1; i < n - L + 1; i++) {
j = i + L - 1;
m[i][j] = INT_MAX;
for (k = i; k <= j - 1; k++) {
q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
if (q < m[i][j])
m[i][j] = q;
}
}
}
return m[1][n - 1];
}

int main() {
int n, a, b;
scanf("%d", &n);
int arr[n + 1]; // Increase the size by 1 to store 'b'

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

scanf("%d %d", &a, &b);
arr[i] = a;
}
 arr[n] = b; // Store 'b' at the end of the array

printf("%d", MatrixChainOrder(arr, n + 1));

return 0;
}

20. Given an unsorted array of elements, design an algorithm and implement it using a program
to find whether majority element exists or not. Also find median of the array. A majority
element is an element that appears more than n/2 times, where n is the size of array.

Input Format:
First line of input will give size n of array.
Second line of input will take n space-separated elements of array.

Output Format:
First line of output will be 'yes' if majority element exists, otherwise print 'no'.
Second line of output will print median of the array.

Sample I/O Problem III:

Input: Output:
9 yes
442322322 2

#include <stdio.h>
#include <stdbool.h>

bool majority(int n, int arr[]) {

int count[100] = {0}; // Initialize count array with zeros
int i;

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

count[arr[i]]++;

int maxCount = 0;
for (i = 0; i < 100; i++) {
if (count[i] > maxCount)
maxCount = count[i];
}

if (maxCount > n / 2)
return true;
else
return false;
}
float median(int n, int arr[]) {
float med;

if (n % 2 != 0)
med = (float)arr[n / 2];
else
med = (float)(arr[n / 2] + arr[n / 2 - 1]) / 2.0;

return med;
}

int main() {
int n, i;
scanf("%d", &n);

int arr[100]; // Assuming a maximum size of 100, change accordingly

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

scanf("%d", &arr[i]);

// Sorting in descending order

for (i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] < arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}

if (majority(n, arr))
printf("Yes\n");
else
printf("No\n");

printf("\n%f\n", median(n, arr));

return 0;
}