1.

Write a program to sort a list of N elements

using Selection Sort Technique.

#include <stdio.h>
// Function to swap two elements
void swap(int *x, int *y) {
int temp = *x;
*x = *y;
*y = temp;
}
// Function to perform Selection Sort
void selectionSort(int arr[], int n) {
int i, j, min_idx;
// One by one move the boundary of unsorted
subarray
for (i = 0; i < n - 1; i++) {
// Find the minimum element in unsorted array
min_idx = i;
for (j = i + 1; j < n; j++) {
if (arr[j] < arr[min_idx])
min_idx = j;
}

// Swap the found minimum element with the

first element
swap(&arr[min_idx], &arr[i]);
}
}

// Function to print the array

void printArray(int arr[], int size) {
 int i;
for (i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}

int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);

printf("Original array: \n");

printArray(arr, n);

selectionSort(arr, n);

printf("Sorted array in ascending order: \n");

printArray(arr, n);

return 0;
}
2. Write a program to perform Travelling Salesman
Problem
#include <stdio.h>
#define V 4 // Number of vertices in the graph

int graph[V][V] = {
{0, 10, 15, 20},
{10, 0, 35, 25},
{15, 35, 0, 30},
{20, 25, 30, 0}
}; // Example adjacency matrix representing the graph

int min(int a, int b) {

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

int tsp(int mask, int pos) {

if (mask == (1 << V) - 1) // If all cities have been
visited
return graph[pos][0]; // Return to starting city

int minCost = 99999;

 for (int city = 0; city < V; city++) {
if (!(mask & (1 << city))) {
int newCost = graph[pos][city] + tsp(mask | (1 <<
city), city);
minCost = min(minCost, newCost);
}
}

return minCost;
}

int main() {
int start = 0; // Starting vertex

printf("The minimum cost for the TSP is: %d\n", tsp(1

<< start, start));

return 0;
}
3. Write program to implement Dynamic
Programming algorithm for the 0/1 Knapsack
problem.
#include <stdio.h>
#include <stdlib.h>
#define V 5 // Number of vertices in the graph
#define E 7 // Number of edges in the graph

typedef struct Edge {

int src, dest, weight;
} Edge;

typedef struct Graph {

int V, E;
Edge* edge;
} Graph;

Graph* createGraph(int v, int e) {

Graph* graph = (Graph*)malloc(sizeof(Graph));
graph->V = v;
graph->E = e;
graph->edge = (Edge*)malloc(e * sizeof(Edge));
return graph;
}

void printMST(Edge result[], int e) {

printf("Edge Weight\n");
 for (int i = 0; i < e; i++) {
printf("%d - %d %d \n", result[i].src, result[i].dest,
result[i].weight);
}
}

int find(int parent[], int i) {

if (parent[i] == -1)
return i;
return find(parent, parent[i]);
}
void Union(int parent[], int x, int y) {
int xset = find(parent, x);
int yset = find(parent, y);
parent[xset] = yset;
}
int myComp(const void* a, const void* b) {
Edge* a1 = (Edge*)a;
Edge* b1 = (Edge*)b;
return a1->weight > b1->weight;
}

void kruskalMST(Graph* graph) {

 int V = graph->V;
Edge result[V];
int e = 0;
int i = 0;

qsort(graph->edge, graph->E, sizeof(graph->edge[0]),

myComp);

int* parent = (int*)malloc(V * sizeof(int));

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

parent[v] = -1;

while (e < V - 1 && i < graph->E) {

Edge next_edge = graph->edge[i++];
int x = find(parent, next_edge.src);
int y = find(parent, next_edge.dest);

if (x != y) {
result[e++] = next_edge;
Union(parent, x, y);
}
}
 printMST(result, e);
}

int main() {
Graph* graph = createGraph(V, E);

graph->edge[0].src = 0;
graph->edge[0].dest = 1;
graph->edge[0].weight = 10;

graph->edge[1].src = 0;
graph->edge[1].dest = 2;
graph->edge[1].weight = 6;

graph->edge[2].src = 0;
graph->edge[2].dest = 3;
graph->edge[2].weight = 5;

graph->edge[3].src = 1;
graph->edge[3].dest = 3;
graph->edge[3].weight = 15;
 graph->edge[4].src = 2;
graph->edge[4].dest = 3;
graph->edge[4].weight = 4;

graph->edge[5].src = 1;
graph->edge[5].dest = 4;
graph->edge[5].weight = 3;

graph->edge[6].src = 3;
graph->edge[6].dest = 4;
graph->edge[6].weight = 7;

kruskalMST(graph);

return 0;
}
#include <stdio.h>

// Function to calculate maximum of two integers

int max(int a, int b) {
return (a > b) ? a : b;
}
// Function implementing the 0/1 Knapsack problem
using Dynamic Programming
int knapsack(int W, int wt[], int val[], int n) {
int i, w;
int K[n + 1][W + 1];

// Building the K table in bottom-up manner

for (i = 0; i <= n; i++) {
for (w = 0; w <= W; w++) {
if (i == 0 || w == 0)
K[i][w] = 0;
else if (wt[i - 1] <= w)
K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]],
K[i - 1][w]);
else
K[i][w] = K[i - 1][w];
}
}

return K[n][W]; // Returning the maximum value that

can be put in the knapsack of capacity W
}

int main() {
 int val[] = {60, 100, 120}; // Values of items
int wt[] = {10, 20, 30}; // Weights of items
int W = 50; // Knapsack capacity
int n = sizeof(val) / sizeof(val[0]);

int maxValue = knapsack(W, wt, val, n);

printf("The maximum value that can be put in a
knapsack of capacity %d is: %d\n", W, maxValue);

return 0;
}
4. Write a program to perform Knapsack Problem
using GreedySolution
#include <stdio.h>
#include <stdlib.h>

// Structure to represent items

struct Item {
int value;
int weight;
};

// Function to compare items based on value-to-weight

ratio for sorting
int compare(const void *a, const void *b) {
double ratioA = (double)(((struct Item *)a)->value) /
(((struct Item *)a)->weight);
double ratioB = (double)(((struct Item *)b)->value) /
(((struct Item *)b)->weight);
return (ratioB > ratioA) ? 1 : -1;
}

// Function to perform the Greedy approach for

Knapsack
double knapsackGreedy(int W, struct Item arr[], int n) {
 // Sorting items based on value-to-weight ratio
qsort(arr, n, sizeof(arr[0]), compare);

int currentWeight = 0; // Current weight in knapsack

double finalValue = 0.0; // Final value of items
selected

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

// If adding the whole item doesn't exceed the
capacity, add it completely
if (currentWeight + arr[i].weight <= W) {
currentWeight += arr[i].weight;
finalValue += arr[i].value;
} else {
// Otherwise, add fractional part of the item
int remaining = W - currentWeight;
finalValue += arr[i].value * ((double)remaining /
arr[i].weight);
break;
}
}

return finalValue;
}
int main() {
int W = 50; // Knapsack capacity
struct Item items[] = {{60, 10}, {100, 20}, {120, 30}}; //
Values and weights of items
int n = sizeof(items) / sizeof(items[0]);

double maxValue = knapsackGreedy(W, items, n);

printf("The maximum value that can be put in a
knapsack of capacity %d using Greedy approach is:
%.2f\n", W, maxValue);

return 0;
}
5. Write program to implement the DFS and BFS
algorithm for agraph.
#include <stdio.h>
#include <stdlib.h>

#define MAX 100

// Stack implementation for DFS

struct Stack {
int items[MAX];
int top;
};

void initializeStack(struct Stack *s) {

s->top = -1;
}

int isEmpty(struct Stack *s) {

return (s->top == -1);
}

int isFull(struct Stack *s) {

return (s->top == MAX - 1);
}

void push(struct Stack *s, int value) {

if (isFull(s)) {
printf("Stack is full\n");
} else {
s->items[++(s->top)] = value;
}
}

int pop(struct Stack *s) {

if (isEmpty(s)) {
printf("Stack is empty\n");
return -1;
} else {
return s->items[(s->top)--];
}
}

// Queue implementation for BFS

struct Queue {
int items[MAX];
int front;
 int rear;
};

void initializeQueue(struct Queue *q) {

q->front = -1;
q->rear = -1;
}

int isQueueEmpty(struct Queue *q) {

return (q->rear == -1);
}

int isQueueFull(struct Queue *q) {

return ((q->rear + 1) % MAX == q->front);
}

void enqueue(struct Queue *q, int value) {

if (isQueueFull(q)) {
printf("Queue is full\n");
} else {
if (isQueueEmpty(q)) {
q->front = 0;
}
 q->rear = (q->rear + 1) % MAX;
q->items[q->rear] = value;
}
}

int dequeue(struct Queue *q) {

int value;
if (isQueueEmpty(q)) {
printf("Queue is empty\n");
return -1;
} else {
value = q->items[q->front];
if (q->front == q->rear) {
q->front = -1;
q->rear = -1;
} else {
q->front = (q->front + 1) % MAX;
}
return value;
}
}

// Depth-First Search (DFS) algorithm

void DFS(int graph[MAX][MAX], int vertices, int start) {
struct Stack stack;
int visited[MAX] = {0};

initializeStack(&stack);

push(&stack, start);
visited[start] = 1;

printf("Depth-First Search starting from vertex %d: ",

start);

while (!isEmpty(&stack)) {
int current = pop(&stack);
printf("%d ", current);

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

if (graph[current][i] == 1 && visited[i] == 0) {
push(&stack, i);
visited[i] = 1;
}
}
}
 printf("\n");
}

// Breadth-First Search (BFS) algorithm

void BFS(int graph[MAX][MAX], int vertices, int start) {
struct Queue queue;
int visited[MAX] = {0};

initializeQueue(&queue);

visited[start] = 1;
enqueue(&queue, start);

printf("Breadth-First Search starting from vertex %d: ",

start);

while (!isQueueEmpty(&queue)) {
int current = dequeue(&queue);
printf("%d ", current);

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

if (graph[current][i] == 1 && visited[i] == 0) {
visited[i] = 1;
 enqueue(&queue, i);
}
}
}
printf("\n");
}

int main() {
int graph[MAX][MAX], vertices, edges, i, j, v, u;

printf("Enter the number of vertices: ");

scanf("%d", &vertices);

printf("Enter the number of edges: ");

scanf("%d", &edges);

for (i = 0; i < MAX; ++i) {

for (j = 0; j < MAX; ++j) {
graph[i][j] = 0;
}
}

printf("Enter the edges (format: vertex1 vertex2):\n");

 for (i = 0; i < edges; ++i) {
scanf("%d %d", &v, &u);
graph[v][u] = 1; // Assuming an undirected graph
graph[u][v] = 1; // Add this line for directed graph
}

printf("\nEnter the starting vertex for DFS and BFS: ");

scanf("%d", &v);

DFS(graph, vertices, v);

BFS(graph, vertices, v);

return 0;
}
6. Write a program to find minimum and maximum
value in an array using divide and conquer.

#include <stdio.h>

// Structure to hold minimum and maximum values

struct MinMax {
int min;
int max;
};

// Function to find minimum and maximum using divide

and conquer
struct MinMax findMinMax(int arr[], int low, int high) {
struct MinMax minmax, leftMinMax, rightMinMax;
int mid;

// If there is only one element

if (low == high) {
minmax.min = arr[low];
minmax.max = arr[low];
return minmax;
}

// If there are two elements

if (high == low + 1) {
if (arr[low] > arr[high]) {
minmax.max = arr[low];
minmax.min = arr[high];
} else {
minmax.max = arr[high];
minmax.min = arr[low];
 }
return minmax;
}

// If there are more than two elements, divide the

array
mid = (low + high) / 2;
leftMinMax = findMinMax(arr, low, mid);
rightMinMax = findMinMax(arr, mid + 1, high);

// Compare minimums and maximums of two halves

to get final result
if (leftMinMax.min < rightMinMax.min)
minmax.min = leftMinMax.min;
else
minmax.min = rightMinMax.min;

if (leftMinMax.max > rightMinMax.max)

minmax.max = leftMinMax.max;
else
minmax.max = rightMinMax.max;

return minmax;
}

int main() {
int arr[] = {1000, 11, 445, 1, 330, 3000};
int size = sizeof(arr) / sizeof(arr[0]);

struct MinMax result = findMinMax(arr, 0, size - 1);

printf("Minimum element in the array: %d\n",

result.min);
printf("Maximum element in the array: %d\n",
result.max);

return 0;
}
7. Write a test program to implement Divide and
Conquer Strategy. Eg: Quick sort algorithm for
sorting list of integers in ascending order.

#include <stdio.h>
// Function to swap two elements
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
 *b = temp;
}

// Partition function to select a pivot and rearrange the

array elements
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // Choosing the pivot element
int i = (low - 1); // Index of smaller element

for (int j = low; j <= high - 1; j++) {

// If the current element is smaller than or equal to
the pivot
if (arr[j] <= pivot) {
i++; // Increment index of smaller element
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}

// Function to implement Quick Sort algorithm using

Divide and Conquer
void quickSort(int arr[], int low, int high) {
 if (low < high) {
// pi is partitioning index, arr[pi] is now at right place
int pi = partition(arr, low, high);

// Separately sort elements before partition and

after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}

// Function to print the array

void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}

int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: \n");
 printArray(arr, n);

quickSort(arr, 0, n - 1);

printf("Sorted array in ascending order: \n");

printArray(arr, n);

return 0;
}

8. Write a program to implement Merge sort

algorithm forsorting a list of integers inascending
order.

#include <stdio.h>
// Merge function to merge two sorted subarrays into a
single sorted array
void merge(int arr[], int left, int mid, int right) {
int i, j, k;
int n1 = mid - left + 1;
int n2 = right - mid;

// Create temporary arrays

int L[n1], R[n2];
// Copy data to temporary arrays L[] and R[]
for (i = 0; i < n1; i++)
L[i] = arr[left + i];
for (j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];

// Merge the temporary arrays back into arr[left..right]

i = 0;
j = 0;
k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}

// Copy the remaining elements of L[], if any

 while (i < n1) {
arr[k] = L[i];
i++;
k++;
}

// Copy the remaining elements of R[], if any

while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}

// Merge Sort function to divide the array into halves and

merge them recursively
void mergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;

// Sort first and second halves

mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
 // Merge the sorted halves
merge(arr, left, mid, right);
}
}

// Function to print the array

void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}

int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int arr_size = sizeof(arr) / sizeof(arr[0]);

printf("Original array: \n");

printArray(arr, arr_size);

mergeSort(arr, 0, arr_size - 1);

 printf("Sorted array in ascending order: \n");
printArray(arr, arr_size);

return 0;
}

9. Sort a given set of n integer elements using Merge

Sort method and compute its time complexity. Run
the program for varied values of n> 5000, and record
the time taken to sort.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// Merge function to merge two sorted subarrays into a

single sorted array
void merge(int arr[], int left, int mid, int right) {
int i, j, k;
int n1 = mid - left + 1;
int n2 = right - mid;

// Create temporary arrays

int L[n1], R[n2];
// Copy data to temporary arrays L[] and R[]
for (i = 0; i < n1; i++)
L[i] = arr[left + i];
for (j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];

// Merge the temporary arrays back into arr[left..right]

i = 0;
j = 0;
k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}

// Copy the remaining elements of L[], if any

while (i < n1) {
 arr[k] = L[i];
i++;
k++;
}

// Copy the remaining elements of R[], if any

while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}

// Merge Sort function to divide the array into halves and

merge them recursively
void mergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;

// Sort first and second halves

mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
 // Merge the sorted halves
merge(arr, left, mid, right);
}
}

int main() {
int n, i;
clock_t start, end;
double cpu_time_used;

printf("Enter the number of elements: ");

scanf("%d", &n);

int arr[n];

// Generating n random integers for sorting

for (i = 0; i < n; i++) {
arr[i] = rand();
}

printf("Sorting %d elements using Merge Sort...\n", n);

start = clock(); // Record the start time

 mergeSort(arr, 0, n - 1); // Sorting using Merge Sort
algorithm

end = clock(); // Record the end time

cpu_time_used = ((double)(end - start)) /

CLOCKS_PER_SEC; // Calculate the CPU time used

printf("Sorted array in ascending order: \n");

// Print sorted array if needed
// for (i = 0; i < n; i++) {
// printf("%d ", arr[i]);
// }
// printf("\n");

printf("Time taken for sorting %d elements: %f

seconds\n", n, cpu_time_used);

return 0;
}

10. Sort a given set of n integer elements using

Quick Sort method and compute its time complexity.
Run the program for varied values of n> 5000 and
record the time taken to sort.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// Function to swap two elements

void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
// Partition function to select a pivot and rearrange the
array elements
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // Choosing the pivot element
int i = (low - 1); // Index of smaller element
for (int j = low; j <= high - 1; j++) {
// If the current element is smaller than or equal to
the pivot
if (arr[j] <= pivot) {
i++; // Increment index of smaller element
swap(&arr[i], &arr[j]);
}
 }
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}

// Quick Sort function to sort the array using divide and

conquer
void quickSort(int arr[], int low, int high) {
if (low < high) {
// pi is partitioning index, arr[pi] is now at right place
int pi = partition(arr, low, high);

// Separately sort elements before partition and

after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}

int main() {
int n, i;
clock_t start, end;
double cpu_time_used;
 printf("Enter the number of elements: ");
scanf("%d", &n);

int arr[n];

// Generating n random integers for sorting

for (i = 0; i < n; i++) {
arr[i] = rand();
}

printf("Sorting %d elements using Quick Sort...\n", n);

start = clock(); // Record the start time

quickSort(arr, 0, n - 1); // Sorting using Quick Sort

algorithm

end = clock(); // Record the end time

cpu_time_used = ((double)(end - start)) /

CLOCKS_PER_SEC; // Calculate the CPU time used
 printf("Sorted array in ascending order: \n");
// Print sorted array if needed
// for (i = 0; i < n; i++) {
// printf("%d ", arr[i]);
// }
// printf("\n");

printf("Time taken for sorting %d elements: %f

seconds\n", n, cpu_time_used);

return 0;
}

11. Write C program that acceptsthe vertices and

edgesfor a graph and stores it as an adjacency
matrix.

#include <stdio.h>
#define MAX_VERTICES 100
int main() {
int vertices, edges, i, j;
printf("Enter the number of vertices: ");
scanf("%d", &vertices);
 int
adjacencyMatrix[MAX_VERTICES][MAX_VERTICES];
// Initialize the adjacency matrix with zeros
for (i = 0; i < vertices; i++) {
for (j = 0; j < vertices; j++) {
adjacencyMatrix[i][j] = 0;
}
}
printf("Enter the number of edges: ");
scanf("%d", &edges);
printf("Enter edges (format: vertex1 vertex2):\n");
for (i = 0; i < edges; i++) {
int v1, v2;
scanf("%d %d", &v1, &v2);
// Assuming an undirected graph, so marking both
vertices as connected
adjacencyMatrix[v1][v2] = 1;
adjacencyMatrix[v2][v1] = 1; // Comment out for
directed graph
}
// Displaying the adjacency matrix
printf("\nAdjacency Matrix:\n");
for (i = 0; i < vertices; i++) {
 for (j = 0; j < vertices; j++) {
printf("%d ", adjacencyMatrix[i][j]);
}
printf("\n");
}
return 0;
}

12. Implement function to print In-Degree, Out-

Degree and to display that adjacency matrix.
#include <stdio.h>
#define MAX_VERTICES 100
// Function to calculate and print In-Degree of vertices in
a graph
void calculateInDegree(int vertices, int
adjacencyMatrix[MAX_VERTICES][MAX_VERTICES]) {
int inDegree[MAX_VERTICES] = {0};

// Calculate in-degree of each vertex

for (int i = 0; i < vertices; i++) {
for (int j = 0; j < vertices; j++) {
if (adjacencyMatrix[j][i] == 1) {
inDegree[i]++;
}
 }
}

// Print in-degree of each vertex

printf("\nIn-Degree of vertices:\n");
for (int i = 0; i < vertices; i++) {
printf("Vertex %d: %d\n", i, inDegree[i]);
}
}

// Function to calculate and print Out-Degree of vertices

in a graph
void calculateOutDegree(int vertices, int
adjacencyMatrix[MAX_VERTICES][MAX_VERTICES]) {
int outDegree[MAX_VERTICES] = {0};

// Calculate out-degree of each vertex

for (int i = 0; i < vertices; i++) {
for (int j = 0; j < vertices; j++) {
if (adjacencyMatrix[i][j] == 1) {
outDegree[i]++;
}
}
 }

// Print out-degree of each vertex

printf("\nOut-Degree of vertices:\n");
for (int i = 0; i < vertices; i++) {
printf("Vertex %d: %d\n", i, outDegree[i]);
}
}

// Function to display the adjacency matrix of the graph

void displayAdjacencyMatrix(int vertices, int
adjacencyMatrix[MAX_VERTICES][MAX_VERTICES]) {
printf("\nAdjacency Matrix:\n");
for (int i = 0; i < vertices; i++) {
for (int j = 0; j < vertices; j++) {
printf("%d ", adjacencyMatrix[i][j]);
}
printf("\n");
}
}

int main() {
int vertices, edges, i, j;
 printf("Enter the number of vertices: ");
scanf("%d", &vertices);

int
adjacencyMatrix[MAX_VERTICES][MAX_VERTICES];

// Initialize the adjacency matrix with zeros

for (i = 0; i < vertices; i++) {
for (j = 0; j < vertices; j++) {
adjacencyMatrix[i][j] = 0;
}
}

printf("Enter the number of edges: ");

scanf("%d", &edges);

printf("Enter edges (format: vertex1 vertex2):\n");

for (i = 0; i < edges; i++) {
int v1, v2;
scanf("%d %d", &v1, &v2);

// Assuming an undirected graph, so marking both

vertices as connected
 adjacencyMatrix[v1][v2] = 1;
adjacencyMatrix[v2][v1] = 1; // Comment out for
directed graph
}

displayAdjacencyMatrix(vertices, adjacencyMatrix);
calculateInDegree(vertices, adjacencyMatrix);
calculateOutDegree(vertices, adjacencyMatrix);

return 0;
}

13. Write program to implement backtracking

algorithm for solving problems like N queens .
#include <stdio.h>
#include <stdbool.h>

#define N 8 // Change N to the required size of the

chessboard

void printSolution(int board[N][N]) {

for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
printf("%d ", board[i][j]);
 }
printf("\n");
}
}

bool isSafe(int board[N][N], int row, int col) {

int i, j;

// Check this row on the left side

for (i = 0; i < col; i++) {
if (board[row][i])
return false;
}

// Check upper diagonal on the left side

for (i = row, j = col; i >= 0 && j >= 0; i--, j--) {
if (board[i][j])
return false;
}

// Check lower diagonal on the left side

for (i = row, j = col; j >= 0 && i < N; i++, j--) {
if (board[i][j])
 return false;
}

return true;
}

bool solveNQueensUtil(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 (solveNQueensUtil(board, col + 1))

return true;

board[i][col] = 0; // Backtrack
}
}

return false;
}
bool solveNQueens() {
int board[N][N] = {{0}};

if (solveNQueensUtil(board, 0) == false) {
printf("Solution does not exist");
return false;
}

printSolution(board);
return true;
}
int main() {
solveNQueens();
return 0;
}

14. Write a program to implement the backtracking

algorithm for the sum of subsets problem
#include <stdio.h>
#include <stdbool.h>
#define MAX 100
int finalSubset[MAX];
int finalSize = 0;
bool isSubsetSum(int set[], int n, int sum) {
if (sum == 0) {
return true;
}
if (n == 0 && sum != 0) {
return false;
}

if (set[n - 1] > sum) {

return isSubsetSum(set, n - 1, sum);
}

if (isSubsetSum(set, n - 1, sum) == true) {

return true;
}

finalSubset[finalSize++] = set[n - 1];

return isSubsetSum(set, n - 1, sum - set[n - 1]);

}

void displaySubset(int set[], int size) {

 printf("Subset with the given sum is: ");
for (int i = 0; i < size; i++) {
printf("%d ", set[i]);
}
printf("\n");
}

int main() {
int set[] = {10, 7, 5, 18, 12, 20, 15};
int n = sizeof(set) / sizeof(set[0]);
int sum = 35;

if (isSubsetSum(set, n, sum) == true) {

displaySubset(finalSubset, finalSize);
} else {
printf("No subset with the given sum exists.\n");
}

return 0;
}

15. Write program to implement greedy algorithm

for job sequencing with deadlines.
#include <stdio.h>
#include <stdbool.h>
#define MAX 100
typedef struct {
int jobID;
int deadline;
int profit;
} Job;
void swap(Job *a, Job *b) {
Job temp = *a;
*a = *b;
*b = temp;
}
void sortJobs(Job jobs[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (jobs[j].profit < jobs[j + 1].profit) {
swap(&jobs[j], &jobs[j + 1]);
}
}
}
}
void jobSequencing(Job jobs[], int n) {
 int result[MAX];
bool slot[MAX] = {false};
for (int i = 0; i < n; i++) {
for (int j = jobs[i].deadline - 1; j >= 0; j--) {
if (slot[j] == false) {
result[j] = i;
slot[j] = true;
break;
}
}
}
printf("Job Sequence with deadlines:\n");
for (int i = 0; i < MAX; i++) {
if (slot[i]) {
printf("Job ID: %d, Deadline: %d, Profit: %d\n",
jobs[result[i]].jobID, jobs[result[i]].deadline,
jobs[result[i]].profit);
}
}
}

int main() {
Job jobs[] = { {1, 4, 70}, {2, 2, 60}, {3, 4, 100}, {4, 3,
50} };
 int n = sizeof(jobs) / sizeof(jobs[0]);
sortJobs(jobs, n);
jobSequencing(jobs, n);

return 0;
}
16. Write program to implement Dynamic
Programming algorithm for the Optimal Binary
Search Tree Problem.
#include <stdio.h>
#include <limits.h>
#define MAX_KEYS 10
int obst(int keys[], int freq[], int n) {
int cost[MAX_KEYS + 1][MAX_KEYS + 1];
// Initializing cost[i][i]
for (int i = 0; i < n; i++)
cost[i][i] = freq[i];
// Computing costs for chains of increasing length
for (int L = 2; L <= n; L++) {
for (int i = 0; i <= n - L + 1; i++) {
int j = i + L - 1;
cost[i][j] = INT_MAX;
int sum = 0;
 for (int k = i; k <= j; k++)
sum += freq[k];

for (int r = i; r <= j; r++) {

int c = ((r > i) ? cost[i][r - 1] : 0) +
((r < j) ? cost[r + 1][j] : 0) +
sum;

if (c < cost[i][j])
cost[i][j] = c;
}
}
}
return cost[0][n - 1];
}

int main() {
int keys[] = {10, 12, 20};
int freq[] = {34, 8, 50};
int n = sizeof(keys) / sizeof(keys[0]);

printf("Cost of optimal BST is: %d\n", obst(keys, freq,

n));
 return 0;
}
17. Write a program that implements Prim’algorithm
to generate minimum cost spanning Tree.
#include <stdio.h>
#include <stdbool.h>
#include <limits.h>
#define V 5 // Number of vertices in the graph
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;
}
void printMST(int parent[], int graph[V][V]) {
printf("Edge Weight\n");
for (int i = 1; i < V; i++) {
 printf("%d - %d %d \n", parent[i], i,
graph[i][parent[i]]);
}
}
void primMST(int graph[V][V]) {
int parent[V];
int key[V];
bool mstSet[V];
for (int i = 0; i < V; i++) {
key[i] = INT_MAX;
mstSet[i] = false;
}
key[0] = 0;
parent[0] = -1;
for (int count = 0; count < V - 1; count++) {
int u = minKey(key, mstSet);
mstSet[u] = true;
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);
}
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);
return 0;
}

18. Write a program that implements Kruskal’s

algorithm to generate minimum cost spanning tree.
#include <stdio.h>
#include <stdlib.h>
#define V 5 // Number of vertices in the graph
#define E 7 // Number of edges in the graph
typedef struct Edge {
 int src, dest, weight;
} Edge;
typedef struct Graph {
int V, E;
Edge* edge;
} Graph;
Graph* createGraph(int v, int e) {
Graph* graph = (Graph*)malloc(sizeof(Graph));
graph->V = v;
graph->E = e;
graph->edge = (Edge*)malloc(e * sizeof(Edge));
return graph;
}

void printMST(Edge result[], int e) {

printf("Edge Weight\n");
for (int i = 0; i < e; i++) {
printf("%d - %d %d \n", result[i].src, result[i].dest,
result[i].weight);
}
}
int find(int parent[], int i) {
if (parent[i] == -1)
 return i;
return find(parent, parent[i]);
}
void Union(int parent[], int x, int y) {
int xset = find(parent, x);
int yset = find(parent, y);
parent[xset] = yset;
}
int myComp(const void* a, const void* b) {
Edge* a1 = (Edge*)a;
Edge* b1 = (Edge*)b;
return a1->weight > b1->weight;
}
void kruskalMST(Graph* graph) {
int V = graph->V;
Edge result[V];
int e = 0;
int i = 0;
qsort(graph->edge, graph->E, sizeof(graph->edge[0]),
myComp);
int* parent = (int*)malloc(V * sizeof(int));
for (int v = 0; v < V; ++v)
parent[v] = -1;
 while (e < V - 1 && i < graph->E) {
Edge next_edge = graph->edge[i++];
int x = find(parent, next_edge.src);
int y = find(parent, next_edge.dest);
if (x != y) {
result[e++] = next_edge;
Union(parent, x, y);
}
}
printMST(result, e);
}
int main() {
Graph* graph = createGraph(V, E);

graph->edge[0].src = 0;
graph->edge[0].dest = 1;
graph->edge[0].weight = 10;

graph->edge[1].src = 0;
graph->edge[1].dest = 2;
graph->edge[1].weight = 6;

graph->edge[2].src = 0;
 graph->edge[2].dest = 3;
graph->edge[2].weight = 5;

graph->edge[3].src = 1;
graph->edge[3].dest = 3;
graph->edge[3].weight = 15;

graph->edge[4].src = 2;
graph->edge[4].dest = 3;
graph->edge[4].weight = 4;

graph->edge[5].src = 1;
graph->edge[5].dest = 4;
graph->edge[5].weight = 3;

graph->edge[6].src = 3;
graph->edge[6].dest = 4;
graph->edge[6].weight = 7;

kruskalMST(graph);

return 0;
}