1. Write a program to implement linear search algorithm.

Repeat the experiment for

#include <stdio.h>
int linearSearch(int arr[], int n, int key) {
for (int i = 0; i < n; i++) {
if (arr[i] == key)
return i; // Return index
}
return -1; // Not found
}
int main() {
int n, key, i, result, choice;
do {
printf("\nEnter the number of elements (n): ");
scanf("%d", &n);

int arr[n];
printf("Enter %d elements:\n", n);
for (i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
printf("Enter the element to search: ");
scanf("%d", &key);
result = linearSearch(arr, n, key);
if (result == -1)
printf("Element %d not found in the array.\n", key);
else
printf("Element %d found at position %d (index %d).\n", key, result + 1, result);
printf("\nDo you want to repeat the experiment with a different value of n? (1 for Yes / 0
for No): ");
scanf("%d", &choice);
} while (choice == 1);
return 0;
}
o/p
Enter the number of elements (n): 5
Enter 5 elements:
10 20 30 40 50
Enter the element to search: 30
Element 30 found at position 3 (index 2).
2. Write a program to implement binary search algorithm. Repeat the experiment for
different values of n, the number of elements in the list to be searched.

#include <stdio.h>
int binarySearch(int arr[], int n, int key) {
int low = 0, high = n - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == key)
return mid; // Found
else if (arr[mid] < key)
low = mid + 1;
else
high = mid - 1;
}
return -1; // Not found
}
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n-1; i++) {
for (int j = 0; j < n-i-1; j++) {
if (arr[j] > arr[j+1]) {
// Swap
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
int main() {
int n, key, choice;
do {
printf("\nEnter the number of elements (n): ");
scanf("%d", &n);
int arr[n];
printf("Enter %d elements (unsorted list):\n", n);
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
bubbleSort(arr, n); // Sort array before Binary Search
printf("Sorted array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\nEnter the element to search: ");
scanf("%d", &key);
int result = binarySearch(arr, n, key);
if (result == -1)
printf("Element %d not found in the array.\n", key);
else
 printf("Element %d found at position %d (index %d).\n", key, result + 1, result);
printf("\nDo you want to repeat the experiment with a different value of n? (1 for Yes / 0
for No): ");
scanf("%d", &choice);
} while (choice == 1);
return 0;
}
o/p
Enter the number of elements (n): 6
Enter 6 elements (unsorted list):
25 10 40 20 50 30
Sorted array: 10 20 25 30 40 50
Enter the element to search: 30
Element 30 found at position 4 (index 3).
3. Write a program to solve towers of Hanoi problem and execute it for different
number of disks.

#include <stdio.h>
void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod) {
if (n == 1) {
printf("Move disk 1 from rod %c to rod %c\n", from_rod, to_rod);
return;
}
towerOfHanoi(n - 1, from_rod, aux_rod, to_rod);
printf("Move disk %d from rod %c to rod %c\n", n, from_rod, to_rod);
towerOfHanoi(n - 1, aux_rod, to_rod, from_rod);
}
int main() {
int n, choice;
do {
printf("\nEnter the number of disks: ");
scanf("%d", &n);
printf("Steps to solve Towers of Hanoi with %d disks:\n", n);
towerOfHanoi(n, 'A', 'C', 'B'); // A = source, C = destination, B = auxiliary
printf("\nDo you want to try with a different number of disks? (1 for Yes / 0 for
No): ");
scanf("%d", &choice);
} while (choice == 1);
return 0;
}
o/p
Enter the number of disks: 3
Steps to solve Towers of Hanoi with 3 disks:
Move disk 1 from rod A to rod C
Move disk 2 from rod A to rod B
Move disk 1 from rod C to rod B
 Move disk 3 from rod A to rod C
Move disk 1 from rod B to rod A
Move disk 2 from rod B to rod C
Move disk 1 from rod A to rod C
4. Write a Program to Sort a given set of numbers using selection sort algorithm.

#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 n, i;
printf("Enter the number of elements: ");
scanf("%d", &n);
int arr[n];
printf("Enter %d elements:\n", n);
for (i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
selectionSort(arr, n);
printf("Sorted array using Selection Sort:\n");
for (i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
o/p
Enter the number of elements: 5
Enter 5 elements:
64 25 12 22 11
Sorted array using Selection Sort:
11 12 22 25 64
5. Write a program to find the value of aⁿ (where a and n are integers) using both
brute-force based algorithm and divide and conquer based algorithm.

#include <stdio.h>
 int powerBruteForce(int a, int n) {
int result = 1;
for (int i = 0; i < n; i++) {
result *= a;
}
return result;
}
int powerDivideConquer(int a, int n) {
if (n == 0)
return 1;
int half = powerDivideConquer(a, n / 2);
if (n % 2 == 0)
return half * half;
else
return a * half * half;
}
int main() {
int a, n;
printf("Enter base (a): ");
scanf("%d", &a);
printf("Enter exponent (n): ");
scanf("%d", &n);
int result1 = powerBruteForce(a, n);
int result2 = powerDivideConquer(a, n);
printf("\nResult using Brute Force: %d^%d = %d\n", a, n, result1);
printf("Result using Divide & Conquer: %d^%d = %d\n", a, n, result2);
return 0;
}
o/p
Enter base (a): 2
Enter exponent (n): 5
Result using Brute Force: 2^5 = 32
Result using Divide & Conquer: 2^5 = 32
6. Write a Program to Sort a given set of elements using quick sort algorithm.

#include <stdio.h>
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // choose the last element as pivot
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
 }
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
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 the number of elements: ");
scanf("%d", &n);
int arr[n];
printf("Enter %d elements:\n", n);
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
quickSort(arr, 0, n - 1);
printf("Sorted array using Quick Sort:\n");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
o/p
Enter the number of elements: 6
Enter 6 elements:
10 7 8 9 1 5
Sorted array using Quick Sort:
1 5 7 8 9 10
7. Write a Program to find the binomial co-efficient C(n, k), [where n and k are
integers and n > k] using brute force based algorithm.

#include <stdio.h>
long long factorial(int num) {
long long fact = 1;
for (int i = 1; i <= num; i++)
fact *= i;
return fact;
}
 long long binomialCoefficient(int n, int k) {
if (k > n) return 0;
return factorial(n) / (factorial(k) * factorial(n - k));
}
int main() {
int n, k;
printf("Enter values for n and k (n > k):\n");
printf("n = ");
scanf("%d", &n);
printf("k = ");
scanf("%d", &k);
if (n < 0 || k < 0 || k > n) {
printf("Invalid input. Ensure that n >= 0, k >= 0, and n > k.\n");
return 1;
}
long long result = binomialCoefficient(n, k);
printf("C(%d, %d) = %lld\n", n, k, result);
return 0;
}
o/p
Enter values for n and k (n > k):
n=5
k=2
C(5, 2) = 10
8. Write a program to find the Minimum Spanning Tree (MST) of a connected graph.
Greedy Algorithm, Graphs.

#include <stdio.h>
#include <limits.h>
#define MAX 100
#define INF 9999
int findMinVertex(int key[], int mstSet[], int n) {
int min = INF, minIndex;
for (int v = 0; v < n; v++) {
if (mstSet[v] == 0 && key[v] < min) {
min = key[v], minIndex = v;
}
}
return minIndex;
}
void primMST(int graph[MAX][MAX], int n) {
int parent[MAX];
int key[MAX];
int mstSet[MAX];
 for (int i = 0; i < n; i++) {
key[i] = INF;
mstSet[i] = 0;
}
key[0] = 0;
parent[0] = -1;
for (int count = 0; count < n - 1; count++) {
int u = findMinVertex(key, mstSet, n);
mstSet[u] = 1;
for (int v = 0; v < n; v++) {
if (graph[u][v] && mstSet[v] == 0 && graph[u][v] < key[v]) {
parent[v] = u;
key[v] = graph[u][v];
}
}
}
printf("Edge \tWeight\n");
for (int i = 1; i < n; i++)
printf("%d - %d \t%d\n", parent[i], i, graph[i][parent[i]]);
}
int main() {
int n, graph[MAX][MAX];
printf("Enter number of vertices: ");
scanf("%d", &n);
printf("Enter adjacency matrix (0 if no edge):\n");
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
scanf("%d", &graph[i][j]);
primMST(graph, n);
return 0;
}
Sample Input:
Enter number of vertices: 4
Enter adjacency matrix:
0206
2038
0300
6800
Output:
Edge Weight
0-1 2
1-2 3
0-3 6
9. Write a program to evaluate a polynomial using brute-force based algorithm and
using Horner’s rule and compare their performances.
 #include <stdio.h>
#include <time.h>
#include <math.h>
#define MAX 100
double evaluateBruteForce(int coeff[], int degree, double x) {
double result = 0.0;
for (int i = 0; i <= degree; i++) {
result += coeff[i] * pow(x, degree - i);
}
return result;
}
double evaluateHorner(int coeff[], int degree, double x) {
double result = coeff[0];
for (int i = 1; i <= degree; i++) {
result = result * x + coeff[i];
}
return result;
}
int main() {
int degree, coeff[MAX];
double x;
printf("Enter the degree of the polynomial: ");
scanf("%d", &degree);
printf("Enter %d coefficients (highest to lowest degree):\n", degree + 1);
for (int i = 0; i <= degree; i++) {
scanf("%d", &coeff[i]);
}
printf("Enter the value of x: ");
scanf("%lf", &x);
clock_t start = clock();
double result1 = evaluateBruteForce(coeff, degree, x);
clock_t end = clock();
double time_brute = (double)(end - start) / CLOCKS_PER_SEC;
start = clock();
double result2 = evaluateHorner(coeff, degree, x);
end = clock();
double time_horner = (double)(end - start) / CLOCKS_PER_SEC;
printf("\nResult using Brute-force: %.2lf", result1);
printf("\nResult using Horner's Rule: %.2lf", result2);
printf("\n\nTime taken by Brute-force: %lf seconds", time_brute);
printf("\nTime taken by Horner's Rule: %lf seconds\n", time_horner);
return 0;
}
Sample Input:

Enter the degree of the polynomial: 3

Time taken by Brute-force: 0.0000 seconds

#include <stdio.h>
#include <limits.h>
#define MAX 100
#define INF 9999
int findMinDistance(int dist[], int visited[], int n) {
int min = INF, minIndex;
for (int v = 0; v < n; v++) {
if (!visited[v] && dist[v] <= min) {
min = dist[v];
minIndex = v;
}
}
return minIndex;
}
void dijkstra(int graph[MAX][MAX], int n, int src) {
int dist[MAX]; // Shortest distance from src to i
int visited[MAX]; // Visited vertices
for (int i = 0; i < n; i++) {
dist[i] = INF;
visited[i] = 0;
}
dist[src] = 0;
for (int count = 0; count < n - 1; count++) {
int u = findMinDistance(dist, visited, n);
visited[u] = 1;
for (int v = 0; v < n; v++) {
if (!visited[v] && graph[u][v] && dist[u] != INF &&
dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}
printf("\nVertex\tDistance from Source %d\n", src);
for (int i = 0; i < n; i++)
printf("%d\t%d\n", i, dist[i]);
 }
int main() {
int n, graph[MAX][MAX], src;
printf("Enter number of vertices: ");
scanf("%d", &n);
printf("Enter the adjacency matrix (0 if no edge):\n");
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
scanf("%d", &graph[i][j]);
printf("Enter the source vertex: ");
scanf("%d", &src);
dijkstra(graph, n, src);
return 0;
}
Sample Input:
Enter number of vertices: 5
Enter adjacency matrix:
0 10 0 0 5
00102
00040
70600
03920
Enter the source vertex: 0
Output:
Vertex Distance from Source 0
0 0
1 8
2 9
3 7
4 5
11. Write a program to determine whether there exists a subset of the given set that
adds up to a given sum using Backtracking.

#include <stdio.h>
#define MAX 100
int subsetSum(int set[], int n, int index, int currentSum, int target) {
if (currentSum == target)
return 1;
if (index == n || currentSum > target)
return 0;
if (subsetSum(set, n, index + 1, currentSum + set[index], target))
return 1;
if (subsetSum(set, n, index + 1, currentSum, target))
return 1;
return 0;
}
 int main() {
int set[MAX], n, target;
printf("Enter number of elements in the set: ");
scanf("%d", &n);
printf("Enter %d elements:\n", n);
for (int i = 0; i < n; i++)
scanf("%d", &set[i]);
printf("Enter the target sum: ");
scanf("%d", &target);
if (subsetSum(set, n, 0, 0, target))
printf("Subset with the given sum exists.\n");
else
printf("No subset with the given sum exists.\n");
return 0;
}
Sample Input:
Enter number of elements in the set: 5
Enter 5 elements:
3 34 4 12 5
Enter the target sum: 9
Output:
Subset with the given sum exists.
12. Write a program to implement BFS traversal algorithm.

#include <stdio.h>
#define MAX 100
int queue[MAX], front = -1, rear = -1;
void enqueue(int value) {
if (rear == MAX - 1)
return;
if (front == -1) front = 0;
queue[++rear] = value;
}
int dequeue() {
if (front == -1 || front > rear)
return -1;
return queue[front++];
}
int isEmpty() {
return (front == -1 || front > rear);
}
void BFS(int graph[MAX][MAX], int n, int start) {
int visited[MAX] = {0};
enqueue(start);
visited[start] = 1;
 printf("BFS Traversal: ");
while (!isEmpty()) {
int current = dequeue();
printf("%d ", current);
for (int i = 0; i < n; i++) {
if (graph[current][i] && !visited[i]) {
enqueue(i);
visited[i] = 1;
}
}
}
printf("\n");
}
int main() {
int n, graph[MAX][MAX], start;
printf("Enter number of vertices: ");
scanf("%d", &n);
printf("Enter the adjacency matrix:\n");
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
scanf("%d", &graph[i][j]);
printf("Enter the starting vertex: ");
scanf("%d", &start);
BFS(graph, n, start);
return 0;
}
Sample Input:
Enter number of vertices: 4
Enter the adjacency matrix:
0110
1001
1001
0110
Enter the starting vertex: 0
Output:
BFS Traversal: 0 1 2 3
13. Write a program to find the minimum spanning tree of a given graph using Prim’s
algorithm.

#include <stdio.h>
#include <limits.h>
#define MAX 100
#define INF 9999
int findMinVertex(int key[], int mstSet[], int n) {
int min = INF, minIndex = -1;
for (int v = 0; v < n; v++) {
 if (!mstSet[v] && key[v] < min) {
min = key[v];
minIndex = v;
}
}
return minIndex;
}
void primMST(int graph[MAX][MAX], int n) {
int parent[MAX]; // Stores MST
int key[MAX]; // Minimum weight edge for each vertex
int mstSet[MAX]; // Set of vertices included in MST
for (int i = 0; i < n; i++) {
key[i] = INF;
mstSet[i] = 0;
}
key[0] = 0; // Start from the first vertex
parent[0] = -1; // First node is always root
for (int count = 0; count < n - 1; count++) {
int u = findMinVertex(key, mstSet, n);
mstSet[u] = 1;
for (int v = 0; v < n; v++) {
if (graph[u][v] && !mstSet[v] && graph[u][v] < key[v]) {
parent[v] = u;
key[v] = graph[u][v];
}
}
}
printf("Edge \tWeight\n");
for (int i = 1; i < n; i++)
printf("%d - %d \t%d\n", parent[i], i, graph[i][parent[i]]);
}
int main() {
int n, graph[MAX][MAX];
printf("Enter the number of vertices: ");
scanf("%d", &n);
printf("Enter the adjacency matrix (0 if no edge):\n");
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
scanf("%d", &graph[i][j]);
primMST(graph, n);
return 0;
}
Sample Input:
Enter the number of vertices: 4
Enter the adjacency matrix:
0206
 2038
0300
6800
Output:
Edge Weight
0-1 2
1-2 3
0-3 6
14. Write a program to sort a given set of elements using the heap sort method.

#include <stdio.h>
void heapify(int arr[], int n, int i) {
int largest = i; // Initialize largest as root
int left = 2 * i + 1; // left = 2*i + 1
int right = 2 * i + 2; // 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;
heapify(arr, i, 0);
}
}
int main() {
int arr[100], n;
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter %d elements:\n", n);
for (int i = 0; i < n; i++)
scanf("%d", &arr[i]);
heapSort(arr, n);
printf("Sorted array using Heap Sort:\n");
for (int i = 0; i < n; i++)
 printf("%d ", arr[i]);
printf("\n");
return 0;
}
Sample Input:
Enter number of elements: 6
Enter 6 elements:
12 11 13 5 6 7
Output:
Sorted array using Heap Sort:
5 6 7 11 12 13
15. Write a Program to Find a subset of a given set S = {s₁, s₂, ..., sₙ} of n positive
integers whose sum is equal to a given positive integer d. For example, if S = {1, 2,
5, 6, 8} and d = 9 there are two solutions {1, 2, 6} and {1, 8}. A suitable message is to
be displayed if the given problem instance doesn't have a solution.

#include <stdio.h>
#define MAX 100
int found = 0;
void subsetSum(int set[], int subset[], int n, int index, int subsetSize, int currentSum, int
target) {
if (currentSum == target) {
found = 1;
printf("Subset found: { ");
for (int i = 0; i < subsetSize; i++)
printf("%d ", subset[i]);
printf("}\n");
return;
}
if (index == n || currentSum > target)
return;
subset[subsetSize] = set[index];
subsetSum(set, subset, n, index + 1, subsetSize + 1, currentSum + set[index], target);
subsetSum(set, subset, n, index + 1, subsetSize, currentSum, target);
}
int main() {
int set[MAX], subset[MAX];
int n, target;
printf("Enter the number of elements in the set: ");
scanf("%d", &n);
printf("Enter %d positive integers:\n", n);
for (int i = 0; i < n; i++)
scanf("%d", &set[i]);
printf("Enter the target sum: ");
scanf("%d", &target);
 printf("\nChecking for subsets that sum to %d...\n", target);
subsetSum(set, subset, n, 0, 0, 0, target);
if (!found)
printf("No subset with the given sum exists.\n");
return 0;
}
Sample Input:
Enter the number of elements in the set: 5
Enter 5 positive integers:
12568
Enter the target sum: 9
Sample Output:
Checking for subsets that sum to 9...
Subset found: { 1 2 6 }
Subset found: { 1 8 }