Experiment - 1

Objective: Program for recursive binary & linear search.

Code:
#include <stdio.h>

// Recursive Linear Search

int recursiveLinearSearch(int arr[], int size, int key, int index) {
if (index >= size)
return -1;
if (arr[index] == key)
return index;
return recursiveLinearSearch(arr, size, key, index + 1);
}

// Recursive Binary Search

int recursiveBinarySearch(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 recursiveBinarySearch(arr, low, mid - 1, key);
else
return recursiveBinarySearch(arr, mid + 1, high, key);
}

int main() {
int arr[] = {2, 4, 6, 8, 10};
int n = 5;
int key1 = 8; // for binary search
int key2 = 4; // for linear search

int result1 = recursiveLinearSearch(arr, n, key2, 0);

 int result2 = recursiveBinarySearch(arr, 0, n - 1, key1);

printf("Array elements: ");

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

printf("Linear Search: Searching for %d:\n", key2);

if (result1 != -1)
printf("Element found at position %d\n", result1 + 1);
else
printf("Element not found.\n");

printf("\nBinary Search: Searching for %d:\n", key1);

if (result2 != -1)
printf("Element found at position %d\n", result2 + 1);
else
printf("Element not found.\n");

return 0;
}

Output:
 Experiment - 2

Objective: Program for heap sort.

Code:
#include <stdio.h>

// Function to heapify a subtree rooted at index i

void heapify(int arr[], int n, int i) {
int largest = i; // Initialize largest as root
int left = 2 * i + 1; // Left child
int right = 2 * i + 2; // Right child

// If left child is larger than root

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

// If right child is larger than largest so far

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

// If largest is not root

if (largest != i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;

// Recursively heapify the affected subtree

heapify(arr, n, largest);
}
}

// Main function to perform Heap Sort

void heapSort(int arr[], int n) {
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);

// Extract elements from heap one by one

for (int i = n - 1; i > 0; i--) {
 // Move current root to end
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;

// call max heapify on the reduced heap

heapify(arr, i, 0);
}
}

// Function to print array

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

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

printf("Original array:\n");
printArray(arr, n);

heapSort(arr, n);

printf("\nSorted array using Heap Sort:\n");

printArray(arr, n);

return 0;
}

Output:
 Experiment - 3

Objective: Program for merge sort.

Code:
#include <stdio.h>

// Function to merge two halves of an array

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

int L[n1], R[n2]; // Temporary arrays

// 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[]

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 remaining elements of L[], if any

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

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

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

// Function to perform merge sort

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 array

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

// Main function
int main() {
int arr[] = {38, 27, 43, 3, 9, 82, 10};
int n = sizeof(arr) / sizeof(arr[0]);

printf("Original array:\n");
printArray(arr, n);
 mergeSort(arr, 0, n - 1);

printf("\nSorted array using Merge Sort:\n");

printArray(arr, n);

return 0;
}

Output:
 Experiment - 4

Objective: Program for selection sort.

Code:
#include <stdio.h>

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

int i, j, minIndex, temp;

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

minIndex = i;

// Find the index of the smallest element in the unsorted part

for (j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex])
minIndex = j;
}

// Swap the found minimum element with the first element

temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}

// Function to print an array

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

// Main function
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("\nSorted array using Selection Sort:\n");

printArray(arr, n);

return 0;
}

Output:
 Experiment - 5

Objective: Program for Insertion Sort.

Code:
#include <stdio.h>

// Function to perform Insertion Sort

void insertionSort(int arr[], int n) {
int i, key, j;
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;

// Move elements of arr[0..i-1], that are greater than key,

// to one position ahead of their current position
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}

// Function to print an array

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

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

printf("Original array:\n");
printArray(arr, n);

insertionSort(arr, n);
 printf("\nSorted array using Insertion Sort:\n");
printArray(arr, n);

return 0;
}

Output:
 Experiment - 6

Objective: Program for quick sort.

Code:
#include <stdio.h>

// Function to swap two elements

void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}

// Partition function
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // pivot element
int i = (low - 1); // index of smaller element

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

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

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

return (i + 1);
}

// Quick Sort function

void quickSort(int arr[], int low, int high) {
if (low < high) {
// pi is partition index
int pi = partition(arr, low, high);

// Recursively sort elements before and after partition

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

// Function to print an array

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

// Main function
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("\nSorted array using Quick Sort:\n");

printArray(arr, n);

return 0;
}

Output:
 Experiment - 7

Objective: Knapsack problem using greedy algorithm.

Code:
#include <stdio.h>

// Structure for items

struct Item {
int weight;
int value;
};

// Function to swap two items

void swap(struct Item *a, struct Item *b) {
struct Item temp = *a;
*a = *b;
*b = temp;
}

// Function to sort items by value/weight ratio (descending order)

void sortByRatio(struct Item arr[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
double r1 = (double)arr[i].value / arr[i].weight;
double r2 = (double)arr[j].value / arr[j].weight;
if (r1 < r2)
swap(&arr[i], &arr[j]);
}
}
}

// Function to find maximum value for given knapsack capacity

double knapsack(struct Item arr[], int n, int capacity) {
sortByRatio(arr, n);

double totalValue = 0.0;

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

if (capacity == 0)
 break;

// If the item can fit completely

if (arr[i].weight <= capacity) {
capacity -= arr[i].weight;
totalValue += arr[i].value;
} else {
// Take fractional part of the item
totalValue += arr[i].value * ((double)capacity /
arr[i].weight);
capacity = 0;
}
}

return totalValue;
}

int main() {
struct Item items[] = {{10, 60}, {20, 100}, {30, 120}};
int n = sizeof(items) / sizeof(items[0]);
int capacity = 50;

printf("Items (weight, value):\n");

for (int i = 0; i < n; i++)
printf("(%d, %d)\n", items[i].weight, items[i].value);

double maxValue = knapsack(items, n, capacity);

printf("\nMaximum value in Knapsack (Greedy Method) = %.2f\n",

maxValue);

return 0;
}

Output:
 Experiment - 8

Objective: Perform Travelling Salesman Problem.

Code:
#include <stdio.h>

#define N 4 // Number of cities

int tsp(int city, int visited, int dist[N][N], int n, int memo[N][16]) {
if (visited == (1 << n) - 1) // All cities visited
return dist[city][0]; // Return to starting city

if (memo[city][visited] != -1)
return memo[city][visited];

int ans = 1000000; // Infinity

for (int next = 0; next < n; next++) {
if (!(visited & (1 << next))) {
int temp = dist[city][next] + tsp(next, visited | (1 << next),
dist, n, memo);
if (temp < ans)
ans = temp;
}
}
return memo[city][visited] = ans;
}

int main() {
int dist[N][N] = {
{0, 10, 15, 20},
{10, 0, 35, 25},
{15, 35, 0, 30},
{20, 25, 30, 0}
};

int memo[N][16];
for (int i = 0; i < N; i++)
for (int j = 0; j < (1 << N); j++)
memo[i][j] = -1;
 int minCost = tsp(0, 1, dist, N, memo); // Start from city 0

printf("Minimum cost of TSP tour: %d\n", minCost);

return 0;
}

Output:
 Experiment - 9

Objective: Find Minimum spanning tree using Kruskal’s Algorithm.

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

// Structure to represent an edge

struct Edge {
int src, dest, weight;
};

// Structure to represent a graph

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

// Function to create a graph

struct Graph* createGraph(int V, int E) {
struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
graph->V = V;
graph->E = E;
graph->edge = (struct Edge*) malloc(E * sizeof(struct Edge));
return graph;
}

// Union-Find functions
int find(int parent[], int i) {
if (parent[i] != i)
parent[i] = find(parent, parent[i]);
return parent[i];
}

void Union(int parent[], int rank[], int x, int y) {

int xroot = find(parent, x);
int yroot = find(parent, y);

if (rank[xroot] < rank[yroot])

 parent[xroot] = yroot;
else if (rank[xroot] > rank[yroot])
parent[yroot] = xroot;
else {
parent[yroot] = xroot;
rank[xroot]++;
}
}

// Compare function for qsort

int compare(const void* a, const void* b) {
return ((struct Edge*)a)->weight - ((struct Edge*)b)->weight;
}

// Kruskal's algorithm
void KruskalMST(struct Graph* graph) {
int V = graph->V;
struct Edge result[V]; // Store the MST edges
int e = 0; // Index for result[]
int i = 0; // Index for sorted edges

// Sort all edges by increasing weight

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

// Create V subsets with single elements

int *parent = (int*) malloc(V * sizeof(int));
int *rank = (int*) malloc(V * sizeof(int));
for (int v = 0; v < V; v++) {
parent[v] = v;
rank[v] = 0;
}

// Iterate through sorted edges

while (e < V - 1 && i < graph->E) {
struct 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, rank, x, y);
}
}

// Print the MST

printf("Edges in the Minimum Spanning Tree:\n");
int minimumCost = 0;
for (i = 0; i < e; i++) {
printf("%d -- %d == %d\n", result[i].src, result[i].dest,
result[i].weight);
minimumCost += result[i].weight;
}
printf("Minimum Cost of MST: %d\n", minimumCost);

free(parent);
free(rank);
}

// Main function
int main() {
int V = 4; // Number of vertices
int E = 5; // Number of edges
struct Graph* graph = createGraph(V, E);

// Add edges: (src, dest, weight)

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;

KruskalMST(graph);

free(graph->edge);
 free(graph);
return 0;
}

Output:
 Experiment - 10

Objective: Implement N queen problem using back tracking.

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

#define N 8 // Number of queens (and board size)

// Function to print the board

void printBoard(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");
}
}

// Function to check if placing a queen at board[row][col] is safe

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

// Check this row on left side

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

// Check upper diagonal on left side

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

// Check lower diagonal on left side

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

return true;
}
// Recursive function to solve N-Queen problem
bool solveNQueen(int board[N][N], int col) {
if (col >= N)
return true; // All queens are placed

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

if (isSafe(board, i, col)) {
board[i][col] = 1; // Place queen

if (solveNQueen(board, col + 1))

return true;

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

return false; // No valid position found

}

int main() {
int board[N][N] = {0};

if (solveNQueen(board, 0))
printBoard(board);
else
printf("No solution exists.\n");

return 0;
}

Output: