/**************************************************************************

Name : Shelke Vaibhavi Vijay Roll No : 7402

Class : [Link](Computer Science)- I

Assignment No : 1

Assignment Name : Write programs in C to sort a list of n numbers in ascending order using
selection sort, insertion sort, heap sort, radix sort. Determine the time required to sort and
compare on basis of time complexity for different values of n.

**************************************************************************/

//ass1.c

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

// Function Prototypes

void selectionSort(int arr[], int n);

void insertionSort(int arr[], int n);

void heapSort(int arr[], int n);

void radixSort(int arr[], int n);

// Function to generate random numbers

void generateRandomArray(int arr[], int n) {

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

arr[i] = rand() % 10000; // Generate numbers between 0 and 9999

// Selection Sort

void selectionSort(int arr[], int n) {

int i, j, min_idx, temp;

for (i = 0; i < n - 1; i++) {

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

temp = arr[min_idx];

arr[min_idx] = arr[i];

arr[i] = temp;

// Insertion Sort

void insertionSort(int arr[], int n) {

int i, key, j;

for (i = 1; i < n; i++) {

key = arr[i];

j = i - 1;

while (j >= 0 && arr[j] > key) {

arr[j + 1] = arr[j];

j = j - 1;

arr[j + 1] = key;

// Function to heapify a subtree rooted at index i

void heapify(int arr[], int n, int i) {

int largest = i;

int left = 2 * i + 1;

int right = 2 * i + 2;

int temp;

if (left < n && arr[left] > arr[largest]) {

largest = left;
 }

if (right < n && arr[right] > arr[largest]) {

largest = right;

if (largest != i) {

temp = arr[i];

arr[i] = arr[largest];

arr[largest] = temp;

heapify(arr, n, largest);

// Heap Sort

void heapSort(int arr[], int n) {

int i, temp;

// Build max heap

for (i = n / 2 - 1; i >= 0; i--) {

heapify(arr, n, i);

// Extract elements one by one from the heap

for (i = n - 1; i >= 0; i--) {

temp = arr[0];

arr[0] = arr[i];

arr[i] = temp;

heapify(arr, i, 0);

// Function to get the maximum element from the array

int getMax(int arr[], int n) {

int max = arr[0];

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

 if (arr[i] > max) {

max = arr[i];

return max;

// Counting sort based on significant place (exp is 10^i)

void countingSort(int arr[], int n, int exp) {

int output[n];

int count[10] = {0};

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

count[(arr[i] / exp) % 10]++;

for (int i = 1; i < 10; i++) {

count[i] += count[i - 1];

for (int i = n - 1; i >= 0; i--) {

output[count[(arr[i] / exp) % 10] - 1] = arr[i];

count[(arr[i] / exp) % 10]--;

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

arr[i] = output[i];

// Radix Sort

void radixSort(int arr[], int n) {

int max = getMax(arr, n);

for (int exp = 1; max / exp > 0; exp *= 10) {

countingSort(arr, n, exp);

}
}

int main() {

int n = 10000; // Array size, you can modify this for different sizes

int arr[n];

// Generate random numbers

generateRandomArray(arr, n);

// Measure time for Selection Sort

int arr_copy[n];

for (int i = 0; i < n; i++) arr_copy[i] = arr[i];

clock_t start = clock();

selectionSort(arr_copy, n);

clock_t end = clock();

printf("Selection Sort Time: %lf seconds\n", (double)(end - start) / CLOCKS_PER_SEC);

// Measure time for Insertion Sort

for (int i = 0; i < n; i++) arr_copy[i] = arr[i];

start = clock();

insertionSort(arr_copy, n);

end = clock();

printf("Insertion Sort Time: %lf seconds\n", (double)(end - start) / CLOCKS_PER_SEC);

// Measure time for Heap Sort

for (int i = 0; i < n; i++) arr_copy[i] = arr[i];

start = clock();

heapSort(arr_copy, n);

end = clock();

printf("Heap Sort Time: %lf seconds\n", (double)(end - start) / CLOCKS_PER_SEC);

// Measure time for Radix Sort

for (int i = 0; i < n; i++) arr_copy[i] = arr[i];

start = clock();

radixSort(arr_copy, n);

end = clock();
 printf("Radix Sort Time: %lf seconds\n", (double)(end - start) / CLOCKS_PER_SEC);

return 0;

/******************************OUTPUT************************************

[root@localhost vaibhavishelke]# vim ass1.c

[root@localhost vaibhavishelke]# gcc ass1.c

[root@localhost vaibhavishelke]# ./[Link]

Selection Sort Time: 0.269349 seconds

Insertion Sort Time: 0.157727 seconds

Heap Sort Time: 0.003797 seconds

Radix Sort Time: 0.002205 seconds

**************************************************************************/
/**************************************************************************

Name : Shelke Vaibhavi Vijay Roll No : 7402

Class : [Link](Computer Science)- I

Assignment No : 2

Assignment Name : Write a program in C/C++/ Java to sort a given set of elements using the
Quick sort method and determine the time required to sort the elements. Repeat the
experiment for different values of n, the number of elements in the list to be sorted. The
elements can be read from a file or can be generated using the random number generator.

**************************************************************************/

//ass2.c

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

// Function to partition the array for Quick Sort

int partition(int arr[], int low, int high) {

int pivot = arr[high];

int i = low - 1;

int temp;

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

if (arr[j] < pivot) {

i++;

temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

// Swap the pivot element with the element at index i + 1

temp = arr[i + 1];

arr[i + 1] = arr[high];

arr[high] = temp;
 return i + 1;

// Quick Sort Algorithm

void quickSort(int arr[], int low, int high) {

if (low < high) {

// Partition the array

int pi = partition(arr, low, high);

// Recursively sort the two halves

quickSort(arr, low, pi - 1);

quickSort(arr, pi + 1, high);

// Function to generate an array of random numbers

void generateRandomArray(int arr[], int n) {

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

arr[i] = rand() % 10000; // Generate numbers between 0 and 9999

// Function to read integers from a file into the array

int readArrayFromFile(const char *filename, int arr[]) {

FILE *file = fopen(filename, "r");

if (!file) {

printf("Error opening file\n");

return 0;

int i = 0;

while (fscanf(file, "%d", &arr[i]) != EOF) {

i++;

fclose(file);
 return i; // Return the number of elements read

int main() {

int n = 10000; // Array size (You can change it)

int arr[n];

char choice;

// Ask the user if they want to read from file or generate random numbers

printf("Do you want to read elements from a file (f) or generate randomly (r)? ");

scanf(" %c", &choice);

if (choice == 'f') {

char filename[100];

printf("Enter the filename: ");

scanf("%s", filename);

n = readArrayFromFile(filename, arr); // Read array from file

} else if (choice == 'r') {

generateRandomArray(arr, n); // Generate random numbers

} else {

printf("Invalid choice!\n");

return 1;

// Measure time for Quick Sort

clock_t start = clock();

quickSort(arr, 0, n - 1);

clock_t end = clock();

printf("Time taken to sort %d elements using Quick Sort: %lf seconds\n", n, (double)(end -
start) / CLOCKS_PER_SEC);

return 0;

}
/******************************OUTPUT************************************

[root@localhost vaibhavishelke]# vim ass2.c

[root@localhost vaibhavishelke]# gcc ass2.c

[root@localhost vaibhavishelke]# ./[Link]

Do you want to read elements from a file (f) or generate randomly (r)? r

Time taken to sort 10000 elements using Quick Sort: 0.001987 seconds

**************************************************************************/
/**************************************************************************

Name : Shelke Vaibhavi Vijay Roll No : 7402

Class : [Link](Computer Science)- I

Assignment No : 3

Assignment Name : Write a program in C/C++/ Java to implement a Merge Sort algorithm to
sort a given set of elements and determine the time required to sort the elements. Repeat
the experiment for different values of n, the number of elements in the list to be sorted. The
elements can be read from a file or can be generated using the random number generator.
*************************************************************************/

//ass3.c

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

// Function to merge two sub-arrays into one sorted array

void merge(int arr[], int left, int mid, int right) {

int n1 = mid - left + 1;

int n2 = right - mid;

int L[n1], R[n2]; // Temporary arrays to hold the left and right sub-arrays

// Copy data into temporary arrays

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

L[i] = arr[left + i];

for (int j = 0; j < n2; j++)

R[j] = arr[mid + 1 + j];

int i = 0, j = 0, k = left;

// Merge the temporary arrays back into the original array

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 Algorithm

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

if (left < right) {

int mid = left + (right - left) / 2;

// Recursively sort the two halves

mergeSort(arr, left, mid);

mergeSort(arr, mid + 1, right);

// Merge the sorted halves

merge(arr, left, mid, right);

}
// Function to generate an array of random numbers

void generateRandomArray(int arr[], int n) {

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

arr[i] = rand() % 10000; // Generate numbers between 0 and 9999

// Function to read integers from a file into the array

int readArrayFromFile(const char *filename, int arr[]) {

FILE *file = fopen(filename, "r");

if (!file) {

printf("Error opening file\n");

return 0;

int i = 0;

while (fscanf(file, "%d", &arr[i]) != EOF) {

i++;

fclose(file);

return i; // Return the number of elements read

int main() {

int n = 10000; // Array size (You can change it for different sizes)

int arr[n];

char choice;

// Ask the user if they want to read from file or generate random numbers

printf("Do you want to read elements from a file (f) or generate randomly (r)? ");

scanf(" %c", &choice);

if (choice == 'f') {

char filename[100];

printf("Enter the filename: ");

 scanf("%s", filename);

n = readArrayFromFile(filename, arr); // Read array from file

} else if (choice == 'r') {

generateRandomArray(arr, n); // Generate random numbers

} else {

printf("Invalid choice!\n");

return 1;

// Measure time for Merge Sort

clock_t start = clock();

mergeSort(arr, 0, n - 1);

clock_t end = clock();

printf("Time taken to sort %d elements using Merge Sort: %lf seconds\n", n, (double)(end
- start) / CLOCKS_PER_SEC);

return 0;

/******************************OUTPUT************************************

[root@localhost vaibhavishelke]# vim ass3.c

[root@localhost vaibhavishelke]# gcc ass3.c

[root@localhost vaibhavishelke]# ./[Link]

Do you want to read elements from a file (f) or generate randomly (r)? r

Time taken to sort 10000 elements using Merge Sort: 0.002682 seconds

**************************************************************************/
/**************************************************************************

Name : Shelke Vaibhavi Vijay Roll No : 7402

Class : [Link](Computer Science)- I

Assignment No : 4

Assignment Name : Write a program in C/C++/ Java to implement Strassen‟s Matrix

multiplication
*************************************************************************/

//ass4.c

#include <stdio.h>

#include <stdlib.h>

// Function to add two matrices

void add(int n, int A[n][n], int B[n][n], int result[n][n]) {

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

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

result[i][j] = A[i][j] + B[i][j];

// Function to subtract two matrices

void subtract(int n, int A[n][n], int B[n][n], int result[n][n]) {

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

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

result[i][j] = A[i][j] - B[i][j];

// Function to multiply two matrices

void multiply(int n, int A[n][n], int B[n][n], int result[n][n]) {

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

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

result[i][j] = 0;

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

result[i][j] += A[i][k] * B[k][j];

// Function to divide matrix into submatrices (for even dimension)

void divideMatrix(int n, int A[n][n], int A11[n/2][n/2], int A12[n/2][n/2], int A21[n/2][n/2],
int A22[n/2][n/2]) {

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

for (int j = 0; j < n / 2; j++) {

A11[i][j] = A[i][j];

A12[i][j] = A[i][j + n / 2];

A21[i][j] = A[i + n / 2][j];

A22[i][j] = A[i + n / 2][j + n / 2];

// Function to combine four submatrices into one matrix

void combineMatrix(int n, int C11[n/2][n/2], int C12[n/2][n/2], int C21[n/2][n/2], int

C22[n/2][n/2], int C[n][n]) {

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

for (int j = 0; j < n / 2; j++) {

C[i][j] = C11[i][j];

C[i][j + n / 2] = C12[i][j];

C[i + n / 2][j] = C21[i][j];

C[i + n / 2][j + n / 2] = C22[i][j];

 }

// Strassen's Matrix Multiplication

void strassen(int n, int A[n][n], int B[n][n], int C[n][n]) {

if (n == 1) {

C[0][0] = A[0][0] * B[0][0];

return;

int newSize = n / 2;

// Divide matrices into submatrices

int A11[newSize][newSize], A12[newSize][newSize], A21[newSize][newSize],

A22[newSize][newSize];

int B11[newSize][newSize], B12[newSize][newSize], B21[newSize][newSize],

B22[newSize][newSize];

divideMatrix(n, A, A11, A12, A21, A22);

divideMatrix(n, B, B11, B12, B21, B22);

// M1 = (A11 + A22) * (B11 + B22)

int A11_A22[newSize][newSize], B11_B22[newSize][newSize], M1[newSize][newSize];

add(newSize, A11, A22, A11_A22);

add(newSize, B11, B22, B11_B22);

strassen(newSize, A11_A22, B11_B22, M1);

// M2 = (A21 + A22) * B11

int A21_A22[newSize][newSize], M2[newSize][newSize];

add(newSize, A21, A22, A21_A22);

strassen(newSize, A21_A22, B11, M2);

// M3 = A11 * (B12 - B22)

int B12_B22[newSize][newSize], M3[newSize][newSize];

subtract(newSize, B12, B22, B12_B22);

strassen(newSize, A11, B12_B22, M3);

 // M4 = A22 * (B21 - B11)

int B21_B11[newSize][newSize], M4[newSize][newSize];

subtract(newSize, B21, B11, B21_B11);

strassen(newSize, A22, B21_B11, M4);

// M5 = (A11 + A12) * B22

int A11_A12[newSize][newSize], M5[newSize][newSize];

add(newSize, A11, A12, A11_A12);

strassen(newSize, A11_A12, B22, M5);

// M6 = (A21 - A11) * (B11 + B12)

int A21_A11[newSize][newSize], B11_B12[newSize][newSize], M6[newSize][newSize];

subtract(newSize, A21, A11, A21_A11);

add(newSize, B11, B12, B11_B12);

strassen(newSize, A21_A11, B11_B12, M6);

// M7 = (A12 - A22) * (B21 + B22)

int A12_A22[newSize][newSize], B21_B22[newSize][newSize], M7[newSize][newSize];

subtract(newSize, A12, A22, A12_A22);

add(newSize, B21, B22, B21_B22);

strassen(newSize, A12_A22, B21_B22, M7);

// Declare submatrices for C

int C11[newSize][newSize], C12[newSize][newSize], C21[newSize][newSize],

C22[newSize][newSize];

// C11 = M1 + M4 - M5 + M7

int C11_1[newSize][newSize], C11_2[newSize][newSize];

add(newSize, M1, M4, C11_1);

subtract(newSize, C11_1, M5, C11_2);

add(newSize, C11_2, M7, C11);

// C12 = M3 + M5

add(newSize, M3, M5, C12);

// C21 = M2 + M4

add(newSize, M2, M4, C21);

 // C22 = M1 - M2 + M3 + M6

int C22_1[newSize][newSize], C22_2[newSize][newSize];

subtract(newSize, M1, M2, C22_1);

add(newSize, C22_1, M3, C22_2);

add(newSize, C22_2, M6, C22);

// Combine the submatrices into the final result

combineMatrix(n, C11, C12, C21, C22, C);

// Function to print a matrix

void printMatrix(int n, int matrix[n][n]) {

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

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

printf("%d ", matrix[i][j]);

printf("\n");

// Driver program

int main() {

int n;

// Read the size of the matrix

printf("Enter the size of the matrix (n x n): ");

scanf("%d", &n);

int A[n][n], B[n][n], C[n][n];

// Read the matrices A and B

printf("Enter the elements of matrix A:\n");

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

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

scanf("%d", &A[i][j]);
 }

printf("Enter the elements of matrix B:\n");

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

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

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

// Perform Strassen's matrix multiplication

strassen(n, A, B, C);

// Print the result matrix C

printf("Result of matrix multiplication (C = A * B):\n");

printMatrix(n, C);

return 0;

/******************************OUTPUT************************************

[root@localhost vaibhavishelke]# vim ass4.c

[root@localhost vaibhavishelke]# gcc ass4.c

[root@localhost vaibhavishelke]# ./[Link]

Enter the size of the matrix (n x n): 2

Enter the elements of matrix A:

12

34

Enter the elements of matrix B:

56

78

Result of matrix multiplication (C = A * B):

19 22

43 50

**************************************************************************/
/**************************************************************************

Name : Shelke Vaibhavi Vijay Roll No : 7402

Class : [Link](Computer Science)- I

Assignment No : 5

Assignment Name : Write a program in C/C++/ Java to find Minimum Cost Spanning Tree of
a given undirected graph using Kruskal‟s algorithm.
*************************************************************************/

//ass5.c

#include <stdio.h>

#include <stdlib.h>

// Structure to represent an edge

typedef struct {

int u, v, weight;

} Edge;

// Structure to represent a subset for union-find

typedef struct {

int parent, rank;

} Subset;

// Function to compare two edges (used for sorting)

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

return ((Edge*)a)->weight - ((Edge*)b)->weight;

// Find function with path compression

int find(Subset subsets[], int i) {

if (subsets[i].parent != i) {

subsets[i].parent = find(subsets, subsets[i].parent);

return subsets[i].parent;
}

// Union function by rank

void unionSets(Subset subsets[], int xroot, int yroot) {

if (subsets[xroot].rank < subsets[yroot].rank) {

subsets[xroot].parent = yroot;

} else if (subsets[xroot].rank > subsets[yroot].rank) {

subsets[yroot].parent = xroot;

} else {

subsets[yroot].parent = xroot;

subsets[xroot].rank++;

// Kruskal's algorithm to find MST

void kruskal(int V, Edge edges[], int E) {

// Sort all edges in non-decreasing order of their weight

qsort(edges, E, sizeof(Edge), compareEdges);

// Create subsets for union-find

Subset *subsets = (Subset*)malloc(V * sizeof(Subset));

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

subsets[v].parent = v;

subsets[v].rank = 0;

// Result to store the MST

Edge result[V-1];

int e = 0; // Count of edges in MST

int i = 0; // Initial index of sorted edges

// Process edges

while (e < V - 1) {

Edge nextEdge = edges[i++];

int x = find(subsets, nextEdge.u);

 int y = find(subsets, nextEdge.v);

// If including this edge does not cause a cycle, include it in the result

if (x != y) {

result[e++] = nextEdge;

unionSets(subsets, x, y);

// Print the MST

printf("Edges in the Minimum Spanning Tree (MST):\n");

int minCost = 0;

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

printf("%d -- %d == %d\n", result[i].u, result[i].v, result[i].weight);

minCost += result[i].weight;

printf("\nMinimum Cost of Spanning Tree: %d\n", minCost);

// Free memory for subsets

free(subsets);

// Driver program to test Kruskal's algorithm

int main() {

int V, E;

// Read number of vertices and edges

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

scanf("%d %d", &V, &E);

// Create an array of edges

Edge *edges = (Edge*)malloc(E * sizeof(Edge));

printf("Enter the edges (u, v, weight):\n");

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

scanf("%d %d %d", &edges[i].u, &edges[i].v, &edges[i].weight);

 }

// Call Kruskal's algorithm

kruskal(V, edges, E);

// Free memory for edges

free(edges);

return 0;

/******************************OUTPUT************************************

[root@localhost vaibhavishelke]# vim ass5.c

[root@localhost vaibhavishelke]# gcc ass5.c

[root@localhost vaibhavishelke]# ./[Link]

Enter the number of vertices and edges: 4 5

Enter the edges (u, v, weight):

0 1 10

026

035

1 3 15

234

Edges in the Minimum Spanning Tree (MST):

2 -- 3 == 4

0 -- 3 == 5

0 -- 1 == 10

Minimum Cost of Spanning Tree: 19

**************************************************************************/
/**************************************************************************

Name : Shelke Vaibhavi Vijay Roll No : 7402

Class : [Link](Computer Science)- I

Assignment No : 6

Assignment Name : Write a program in C/C++/ Java to find Minimum Cost Spanning Tree of
a given undirected graph using Prim‟s algorithm
*************************************************************************/

//ass6.c

#include <stdio.h>

#include <limits.h>

#define MAX_VERTICES 100

// Function to find the vertex with the minimum key value that hasn't been included in MST

int minKey(int key[], int mstSet[], int V) {

int min = INT_MAX, minIndex;

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

if (mstSet[v] == 0 && key[v] < min) {

min = key[v];

minIndex = v;

return minIndex;

// Function to implement Prim's MST algorithm

void primMST(int graph[MAX_VERTICES][MAX_VERTICES], int V) {

int parent[V]; // Array to store constructed MST

int key[V]; // Key values used to pick minimum weight edge

int mstSet[V]; // To represent the set of vertices included in MST

// Initialize all keys as INFINITE

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

key[i] = INT_MAX;
 mstSet[i] = 0; // All vertices are not in MST initially

// Always include the first vertex in MST

key[0] = 0; // Make the key value of the first vertex 0 to pick it first

parent[0] = -1; // First node is the root of the MST

// The MST will have V vertices

for (int count = 0; count < V - 1; count++) {

// Pick the minimum key vertex from the set of vertices not yet included in MST

int u = minKey(key, mstSet, V);

// Add the picked vertex to the MST Set

mstSet[u] = 1;

// Update the key value and parent index of the adjacent vertices

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

// Update the key value of vertex v if it is not in MST, and there is an edge from u to v

if (graph[u][v] != 0 && mstSet[v] == 0 && graph[u][v] < key[v]) {

key[v] = graph[u][v];

parent[v] = u;

// Print the constructed MST

printf("Edge \tWeight\n");

int minCost = 0;

for (int i = 1; i < V; i++) {

printf("%d - %d \t%d\n", parent[i], i, graph[i][parent[i]]);

minCost += graph[i][parent[i]];

printf("\nMinimum Cost of Spanning Tree: %d\n", minCost);

// Driver program to test the above functions

int main() {

int V, E;

// Read number of vertices and edges

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

scanf("%d %d", &V, &E);

int graph[MAX_VERTICES][MAX_VERTICES];

// Initialize the graph with 0s

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

for (int j = 0; j < V; j++) {

graph[i][j] = 0;

// Read the edges of the graph

printf("Enter the edges (u, v, weight):\n");

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

int u, v, weight;

scanf("%d %d %d", &u, &v, &weight);

graph[u][v] = weight;

graph[v][u] = weight; // As the graph is undirected

// Call Prim's algorithm to find the MST

primMST(graph, V);

return 0;

}
/******************************OUTPUT************************************

[root@localhost vaibhavishelke]# vim ass6.c

[root@localhost vaibhavishelke]# gcc ass6.c

[root@localhost vaibhavishelke]# ./[Link]

Enter the number of vertices and edges: 5 7

Enter the edges (u, v, weight):

012

036

138

123

235

247

349

Edge Weight

0-1 2

1-2 3

2-3 5

2-4 7

Minimum Cost of Spanning Tree: 17

**************************************************************************/
/**************************************************************************

Name : Shelke Vaibhavi Vijay Roll No : 7402

Class : [Link](Computer Science)- I

Assignment No : 7

Assignment Name : Write a program in C/C++/ Java to from a given vertex in a weighted
connected graph, find shortest paths to other vertices using Dijikstra‟s algorithm
*************************************************************************/

//ass7.c

#include <stdio.h>

#include <limits.h>

#define MAX_VERTICES 100

#define INF INT_MAX

// Function to find the vertex with the minimum distance that hasn't been visited

int minDistance(int dist[], int visited[], int V) {

int min = INF, minIndex;

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

if (visited[v] == 0 && dist[v] <= min) {

min = dist[v];

minIndex = v;

return minIndex;

// Function to implement Dijkstra's algorithm to find the shortest paths

void dijkstra(int graph[MAX_VERTICES][MAX_VERTICES], int V, int source) {

int dist[V]; // Array to store the shortest distance from the source to each vertex

int visited[V]; // Array to keep track of visited vertices

// Initialize distances as infinite and visited as false

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

dist[i] = INF;
 visited[i] = 0;

// Distance to the source is 0

dist[source] = 0;

// Find the shortest path for all vertices

for (int count = 0; count < V - 1; count++) {

// Get the vertex with the minimum distance from the unvisited set

int u = minDistance(dist, visited, V);

// Mark the selected vertex as visited

visited[u] = 1;

// Update the distance for all adjacent vertices of the selected vertex

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

// Update dist[v] if and only if the edge u-v exists, v is not visited,

// and the total weight of path through u is smaller than the current dist[v]

if (graph[u][v] != 0 && visited[v] == 0 && dist[u] != INF && dist[u] + graph[u][v] <
dist[v]) {

dist[v] = dist[u] + graph[u][v];

// Print the shortest distance from source to all other vertices

printf("Vertex \t Distance from Source (%d)\n", source);

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

if (dist[i] == INF) {

printf("%d \t INF\n", i);

} else {

printf("%d \t %d\n", i, dist[i]);

}
// Driver program to test Dijkstra's algorithm

int main() {

int V, E;

// Read number of vertices and edges

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

scanf("%d %d", &V, &E);

int graph[MAX_VERTICES][MAX_VERTICES] = {0};

// Read the edges of the graph

printf("Enter the edges (u, v, weight):\n");

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

int u, v, weight;

scanf("%d %d %d", &u, &v, &weight);

graph[u][v] = weight;

graph[v][u] = weight; // Since the graph is undirected

int source;

printf("Enter the source vertex: ");

scanf("%d", &source);

// Call Dijkstra's algorithm

dijkstra(graph, V, source);

return 0;

}
/******************************OUTPUT************************************

[root@localhost vaibhavishelke]# vim ass7.c

[root@localhost vaibhavishelke]# gcc ass7.c

[root@localhost vaibhavishelke]# ./[Link]

Enter the number of vertices and edges: 5 7

Enter the edges (u, v, weight):

0 1 10

025

122

131

239

242

344

Enter the source vertex: 0

Vertex Distance from Source (0)

0 0

1 7

2 5

3 8

4 7

**************************************************************************/
/**************************************************************************

Name : Shelke Vaibhavi Vijay Roll No : 7402

Class : [Link](Computer Science)- I

Assignment No : 8

Assignment Name : Write a program in C/C++/ Java to implement Knapsack problems using
Greedy method
*************************************************************************/

//ass8.c

#include <stdio.h>

#include <stdlib.h>

typedef struct {

int weight, value;

float ratio;

} Item;

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

return ((Item*)b)->ratio - ((Item*)a)->ratio;

float fractionalKnapsack(int W, Item items[], int n) {

qsort(items, n, sizeof(Item), compare);

float totalValue = 0;

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

if (items[i].weight <= W) {

totalValue += items[i].value;

W -= items[i].weight;

} else {

totalValue += items[i].value * ((float)W / items[i].weight);

break;

return totalValue;
}

int main() {

int n, W;

printf("Enter number of items and knapsack capacity: ");

scanf("%d %d", &n, &W);

Item items[n];

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

printf("Enter weight and value for item %d: ", i + 1);

scanf("%d %d", &items[i].weight, &items[i].value);

items[i].ratio = (float)items[i].value / items[i].weight;

printf("Maximum value: %.2f\n", fractionalKnapsack(W, items, n));

return 0;

/******************************OUTPUT************************************

[root@localhost vaibhavishelke]# vim ass8.c

[root@localhost vaibhavishelke]# gcc ass8.c

[root@localhost vaibhavishelke]# ./[Link]

Enter number of items and knapsack capacity: 3 50

Enter weight and value for item 1: 10 60

Enter weight and value for item 2: 20 100

Enter weight and value for item 3: 30 120

Maximum value: 240.00

**************************************************************************/
/**************************************************************************

Name : Shelke Vaibhavi Vijay Roll No : 7402

Class : [Link](Computer Science)- I

Assignment No : 9

Assignment Name : Write a program in C/C++/ Java to implement optimal binary search
tree and also calculate the best case and worst case complexity
*************************************************************************/

//ass9.c

#include <stdio.h>

#include <limits.h>

#define MAX 100

void optimalBST(int keys[], int freq[], int n) {

int cost[MAX][MAX], sum[MAX][MAX];

// Initialize cost and sum arrays

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

cost[i][i] = freq[i];

sum[i][i] = freq[i];

// Calculate the cost for ranges of increasing length

for (int len = 2; len <= n; len++) {

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

int j = i + len - 1;

cost[i][j] = INT_MAX;

sum[i][j] = sum[i][j-1] + freq[j];

// Try every possible root r

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

int left = (r > i) ? cost[i][r-1] : 0;

int right = (r < j) ? cost[r+1][j] : 0;

int totalCost = left + right + sum[i][j];

if (totalCost < cost[i][j]) cost[i][j] = totalCost;

 }

// Output the minimum cost for the optimal BST

printf("Minimum cost of the Optimal BST: %d\n", cost[0][n-1]);

int main() {

int keys[] = {10, 12, 20}; // keys

int freq[] = {34, 8, 50}; // frequencies

int n = sizeof(keys) / sizeof(keys[0]);

optimalBST(keys, freq, n);

return 0;

/******************************OUTPUT************************************

[root@localhost vaibhavishelke]# vim ass9.c

[root@localhost vaibhavishelke]# gcc ass9.c

[root@localhost vaibhavishelke]# ./[Link]

Minimum cost of the Optimal BST: 142

**************************************************************************/
/**************************************************************************

Name : Shelke Vaibhavi Vijay Roll No : 7402

Class : [Link](Computer Science)- I

Assignment No : 10

Assignment Name : Write a program in C/C++/ Java to implement huffman Code using
greedy methods and also calculate the best case and worst case complexity
*************************************************************************/

//ass10.c

#include <stdio.h>

#include <stdlib.h>

struct Node {

char data;

int freq;

struct Node *left, *right;

};

struct MinHeap {

int size;

struct Node* array[100];

};

struct Node* newNode(char data, int freq) {

struct Node* temp = (struct Node*)malloc(sizeof(struct Node));

temp->data = data;

temp->freq = freq;

temp->left = temp->right = NULL;

return temp;

void minHeapify(struct MinHeap* minHeap, int idx) {

int smallest = idx;

int left = 2*idx + 1;

int right = 2*idx + 2;

 if (left < minHeap->size && minHeap->array[left]->freq < minHeap->array[smallest]->freq)

smallest = left;

if (right < minHeap->size && minHeap->array[right]->freq < minHeap->array[smallest]-

>freq)

smallest = right;

if (smallest != idx) {

struct Node* temp = minHeap->array[idx];

minHeap->array[idx] = minHeap->array[smallest];

minHeap->array[smallest] = temp;

minHeapify(minHeap, smallest);

void buildMinHeap(struct MinHeap* minHeap) {

for (int i = (minHeap->size / 2) - 1; i >= 0; i--) {

minHeapify(minHeap, i);

struct Node* buildHuffmanTree(char data[], int freq[], int size) {

struct MinHeap* minHeap = (struct MinHeap*)malloc(sizeof(struct MinHeap));

minHeap->size = size;

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

minHeap->array[i] = newNode(data[i], freq[i]);

buildMinHeap(minHeap);

while (minHeap->size > 1) {

struct Node *left = minHeap->array[0];

struct Node *right = minHeap->array[1];

struct Node *top = newNode('$', left->freq + right->freq);

top->left = left;

top->right = right;
 minHeap->array[0] = top;

minHeap->size--;

minHeapify(minHeap, 0);

return minHeap->array[0];

int main() {

char data[] = {'a', 'b', 'c', 'd', 'e', 'f'};

int freq[] = {5, 9, 12, 13, 16, 45};

int size = sizeof(data) / sizeof(data[0]);

struct Node* root = buildHuffmanTree(data, freq, size);

printf("Huffman Tree Built.\n");

return 0;

/******************************OUTPUT************************************

[root@localhost vaibhavishelke]# vim ass10.c

[root@localhost vaibhavishelke]# gcc ass10.c

[root@localhost vaibhavishelke]# ./[Link]

Huffman Tree Built.

**************************************************************************/
/**************************************************************************

Name : Shelke Vaibhavi Vijay Roll No : 7402

Class : [Link](Computer Science)- I

Assignment No : 11

Assignment Name : Write a program in C/C++/ Java to find Minimum number of

multiplications in Matrix Chain Multiplication
*************************************************************************/

//ass11.c

#include <stdio.h>

#include <limits.h>

#define MAX 10

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

int m[MAX][MAX];

for (int i = 1; i < n; i++) m[i][i] = 0;

for (int len = 2; len < n; len++) {

for (int i = 1; i < n - len + 1; i++) {

int j = i + len - 1;

m[i][j] = INT_MAX;

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

int 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 arr[] = {1, 2, 3, 4, 3};

int n = sizeof(arr)/sizeof(arr[0]);

printf("Minimum number of multiplications: %d\n", matChainOrder(arr, n));

 return 0;

/******************************OUTPUT************************************

[root@localhost vaibhavishelke]# vim ass11.c

[root@localhost vaibhavishelke]# gcc ass11.c

[root@localhost vaibhavishelke]# ./[Link]

Minimum number of multiplications: 30

**************************************************************************/
/**************************************************************************

Name : Shelke Vaibhavi Vijay Roll No : 7402

Class : [Link](Computer Science)- I

Assignment No : 12

Assignment Name : Write a Program in C/C++/Java to find only length of Longest Common
Subsequence
*************************************************************************/

//ass12.c

#include <stdio.h>

#include <string.h>

#define MAX 100

int lcsLength(char X[], char Y[]) {

int m = strlen(X), n = strlen(Y);

int L[MAX][MAX];

for (int i = 0; i <= m; i++) L[i][0] = 0;

for (int j = 0; j <= n; j++) L[0][j] = 0;

for (int i = 1; i <= m; i++) {

for (int j = 1; j <= n; j++) {

if (X[i-1] == Y[j-1]) L[i][j] = L[i-1][j-1] + 1;

else L[i][j] = (L[i-1][j] > L[i][j-1]) ? L[i-1][j] : L[i][j-1];

return L[m][n];

int main() {

char X[] = "ABCBDAB";

char Y[] = "BDCABB";

printf("Length of LCS: %d\n", lcsLength(X, Y));

return 0;

}
/******************************OUTPUT************************************

[root@localhost vaibhavishelke]# vim ass12.c

[root@localhost vaibhavishelke]# gcc ass12.c

[root@localhost vaibhavishelke]# ./[Link]

Length of LCS: 4

**************************************************************************/
/**************************************************************************

Name : Shelke Vaibhavi Vijay Roll No : 7402

Class : [Link](Computer Science)- I

Assignment No : 13

Assignment Name :Write programs in C/C++/ Java to implement DFS and BFS. Compare the
time complexity
*************************************************************************/

//ass13.c

#include <stdio.h>

#include <stdlib.h>

#define MAX 10

int adj[MAX][MAX], visited[MAX], n;

void DFS(int v) {

visited[v] = 1; // Mark the node as visited

printf("%d ", v); // Output the node

// Visit all unvisited neighbors

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

if (adj[v][i] == 1 && !visited[i]) {

DFS(i);

void BFS(int start) {

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

visited[start] = 1;

queue[++rear] = start; // Enqueue the start node

while (front != rear) {

int v = queue[++front]; // Dequeue a node

printf("%d ", v); // Output the node

// Visit all unvisited neighbors and enqueue them

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

if (adj[v][i] == 1 && !visited[i]) {

visited[i] = 1;

queue[++rear] = i; // Enqueue unvisited node

int main() {

printf("Enter number of vertices: ");

scanf("%d", &n);

// Initialize visited array to 0

for (int i = 0; i < n; i++) visited[i] = 0;

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

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

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

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

printf("\nDFS starting from vertex 0: ");

DFS(0); // Call DFS from vertex 0

// Reset visited array before BFS

for (int i = 0; i < n; i++) visited[i] = 0;

printf("\n\nBFS starting from vertex 0: ");

BFS(0); // Call BFS from vertex 0

return 0;

}
/******************************OUTPUT************************************

[root@localhost vaibhavishelke]# vim ass13.c

[root@localhost vaibhavishelke]# gcc ass13.c

[root@localhost vaibhavishelke]# ./[Link]

Enter number of vertices: 5

Enter adjacency matrix:

01000

10110

01001

01001

00110

DFS starting from vertex 0: 0 1 2 4 3

BFS starting from vertex 0: 0 1 2 3 4

**************************************************************************/
/**************************************************************************

Name : Shelke Vaibhavi Vijay Roll No : 7402

Class : [Link](Computer Science)- I

Assignment No : 14

Assignment Name : Write a program in C/C++/ Java for finding Topological sorting for
Directed Acyclic Graph (DAG)
*************************************************************************/

//ass14.c

#include <stdio.h>

#include <stdlib.h>

#define MAX 10

int graph[MAX][MAX], visited[MAX], stack[MAX], top = -1;

void dfs(int v, int n) {

visited[v] = 1;

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

if (graph[v][i] == 1 && !visited[i]) dfs(i, n);

stack[++top] = v;

int main() {

int n = 4;

graph[0][1] = graph[1][2] = graph[2][3] = 1;

for (int i = 0; i < n; i++) visited[i] = 0;

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

if (!visited[i]) dfs(i, n);

printf("Topological Sort: ");

for (int i = top; i >= 0; i--) printf("%d ", stack[i]);

return 0;

}
/******************************OUTPUT************************************

[root@localhost vaibhavishelke]# vim ass14.c

[root@localhost vaibhavishelke]# gcc ass14.c

[root@localhost vaibhavishelke]# ./[Link]

Topological Sort: 0 1 2 3

**************************************************************************/
/**************************************************************************

Name : Shelke Vaibhavi Vijay Roll No : 7402

Class : [Link](Computer Science)- I

Assignment No : 15

Assignment Name : Write a program in C/C++/ Java to determine if a given graph is a

Hamiltonian cycle or not
*************************************************************************/

//ass15.c

#include <stdio.h>

#define V 5

int graph[V][V], path[V];

int isSafe(int v, int pos) {

if (graph[path[pos-1]][v] == 0) return 0;

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

if (path[i] == v) return 0;

return 1;

int hamiltonianCycle(int pos) {

if (pos == V) {

if (graph[path[pos-1]][path[0]] == 1) return 1;

return 0;

for (int v = 1; v < V; v++) {

if (isSafe(v, pos)) {

path[pos] = v;

if (hamiltonianCycle(pos + 1)) return 1;

path[pos] = -1;

}
 return 0;

int main() {

for (int i = 0; i < V; i++) path[i] = -1;

graph[0][1] = graph[1][2] = graph[2][3] = graph[3][4] = graph[4][0] = 1;

path[0] = 0;

if (hamiltonianCycle(1)) {

printf("Hamiltonian Cycle: ");

for (int i = 0; i < V; i++) printf("%d ", path[i]);

} else {

printf("No Hamiltonian Cycle");

return 0;

/******************************OUTPUT************************************

[root@localhost vaibhavishelke]# vim ass15.c

[root@localhost vaibhavishelke]# gcc ass15.c

[root@localhost vaibhavishelke]# ./[Link]

Hamiltonian Cycle: 0 1 2 3 4

**************************************************************************/
/**************************************************************************

Name : Shelke Vaibhavi Vijay Roll No : 7402

Class : [Link](Computer Science)- I

Assignment No : 16

Assignment Name : Write a Java Program in C/C++/ Java to implement Traveling Salesman
Problem using nearest neighbor algorithm
*************************************************************************/

//ass16.c

#include <stdio.h>

#include <limits.h>

#define V 4

int dist[V][V] = { {0, 10, 15, 20},

{10, 0, 35, 25},

{15, 35, 0, 30},

{20, 25, 30, 0} };

int visited[V] = {0};

int tsp(int curr_pos, int count, int cost, int start) {

if (count == V && dist[curr_pos][start]) {

return cost + dist[curr_pos][start];

int ans = INT_MAX;

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

if (!visited[i] && dist[curr_pos][i]) {

visited[i] = 1;

ans = (ans < tsp(i, count+1, cost + dist[curr_pos][i], start)) ? ans : tsp(i, count+1, cost +
dist[curr_pos][i], start);

visited[i] = 0;

return ans;

}
int main() {

visited[0] = 1;

printf("Minimum cost: %d", tsp(0, 1, 0, 0));

return 0;

/******************************OUTPUT************************************

[root@localhost vaibhavishelke]#vim ass16.c

[root@localhost vaibhavishelke]# gcc ass16.c

[root@localhost vaibhavishelke]# ./[Link]

Minimum cost: 80

**************************************************************************/
/**************************************************************************

Name : Shelke Vaibhavi Vijay Roll No : 7402

Class : [Link](Computer Science)- I

Assignment No : 17

Assignment Name : Write a program in C/C++/ Java a to implement Graph Coloring

Algorithm
*************************************************************************/

//ass17.c

#include <stdio.h>

#define V 4

int graph[V][V] = { {0, 1, 1, 0},

{1, 0, 1, 1},

{1, 1, 0, 1},

{0, 1, 1, 0} };

int color[V] = {0};

int isSafe(int v, int c) {

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

if (graph[v][i] == 1 && c == color[i]) return 0;

return 1;

int graphColoring(int m, int v) {

if (v == V) return 1;

for (int c = 1; c <= m; c++) {

if (isSafe(v, c)) {

color[v] = c;

if (graphColoring(m, v + 1)) return 1;

color[v] = 0;

}
 return 0;

int main() {

int m = 3; // Number of colors

if (graphColoring(m, 0)) {

printf("Solution exists with coloring: ");

for (int i = 0; i < V; i++) printf("%d ", color[i]);

} else {

printf("No solution");

return 0;

/******************************OUTPUT************************************

[root@localhost vaibhavishelke]# vim ass17.c

[root@localhost vaibhavishelke]# gcc ass17.c

[root@localhost vaibhavishelke]# ./[Link]

Solution exists with coloring: 1 2 3 1

**************************************************************************/
/**************************************************************************

Name : Shelke Vaibhavi Vijay Roll No : 7402

Class : [Link](Computer Science)- I

Assignment No : 18

Assignment Name : Write a program in C/C++/ Java to implement Sum of Subset by

Backtracking
*************************************************************************/

//ass18.c

#include <stdio.h>

int set[] = {3, 34, 4, 12, 5, 2};

int sum = 9;

int isSubsetSum(int n, int sum) {

if (sum == 0) return 1;

if (n == 0 && sum != 0) return 0;

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

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

int main() {

if (isSubsetSum(6, sum)) printf("Subset with given sum found.");

else printf("No subset with given sum.");

return 0;

/******************************OUTPUT************************************

[root@localhost vaibhavishelke]# vim ass18.c

[root@localhost vaibhavishelke]# gcc ass18.c

[root@localhost vaibhavishelke]# ./[Link]

Subset with given sum found.

**************************************************************************/
/**************************************************************************

Name : Shelke Vaibhavi Vijay Roll No : 7402

Class : [Link](Computer Science)- I

Assignment No : 19

Assignment Name : Write a program in C/C++/ Java to solve N Queens Problem using
Backtracking
*************************************************************************/

//ass19.c

#include <stdio.h>

#define N 4

int board[N][N];

int isSafe(int row, int col) {

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

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

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

return 1;

int solveNQ(int col) {

if (col == N) return 1;

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

if (isSafe(i, col)) {

board[i][col] = 1;

if (solveNQ(col + 1)) return 1;

board[i][col] = 0;

return 0;

int main() {

if (solveNQ(0)) {
 for (int i = 0; i < N; i++) {

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

printf("\n");

} else printf("Solution does not exist.");

return 0;

/******************************OUTPUT************************************

[root@localhost vaibhavishelke]# vim ass19.c

[root@localhost vaibhavishelke]# gcc ass19.c

[root@localhost vaibhavishelke]# ./[Link]

0010

1000

0001

0100

**************************************************************************/
/**************************************************************************

Name : Shelke Vaibhavi Vijay Roll No : 7402

Class : [Link](Computer Science)- I

Assignment No : 20

Assignment Name : Write a program in C/C++/ Java to solve 4 Queens Problem using
Backtracking
*************************************************************************/

//ass20.c

#include <stdio.h>

#define N 4

int board[N][N];

int isSafe(int row, int col) {

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

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

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

return 1;

int solveNQ(int col) {

if (col == N) return 1;

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

if (isSafe(i, col)) {

board[i][col] = 1;

if (solveNQ(col + 1)) return 1;

board[i][col] = 0;

return 0;

int main() {

if (solveNQ(0)) {
 for (int i = 0; i < N; i++) {

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

printf("\n");

} else printf("Solution does not exist.");

return 0;

/******************************OUTPUT************************************

[root@localhost vaibhavishelke]# vim ass20.c

[root@localhost vaibhavishelke]# gcc ass20.c

[root@localhost vaibhavishelke]# ./[Link]

0010

1000

0001

0100

**************************************************************************/
/**************************************************************************

Name : Shelke Vaibhavi Vijay Roll No : 7402

Class : [Link](Computer Science)- I

Assignment No : 21

Assignment Name : Write a program in C/C++/ Java to show board configuration of 4 queens
problem
*************************************************************************/

//ass21.c

#include <stdio.h>

#define N 4

int board[N][N];

int isSafe(int row, int col) {

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

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

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

return 1;

int solveNQ(int col) {

if (col == N) return 1;

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

if (isSafe(i, col)) {

board[i][col] = 1;

if (solveNQ(col + 1)) return 1;

board[i][col] = 0;

return 0;

int main() {

if (solveNQ(0)) {
 for (int i = 0; i < N; i++) {

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

printf("\n");

} else printf("Solution does not exist.");

return 0;

/******************************OUTPUT************************************

[root@localhost vaibhavishelke]# vim ass21.c

[root@localhost vaibhavishelke]# gcc ass21.c

[root@localhost vaibhavishelke]# ./[Link]

0010

1000

0001

0100

**************************************************************************/
/**************************************************************************

Name : Shelke Vaibhavi Vijay Roll No : 7402

Class : [Link](Computer Science)- I

Assignment No : 22

Assignment Name : Write a program in C/C++/ Java to find out longest common
subsequence from the given strings
*************************************************************************/

//ass22.c

#include <stdio.h>

#include <string.h>

#define MAX 100

int lcsLength(char X[], char Y[]) {

int m = strlen(X), n = strlen(Y);

int L[MAX][MAX];

for (int i = 0; i <= m; i++) L[i][0] = 0;

for (int j = 0; j <= n; j++) L[0][j] = 0;

for (int i = 1; i <= m; i++) {

for (int j = 1; j <= n; j++) {

if (X[i-1] == Y[j-1]) L[i][j] = L[i-1][j-1] + 1;

else L[i][j] = (L[i-1][j] > L[i][j-1]) ? L[i-1][j] : L[i][j-1];

return L[m][n];

int main() {

char X[] = "ABCBDAB";

char Y[] = "BDCABB";

printf("Length of LCS: %d\n", lcsLength(X, Y));

return 0;

}
/******************************OUTPUT************************************

[root@localhost vaibhavishelke]# vim ass22.c

[root@localhost vaibhavishelke]# gcc ass22.c

[root@localhost vaibhavishelke]# ./[Link]

Length of LCS: 4

**************************************************************************/
/**************************************************************************

Name : Shelke Vaibhavi Vijay Roll No : 7402

Class : [Link](Computer Science)- I

Assignment No : 23

Assignment Name : Write a program in C/C++/ Java to find out live node, E node and dead
node from a given graph
*************************************************************************/

//ass23.c

#include <stdio.h>

#include <stdlib.h>

#define V 5

int graph[V][V] = {{0, 1, 0, 1, 0},

{1, 0, 1, 1, 0},

{0, 1, 0, 0, 1},

{1, 1, 0, 0, 1},

{0, 0, 1, 1, 0}};

int visited[V] = {0};

void dfs(int v) {

visited[v] = 1;

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

if (graph[v][i] == 1 && !visited[i]) {

dfs(i);

int main() {

for (int i = 0; i < V; i++) visited[i] = 0;

// Perform DFS from node 0

dfs(0);

printf("Live nodes: ");

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

if (visited[i]) printf("%d ", i);

printf("\nDead nodes: ");

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

if (!visited[i]) printf("%d ", i);

return 0;

/******************************OUTPUT************************************

[root@localhost vaibhavishelke]# vim ass23.c

[root@localhost vaibhavishelke]# gcc ass23.c

[root@localhost vaibhavishelke]# ./[Link]

Live nodes: 0 1 2 3 4

Dead nodes:

**************************************************************************/
/**************************************************************************

Name : Shelke Vaibhavi Vijay Roll No : 7402

Class : [Link](Computer Science)- I

Assignment No : 24

Assignment Name : Write a program in C/C++/ Java to find out solution for travelling
salesman problem using LCBB from a given matrix
*************************************************************************/

//ass24.c

#include <stdio.h>

#include <limits.h>

#define V 4

int dist[V][V] = { {0, 10, 15, 20},

{10, 0, 35, 25},

{15, 35, 0, 30},

{20, 25, 30, 0} };

int visited[V] = {0};

int min_cost = INT_MAX;

void tsp(int curr_pos, int count, int cost, int start) {

if (count == V && dist[curr_pos][start]) {

min_cost = (cost + dist[curr_pos][start] < min_cost) ? cost + dist[curr_pos][start] :

min_cost;

return;

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

if (!visited[i] && dist[curr_pos][i]) {

visited[i] = 1;

tsp(i, count + 1, cost + dist[curr_pos][i], start);

visited[i] = 0;

}
int main() {

visited[0] = 1;

tsp(0, 1, 0, 0);

printf("Minimum cost: %d\n", min_cost);

return 0;

/******************************OUTPUT************************************

[root@localhost vaibhavishelke]# vim ass24.c

[root@localhost vaibhavishelke]# gcc ass24.c

[root@localhost vaibhavishelke]# ./[Link]

Minimum cost: 80

**************************************************************************/
/**************************************************************************

Name : Shelke Vaibhavi Vijay Roll No : 7402

Class : [Link](Computer Science)- I

Assignment No : 25

Assignment Name : Write a program in C/C++/ Java to find out solution for 0/1 knapsack
problem
*************************************************************************/

//ass25.c

#include <stdio.h>

#define MAX 100

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

int K[MAX][MAX];

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

for (int w = 0; w <= W; w++) {

if (i == 0 || w == 0) K[i][w] = 0;

else if (wt[i-1] <= w) K[i][w] = (val[i-1] + K[i-1][w-wt[i-1]] > K[i-1][w]) ? 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];

int main() {

int val[] = {60, 100, 120};

int wt[] = {10, 20, 30};

int W = 50;

int n = sizeof(val)/sizeof(val[0]);

printf("Maximum value: %d\n", knapsack(W, wt, val, n));

return 0;

}
/******************************OUTPUT************************************

[root@localhost vaibhavishelke]# vim ass25.c

[root@localhost vaibhavishelke]# gcc ass25.c

[root@localhost vaibhavishelke]# ./[Link]

Maximum value: 220

**************************************************************************/