Experiment 1

Program for Recursive Binary & Linear Search

Code 1 : Recursive Linear Search
#include <stdio.h>
int linearSearch(int arr[], int n, int key, int index) {
if (index == n) {
return -1;
}
if (arr[index] == key){
return index;
}
return linearSearch(arr, n, key, index + 1);
}
int main() {
int n, key;
printf("Enter number of elements: ");
scanf("%d", &n);
int arr[n];
printf("Enter elements: ");
for (int i = 0; i < n; i++){
scanf("%d", &arr[i]);
}
printf("Enter element to search: ");
scanf("%d", &key);
int result = linearSearch(arr, n, key, 0);
if (result != -1){
printf("Element found at index: %d\n", result);
}
else{
printf("Element not found.\n");
}
return 0;

1
Shivam Kumar
23049215210171
 }

Output :

2
Shivam Kumar
23049215210171
Code 2 : Recursive Binary Search
#include <stdio.h>
int binarySearch(int arr[], int low, int high, int key) {
if (low > high){
return -1;
}
int mid = (low + high) / 2;
if (arr[mid] == key)
return mid;
else if (arr[mid] > key)
return binarySearch(arr, low, mid - 1, key);
else
return binarySearch(arr, mid + 1, high, key);
}
int main() {
int n, key;
printf("Enter number of elements: ");
scanf("%d", &n);
int arr[n];
printf("Enter sorted elements: ");
for (int i = 0; i < n; i++)
scanf("%d", &arr[i]);
printf("Enter element to search: ");
scanf("%d", &key);
int result = binarySearch(arr, 0, n - 1, key);
if (result != -1)
printf("Element found at index: %d\n", result);
else
printf("Element not found.\n");

return 0;
}

3
Shivam Kumar
23049215210171
Output :

4
Shivam Kumar
23049215210171
 Experiment 2
Program for Heap Sort by Taking Input From User

Code :
#include <stdio.h>
void heapify(int arr[], int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, n, largest);
}
}

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

for (int i = n / 2 - 1; i >= 0; i--){
heapify(arr, n, i);
}
for (int i = n - 1; i >= 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;

5
Shivam Kumar
23049215210171
 heapify(arr, i, 0);
}
}

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

int arr[n];
printf("Enter elements: ");
for (int i = 0; i < n; i++){
scanf("%d", &arr[i]);
}
printf("\n");
printf("Sorted array : ");
for (int i = 0; i < n; i++){
printf("%d ", arr[i]);
}
printf("\n");
heapSort(arr, n);

printf("Sorted array : ");

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

return 0;
}

6
Shivam Kumar
23049215210171
Output :

7
Shivam Kumar
23049215210171
 Experiment 3
Program for Merge Sort by Taking Input From User
Code :
#include <stdio.h>
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int L[n1], R[n2];
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;
while (i < n1 && j < n2) {
if (L[i] <= R[j]){
arr[k++] = L[i++];
}else{
arr[k++] = R[j++];
}
}
while (i < n1){
arr[k++] = L[i++];
}
while (j < n2){

8
Shivam Kumar
23049215210171
 arr[k++] = R[j++];
}
}

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

if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
int main() {
int n;
printf("Enter number of elements: ");
scanf("%d", &n);
int arr[n];
printf("Enter elements: ");
for (int i = 0; i < n; i++){
scanf("%d", &arr[i]);
}
printf("\n");
printf("Sorted array : ");
for (int i = 0; i < n; i++){
printf("%d ", arr[i]);
}
printf("\n");
mergeSort(arr, n);

printf("Sorted array : ");

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

9
Shivam Kumar
23049215210171
 printf("%d ", arr[i]);
}
printf("\n");

return 0;
}

Output :

10
Shivam Kumar
23049215210171
 Experiment 4
Program for Selection Sort by Taking Input From User
Code :
#include <stdio.h>
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex])
minIndex = j;
}
if (minIndex != i) {
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}

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

11
Shivam Kumar
23049215210171
 int arr[n];
printf("Enter elements: ");
for (int i = 0; i < n; i++){
scanf("%d", &arr[i]);
}
printf("\n");
printf("Sorted array : ");
for (int i = 0; i < n; i++){
printf("%d ", arr[i]);
}
printf("\n");
selectionSort(arr, n);

printf("Sorted array : ");

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

return 0;
}

Output :

12
Shivam Kumar
23049215210171
 Experiment 5
Program for Insertion Sort by Taking Input From User
Code :
#include <stdio.h>
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}

13
Shivam Kumar
23049215210171
 }
int main() {
int n;
printf("Enter number of elements: ");
scanf("%d", &n);
int arr[n];
printf("Enter elements: ");
for (int i = 0; i < n; i++){
scanf("%d", &arr[i]);
}
printf("\n");
printf("Sorted array : ");
for (int i = 0; i < n; i++){
printf("%d ", arr[i]);
}
printf("\n");
insertionSort(arr, n);

printf("Sorted array : ");

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

Output :

14
Shivam Kumar
23049215210171
 Experiment 6
Program for Quick Sort by Taking Input From User
Code :
#include <stdio.h>
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;

15
Shivam Kumar
23049215210171
 }
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = low - 1;

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

if (arr[j] < pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}

swap(&arr[i + 1], &arr[high]);

return (i + 1);
}

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

if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}

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

int arr[n];
printf("Enter elements: ");
for (int i = 0; i < n; i++){
scanf("%d", &arr[i]);

16
Shivam Kumar
23049215210171
 }
printf("\n");
printf("Sorted array : ");
for (int i = 0; i < n; i++){
printf("%d ", arr[i]);
}
printf("\n");
quickSort(arr, n);

printf("Sorted array : ");

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

return 0;
}

Output :

17
Shivam Kumar
23049215210171
 18
Shivam Kumar
23049215210171
 Experiment 7
Program of Knapsack Problem using Greedy Solution by taking input from User
Code :
#include <stdio.h>
struct item {
int profit, weight;
};
void sortitems(struct item arr[],int n){
for (int i=0;i<n-1;i++){
for(int j=i+1;j<n;j++){
double ratio1=(double)arr[i].profit/arr[i].weight;
double ratio2=(double)arr[j].profit/arr[j].weight;
if(ratio1<ratio2){
struct item temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
}
}
void knapsack(int capacity,struct item arr[],int n){
sortitems(arr,n);
double overallprofit=0;
for(int i=0;i<n;i++){
if(arr[i].weight<capacity){
capacity-=arr[i].weight;
overallprofit+=arr[i].profit;
}else{
overallprofit+=(arr[i].profit * (double)capacity/arr[i].weight);
break;
}
}
printf("Profit Over All is : %f",overallprofit);

19
Shivam Kumar
23049215210171
 }
int main() {
int n, cap;
printf("Enter number of items: ");
scanf("%d", &n);
struct item arr[n];
printf("Enter profit and weight of each item:\n");
for (int i = 0; i < n; i++) {
scanf("%d %d", &arr[i].profit, &arr[i].weight);
}
printf("Enter capacity of knapsack: ");
scanf("%d", &cap);

knapsack(cap, arr, n);

return 0;
}

Output :

20
Shivam Kumar
23049215210171
 Experiment 8
Program of finding Minimum Spanning Tree using Kruskal’s Algorithm by
taking Input from User

Code :
#include <stdio.h>
#define MAX 100
struct Edge {
int src, dest, weight;
};
struct Subset {
int parent;
int rank;
};

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

if (subsets[i].parent != i){
subsets[i].parent = find(subsets, subsets[i].parent);
}
return subsets[i].parent;
}

void unionSet(struct Subset subsets[], int x, int y) {

int xroot = find(subsets, x);
int yroot = find(subsets, y);
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++;

21
Shivam Kumar
23049215210171
 }
}
void sortEdges(struct Edge edges[], int E) {
for (int i = 0; i < E - 1; i++) {
for (int j = 0; j < E - i - 1; j++) {
if (edges[j].weight > edges[j + 1].weight) {
struct Edge temp = edges[j];
edges[j] = edges[j + 1];
edges[j + 1] = temp;
}
}
}
}

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

struct Subset subsets[MAX];
struct Edge result[MAX];
int e = 0;
int i = 0;
sortEdges(edges, E);
for (int v = 0; v < V; v++) {
subsets[v].parent = v;
subsets[v].rank = 0;
}
while (e < V - 1 && i < E) {
struct Edge nextEdge = edges[i++];
int x = find(subsets, [Link]);
int y = find(subsets, [Link]);
if (x != y) {
result[e++] = nextEdge;
unionSet(subsets, x, y);
}
}
printf("\nEdges in the Minimum Spanning Tree:\n");

22
Shivam Kumar
23049215210171
 int totalWeight = 0;
for (i = 0; i < e; i++) {
printf("%d -- %d == %d\n", result[i].src, result[i].dest,
result[i].weight);
totalWeight += result[i].weight;
}
printf("Total weight of MST = %d\n", totalWeight);
}

int main() {
int V, E;
struct Edge edges[MAX];

printf("Enter number of vertices: ");

scanf("%d", &V);
printf("Enter number of edges: ");
scanf("%d", &E);

printf("Enter each edge in the format: src dest weight\n");

for (int i = 0; i < E; i++) {
printf("Edge %d: ", i + 1);
scanf("%d %d %d", &edges[i].src, &edges[i].dest, &edges[i].weight);
}

KruskalMST(edges, V, E);
return 0;
}

23
Shivam Kumar
23049215210171
Output :

24
Shivam Kumar
23049215210171
 Experiment 9
Program of Performing Travelling Salesman Problem
Code :
#include <stdio.h>
#include <limits.h>
#define MAX 10
int n;
int graph[MAX][MAX]; // adjacency matrix of the graph
int visited[MAX];
int minCost = INT_MAX;
int min(int a, int b) {
return (a < b) ? a : b;
}

void tsp(int currentCity, int count, int cost, int startCity) {

if (count == n && graph[currentCity][startCity] > 0) {
int totalCost = cost + graph[currentCity][startCity];
if (totalCost < minCost){
minCost = totalCost;
}
return;
}

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

if (!visited[nextCity] && graph[currentCity][nextCity] > 0) {
visited[nextCity] = 1;
tsp(nextCity, count + 1, cost + graph[currentCity][nextCity], startCity);
visited[nextCity] = 0;
}

25
Shivam Kumar
23049215210171
 }
}

int main() {
printf("Enter the number of cities: ");
scanf("%d", &n);
printf("Enter the cost matrix (use 0 if there is no direct path):\n");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &graph[i][j]);
}
}
for (int i = 0; i < n; i++){
visited[i] = 0;
}
visited[0] = 1;
tsp(0, 1, 0, 0);

printf("\nMinimum cost to visit all cities and return to the starting city:
%d\n", minCost);
return 0;
}

Output :

26
Shivam Kumar
23049215210171
 Experiment 10
Program of Performing Travelling Salesman Problem

Code:
#include <stdio.h>
#define MAX 20
int board[MAX];
int n;
void printSolution() {
printf("\nSolution:\n");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (board[i] == j){
printf(" Q ");
}else{
printf(" . ");
}
}
printf("\n");
}
}

int isSafe(int row, int col) {

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

27
Shivam Kumar
23049215210171
 }
}
return 1;
}

void solveNQueen(int row) {

if (row == n) {
printSolution();
return;
}

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

if (isSafe(row, col)) {
board[row] = col;
solveNQueen(row + 1);
}
}
}

int main() {
printf("Enter the number of queens: ");
scanf("%d", &n);
if (n < 1 || n > MAX) {
printf("Invalid number of queens!\n");
return 0;
}
solveNQueen(0);
return 0;
}

28
Shivam Kumar
23049215210171
Output :

29
Shivam Kumar
23049215210171