Experiment 1: Insertion Sort

#include <stdio.h>
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;
}
}

int main() {
int arr[] = {25,12,64,22,11};
int n = 5, i;
insertionSort(arr, n);
printf("Sorted array (Insertion Sort):\n");
for (i = 0; i < n; i++) printf("%d ", arr[i]);
printf("\n");
return 0;}
 Experiment 2: Selection Sort

#include <stdio.h>
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;
temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}
int main() {
int arr[] = {29,10,14,37,13};
int n = 5, i;
selectionSort(arr, n);
printf("Sorted array (Selection Sort):\n");
for (i = 0; i < n; i++) printf("%d ", arr[i]);
printf("\n");
return 0;
 Experiment 3: Merge Sort

#include <stdio.h>
#include <stdlib.h>
void merge(int arr[], int l, int m, int r) {
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int *L = malloc(n1 * sizeof(int));
int *R = malloc(n2 * sizeof(int));
for (i=0;i<n1;i++) L[i]=arr[l+i];
for (j=0;j<n2;j++) R[j]=arr[m+1+j];
i=0;j=0;k=l;
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) arr[k++] = R[j++];
free(L); free(R);
}
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r-l)/2;
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}
int main() {
int arr[] = {38,27,43,3,9,82,10};
int n = 7, i;
mergeSort(arr, 0, n-1);
printf("Sorted array (Merge Sort):\n");
for (i=0;i<n;i++) printf("%d ", arr[i]);
printf("\n");
return 0;
}
 Experiment 4: Quick Sort

#include <stdio.h>
void swap(int *a,int *b){int t=*a;*a=*b;*b=t;}
int partition(int arr[], int low, int high){
int pivot = arr[high];
int i = low-1, j;
for (j=low;j<=high-1;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 arr[] = {10,7,8,9,1,5};
int n = 6, i;
quickSort(arr, 0, n-1);
printf("Sorted array (Quick Sort):\n");
for (i=0;i<n;i++) printf("%d ", arr[i]);
printf("\n");
return 0;
}
 Experiment 5: Heap Sort
#include <stdio.h>
void heapify(int arr[], int n, int i) {
int largest = i, l = 2*i+1, r = 2*i+2, temp;
if (l < n && arr[l] > arr[largest]) largest = l;
if (r < n && arr[r] > arr[largest]) largest = r;
if (largest != i) {
temp = arr[i]; arr[i] = arr[largest]; arr[largest] = temp;
heapify(arr, n, largest);
}
}

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

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

int main(){
int arr[] = {12,11,13,5,6,7};
int n = 6, i;
heapSort(arr, n);
printf("Sorted array (Heap Sort):\n");
for (i=0;i<n;i++) printf("%d ", arr[i]);
printf("\n");
return 0;
}
 Experiment 6: Recursive Binary Search

#include <stdio.h>
int binarySearch(int arr[], int l, int r, int x) {
if (r >= l) {
int mid = l + (r - l)/2;
if (arr[mid] == x) return mid;
if (arr[mid] > x) return binarySearch(arr, l, mid-1, x);
return binarySearch(arr, mid+1, r, x);
}
return -1;
}

int main() {
int arr[] = {2,3,4,10,40};
int n = 5;
int x = 10;
int result = binarySearch(arr, 0, n-1, x);
if (result != -1) printf("Element found at index %d\n", result);
else printf("Element not present\n");
return 0;
}
 Experiment 7: Recursive Linear Search

#include <stdio.h>
int linearSearchRec(int arr[], int n, int idx, int key) {
if (idx >= n) return -1;
if (arr[idx] == key) return idx;
return linearSearchRec(arr, n, idx+1, key);
}

int main() {
int arr[] = {5,3,7,1,9};
int n = 5;
int key = 1;
int pos = linearSearchRec(arr, n, 0, key);
if (pos != -1) printf("Element %d found at index %d\n", key, pos);
else printf("Not found\n");
return 0;
}
 Experiment 8: Floyd's Algorithm (All-Pairs Shortest Paths)

#include <stdio.h>
#define INF 99999
void floydWarshall(int V, int dist[V][V]) {
int i,j,k;
for (k=0;k<V;k++)
for (i=0;i<V;i++)
for (j=0;j<V;j++)
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}

int main() {
int V = 4;
int dist[4][4] = {
{0, 5, INF, 10},
{INF,0,3,INF},
{INF,INF,0,1},
{INF,INF,INF,0}
};
floydWarshall(V, dist);
printf("Shortest distances matrix:\n");
for (int i=0;i<V;i++){
for (int j=0;j<V;j++){
if (dist[i][j]==INF) printf("INF ");
else printf("%d ", dist[i][j]);
}
printf("\n");
}
return 0;
}
 Experiment 9 : Travelling Salesperson(DP-Held-Karp small n)
#include <stdio.h>
#include <limits.h>
int tsp(int n, int dist[10][10], int dp[1 << 10][10], int mask, int pos) {
if (mask == (1 << n) - 1)
return dist[pos][0];
if (dp[mask][pos] != -1)
return dp[mask][pos];
int ans = INT_MAX;
for (int city = 0; city < n; city++) {
if ((mask & (1 << city)) == 0) { // if city not visited
int newAns = dist[pos][city] + tsp(n, dist, dp, mask | (1 << city),
city);
if (newAns < ans)
ans = newAns;
}
}
dp[mask][pos] = ans;
return ans;
}
int main() {
int n = 4;
int dist[10][10] = {
{0, 20, 42, 25},
{20, 0, 30, 34},
{42, 30, 0, 10},
{25, 34, 10, 0}
};
static int dp[1 << 10][10];
for (int i = 0; i < (1 << n); i++)
for (int j = 0; j < n; j++)
dp[i][j] = -1;
int ans = tsp(n, dist, dp, 1, 0); // start from city 0 (mask=1)
printf("Minimum TSP tour cost (n=%d): %d\n", n, ans);
return 0;
}
 Experiment 10: Hamiltonian Cycles (Backtracking)

#include <stdio.h>
#include <stdbool.h>
int V = 5;

void printCycle(int path[]) {

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

bool isSafe(int v, int graph[V][V], int path[], int pos) {

if (graph[path[pos-1]][v] == 0) return false;
for (int i=0;i<pos;i++) if (path[i] == v) return false;
return true;
}

bool hamCycleUtil(int graph[V][V], int path[], int pos) {

if (pos == V) {
if (graph[path[pos-1]][path[0]] == 1) return true;
else return false;
}
for (int v=1; v<V; v++) {
if (isSafe(v, graph, path, pos)) {
path[pos] = v;
if (hamCycleUtil(graph, path, pos+1)) return true;
path[pos] = -1;
}
}
return false;
}
void hamCycle(int graph[V][V]) {
int path[5];
for (int i=0;i<V;i++) path[i] = -1;
path[0] = 0;
if (hamCycleUtil(graph, path, 1)) {
printf("Hamiltonian cycle found:\n");
printCycle(path);
} else printf("No Hamiltonian cycle\n");
}
int main(){
int graph[5][5] = {
{0,1,0,1,0},
{1,0,1,1,1},
{0,1,0,0,1},
{1,1,0,0,1},
{0,1,1,1,0}
};
hamCycle(graph);
return 0;
}