Algorithms in C

A Beginner-Friendly Programs Handbook

All 30 algorithms from your syllabus, each explained simply and written as a complete C
program that takes input from the user and prints the output. Every program has been
compiled and tested to make sure it works.

How to use this book

1. Copy the code into a file, e.g. program.c

2. Compile it: gcc program.c -o program -lm

3. Run it: ./program (or [Link] on Windows)

4. Type the inputs shown in the 'Sample Input/Output' box when asked.
Table of Contents
1. Union-Find Algorithm

2. 0/1 Knapsack Problem

3. Quick Sort and Merge Sort

4. Matrix Chain Multiplication

5. N-Queens Problem (8-Queens)

6. Divide and Conquer (Power Function)

7. Bellman-Ford Algorithm

8. Union by Rank

9. Binary Search and Linear Search

10. Graph Coloring

11. Heap Sort (Heap Data Structure)

12. Brute Force Approach

13. Job Sequencing with Deadlines

14. Greedy Knapsack (Fractional Knapsack)

15. Hamiltonian Cycle

16. Dijkstra's Algorithm

17. Floyd-Warshall Algorithm

18. Max-Min using Divide and Conquer

19. Heuristic Algorithm (Nearest Neighbour for TSP)

20. External Sort (using runs and merging)

21. Prim's and Kruskal's Algorithm (Minimum Spanning Tree)

22. BFS and DFS (Graph Traversal)

23. Max Flow / Min Cut (Edmonds-Karp using BFS)

24. KMP Algorithm (Knuth-Morris-Pratt)

25. Naive String Matching

26. Ford-Fulkerson Algorithm (using DFS)

27. Transitive Closure of a Graph (Warshall's Algorithm)

28. Fast Fourier Transform (FFT)

29. Strassen's Matrix Multiplication

30. 15-Puzzle (Solvability Check + Move Simulation)
1. Union-Find Algorithm
Union-Find (Disjoint Set) keeps track of elements split into groups. 'Find' tells you which group an element
belongs to, and 'Union' merges two groups together.

C Program:
#include <stdio.h>

int parent[100];

// Find the representative (root) of the set containing x

int find(int x) {
if (parent[x] == x)
return x;
return parent[x] = find(parent[x]); // path compression
}

// Union the sets containing x and y

void unionSets(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY)
parent[rootX] = rootY;
}

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

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

parent[i] = i; // initially every element is its own parent

printf("Enter number of union operations: ");

scanf("%d", &q);

printf("Enter pairs to union (a b):\n");

for (int i = 0; i < q; i++) {
int a, b;
scanf("%d %d", &a, &b);
unionSets(a, b);
}

int x, y;
printf("Enter two elements to check if connected: ");
scanf("%d %d", &x, &y);

if (find(x) == find(y))
printf("Output: %d and %d are in the SAME set\n", x, y);
else
printf("Output: %d and %d are in DIFFERENT sets\n", x, y);

return 0;
}

Sample Input / Output:

Input: n=5, unions: (0 1)(1 2)(3 4), check 0 2 -> Output: SAME set
2. 0/1 Knapsack Problem
Given items with weight and value, choose items (each item can be taken fully or not at all) to maximize
value without exceeding the bag's capacity.

C Program:
#include <stdio.h>

int max(int a, int b) { return (a > b) ? a : b; }

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

int wt[100], val[100];

printf("Enter weight and value of each item:\n");
for (int i = 0; i < n; i++)
scanf("%d %d", &wt[i], &val[i]);

printf("Enter knapsack capacity: ");

scanf("%d", &capacity);

int dp[100][1000];
for (int i = 0; i <= n; i++) {
for (int w = 0; w <= capacity; w++) {
if (i == 0 || w == 0)
dp[i][w] = 0;
else if (wt[i - 1] <= w)
dp[i][w] = max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w]);
else
dp[i][w] = dp[i - 1][w];
}
}

printf("Output: Maximum value = %d\n", dp[n][capacity]);

return 0;
}

Sample Input / Output:

Input: 3 items (2,3)(3,4)(4,5), capacity=5 -> Output: Maximum value = 7
3. Quick Sort and Merge Sort
Both are Divide and Conquer sorting algorithms. Quick Sort picks a pivot and partitions the array. Merge
Sort splits the array in half, sorts each half, then merges them.

C Program:
#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], 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);
}
}

void merge(int arr[], int l, int m, int r) {

int n1 = m - l + 1, n2 = r - m;
int L[100], R[100];
for (int i = 0; i < n1; i++) L[i] = arr[l + i];
for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j];

int i = 0, j = 0, k = l;
while (i < n1 && j < n2)
arr[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
}

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 n, arr1[100], arr2[100];
printf("Enter number of elements: ");
scanf("%d", &n);

printf("Enter elements: ");

for (int i = 0; i < n; i++) {
scanf("%d", &arr1[i]);
arr2[i] = arr1[i]; // copy for the second sort
}

quickSort(arr1, 0, n - 1);
mergeSort(arr2, 0, n - 1);

printf("Output (Quick Sort): ");

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

printf("\nOutput (Merge Sort): ");

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

return 0;
}

Sample Input / Output:

Input: 5 elements: 5 2 4 1 3 -> Output: 1 2 3 4 5 (both sorts)
4. Matrix Chain Multiplication
Given the dimensions of a chain of matrices, find the minimum number of scalar multiplications needed to
multiply them all together, using Dynamic Programming.

C Program:
#include <stdio.h>
#include <limits.h>

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

int p[100]; // p[i-1] x p[i] is the dimension of matrix i

printf("Enter %d dimensions (p0 p1 ... pn): ", n + 1);
for (int i = 0; i <= n; i++)
scanf("%d", &p[i]);

int dp[100][100] = {0};

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

for (int i = 1; i <= n - len + 1; i++) {
int j = i + len - 1;
dp[i][j] = INT_MAX;
for (int k = i; k < j; k++) {
int cost = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j];
if (cost < dp[i][j])
dp[i][j] = cost;
}
}
}

printf("Output: Minimum multiplications = %d\n", dp[1][n]);

return 0;
}

Sample Input / Output:

Input: 4 matrices, dims: 10 20 30 40 30 -> Output: Minimum multiplications = 30000
5. N-Queens Problem (8-Queens)
Place N queens on an N x N chessboard so that no two queens attack each other (same row, column, or
diagonal), using backtracking.

C Program:
#include <stdio.h>

int board[20], n;

int isSafe(int row, int col) {

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

void printSolution() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
printf("%c ", (board[i] == j) ? 'Q' : '.');
printf("\n");
}
}

int solve(int row, int *count) {

if (row == n) {
(*count)++;
if (*count == 1) {
printf("Output: First solution found:\n");
printSolution();
}
return 1;
}
int found = 0;
for (int col = 0; col < n; col++) {
if (isSafe(row, col)) {
board[row] = col;
found |= solve(row + 1, count);
}
}
return found;
}

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

int count = 0;
solve(0, &count);

printf("Output: Total number of solutions = %d\n", count);

return 0;
}

Sample Input / Output:

Input: N=4 -> Output: shows first arrangement, Total solutions = 2
6. Divide and Conquer (Power Function)
Divide and Conquer breaks a problem into smaller sub-problems, solves each, then combines results.
Here we compute x^n quickly by splitting the exponent in half each time.

C Program:
#include <stdio.h>

// Compute x^n using Divide and Conquer

long long power(int x, int n) {
if (n == 0)
return 1;
long long half = power(x, n / 2);
if (n % 2 == 0)
return half * half;
else
return half * half * x;
}

int main() {
int x, n;
printf("Enter base (x): ");
scanf("%d", &x);
printf("Enter exponent (n): ");
scanf("%d", &n);

printf("Output: %d^%d = %lld\n", x, n, power(x, n));

return 0;
}

Sample Input / Output:

Input: x=2, n=10 -> Output: 2^10 = 1024
7. Bellman-Ford Algorithm
Finds shortest paths from a source vertex to all other vertices, and works even when edge weights are
negative (unlike Dijkstra).

C Program:
#include <stdio.h>
#include <limits.h>

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

int src[100], dest[100], wt[100];

printf("Enter each edge as (source destination weight):\n");
for (int i = 0; i < E; i++)
scanf("%d %d %d", &src[i], &dest[i], &wt[i]);

int source;
printf("Enter source vertex: ");
scanf("%d", &source);

int dist[100];
for (int i = 0; i < V; i++)
dist[i] = INT_MAX;
dist[source] = 0;

// Relax all edges V-1 times

for (int i = 1; i <= V - 1; i++) {
for (int j = 0; j < E; j++) {
if (dist[src[j]] != INT_MAX && dist[src[j]] + wt[j] < dist[dest[j]])
dist[dest[j]] = dist[src[j]] + wt[j];
}
}

// Check for negative weight cycles

for (int j = 0; j < E; j++) {
if (dist[src[j]] != INT_MAX && dist[src[j]] + wt[j] < dist[dest[j]]) {
printf("Output: Graph contains a negative weight cycle\n");
return 0;
}
}

printf("Output: Shortest distances from source %d:\n", source);

for (int i = 0; i < V; i++)
printf("Vertex %d -> Distance %d\n", i, dist[i]);

return 0;
}

Sample Input / Output:

Input: V=5, E=8 edges with weights, source=0 -> Output: distance to each vertex
8. Union by Rank
An improvement to Union-Find: when merging two sets, always attach the smaller (lower rank) tree under
the root of the bigger (higher rank) tree. This keeps the tree flat and searches fast.

C Program:
#include <stdio.h>

int parent[100], rank_[100];

int find(int x) {
if (parent[x] != x)
parent[x] = find(parent[x]); // path compression
return parent[x];
}

void unionByRank(int x, int y) {

int rootX = find(x), rootY = find(y);
if (rootX == rootY) return;

if (rank_[rootX] < rank_[rootY])

parent[rootX] = rootY;
else if (rank_[rootX] > rank_[rootY])
parent[rootY] = rootX;
else {
parent[rootY] = rootX;
rank_[rootX]++;
}
}

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

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

parent[i] = i;
rank_[i] = 0;
}

printf("Enter number of union operations: ");

scanf("%d", &q);

printf("Enter pairs to union (a b):\n");

for (int i = 0; i < q; i++) {
int a, b;
scanf("%d %d", &a, &b);
unionByRank(a, b);
}

printf("Output: Final parent of each element:\n");

for (int i = 0; i < n; i++)
printf("Element %d -> Root %d\n", i, find(i));

return 0;
}

Sample Input / Output:

Input: n=5, unions (0 1)(1 2)(3 4) -> Output: root/group of each element
9. Binary Search and Linear Search
Linear Search checks every element one by one. Binary Search works only on a SORTED array and
repeatedly cuts the search space in half, making it much faster.

C Program:
#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 -1;
}

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;
else if (arr[mid] < key)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}

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

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

int key;
printf("Enter the element to search: ");
scanf("%d", &key);

int posLinear = linearSearch(arr, n, key);

int posBinary = binarySearch(arr, n, key);

printf("Output (Linear Search): ");

if (posLinear != -1) printf("Found at index %d\n", posLinear);
else printf("Not found\n");

printf("Output (Binary Search): ");

if (posBinary != -1) printf("Found at index %d\n", posBinary);
else printf("Not found\n");

return 0;
}

Sample Input / Output:

Input: 1 2 3 4 5, search 4 -> Output: Found at index 3 (both methods)
10. Graph Coloring
Assign colors to each vertex of a graph so that no two adjacent (connected) vertices share the same color,
using the fewest colors possible (backtracking approach).

C Program:
#include <stdio.h>

int graph[20][20], color[20], V, m;

int isSafe(int v, int c) {

for (int i = 0; i < V; i++)
if (graph[v][i] && color[i] == c)
return 0;
return 1;
}

int solve(int v) {
if (v == V)
return 1; // all vertices colored successfully

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

if (isSafe(v, c)) {
color[v] = c;
if (solve(v + 1))
return 1;
color[v] = 0; // backtrack
}
}
return 0;
}

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

printf("Enter adjacency matrix (%dx%d):\n", V, V);

for (int i = 0; i < V; i++)
for (int j = 0; j < V; j++)
scanf("%d", &graph[i][j]);

printf("Enter number of colors available: ");

scanf("%d", &m);

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

if (solve(0)) {
printf("Output: Coloring possible! Assigned colors:\n");
for (int i = 0; i < V; i++)
printf("Vertex %d -> Color %d\n", i, color[i]);
} else {
printf("Output: No solution exists with %d colors\n", m);
}

return 0;
}

Sample Input / Output:

Input: 4 vertices (cycle graph), m=3 colors -> Output: color assigned to each vertex
11. Heap Sort (Heap Data Structure)
A Heap is a special tree where the parent is always bigger (max-heap) than its children. Heap Sort
repeatedly builds a max-heap and removes the largest element to sort the array.

C Program:
#include <stdio.h>

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

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

int largest = i, l = 2 * i + 1, r = 2 * i + 2;

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

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

if (largest != i) {
swap(&arr[i], &arr[largest]);
heapify(arr, n, largest); // fix the affected sub-tree
}
}

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

// Build max heap
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);

// One by one extract elements

for (int i = n - 1; i > 0; i--) {
swap(&arr[0], &arr[i]);
heapify(arr, i, 0);
}
}

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

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

heapSort(arr, n);

printf("Output (Sorted using Heap Sort): ");

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

return 0;
}

Sample Input / Output:

Input: 5 2 4 1 3 -> Output: 1 2 3 4 5
12. Brute Force Approach
A Brute Force algorithm simply tries every possible option until it finds the answer. Here we find a pair of
numbers in an array whose sum equals a given target by checking all pairs.

C Program:
#include <stdio.h>

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

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

int target;
printf("Enter target sum: ");
scanf("%d", &target);

int found = 0;
// Brute force: check every possible pair
for (int i = 0; i < n && !found; i++) {
for (int j = i + 1; j < n; j++) {
if (arr[i] + arr[j] == target) {
printf("Output: Pair found -> (%d, %d) at indices (%d, %d)\n",
arr[i], arr[j], i, j);
found = 1;
break;
}
}
}

if (!found)
printf("Output: No pair found with sum %d\n", target);

return 0;
}

Sample Input / Output:

Input: 2 7 11 15, target=9 -> Output: Pair found -> (2, 7) at indices (0, 1)
13. Job Sequencing with Deadlines
Given jobs with a deadline and profit, schedule the jobs (one job per time slot) to maximize total profit,
making sure no job is scheduled after its deadline. This is a Greedy algorithm.

C Program:
#include <stdio.h>

struct Job {
int id, deadline, profit;
};

void sortJobs(struct Job jobs[], int n) {

// Sort jobs by profit in descending order
for (int i = 0; i < n - 1; i++)
for (int j = 0; j < n - i - 1; j++)
if (jobs[j].profit < jobs[j + 1].profit) {
struct Job temp = jobs[j];
jobs[j] = jobs[j + 1];
jobs[j + 1] = temp;
}
}

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

struct Job jobs[100];

printf("Enter job id, deadline and profit for each job:\n");
for (int i = 0; i < n; i++)
scanf("%d %d %d", &jobs[i].id, &jobs[i].deadline, &jobs[i].profit);

sortJobs(jobs, n);

int maxDeadline = 0;
for (int i = 0; i < n; i++)
if (jobs[i].deadline > maxDeadline)
maxDeadline = jobs[i].deadline;

int slot[100]; // slot[i] = job id scheduled at time i, 0 = empty

for (int i = 0; i <= maxDeadline; i++) slot[i] = -1;

int totalProfit = 0;
for (int i = 0; i < n; i++) {
// Try to place job in the latest free slot before its deadline
for (int t = jobs[i].deadline; t > 0; t--) {
if (slot[t] == -1) {
slot[t] = jobs[i].id;
totalProfit += jobs[i].profit;
break;
}
}
}

printf("Output: Scheduled jobs (time slot -> job id):\n");

for (int i = 1; i <= maxDeadline; i++)
if (slot[i] != -1)
printf("Slot %d -> Job %d\n", i, slot[i]);

printf("Output: Total Profit = %d\n", totalProfit);

return 0;
}

Sample Input / Output:

Input: 4 jobs (id,deadline,profit): 1 4 20, 2 1 10, 3 1 40, 4 1 30 -> Output: Total Profit = 60
14. Greedy Knapsack (Fractional Knapsack)
Unlike 0/1 Knapsack, here you CAN take a fraction of an item. The Greedy strategy: always pick the item
with the highest value/weight ratio first.

C Program:
#include <stdio.h>

struct Item {
int weight, value;
float ratio;
};

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

struct Item items[100];

printf("Enter weight and value of each item:\n");
for (int i = 0; i < n; i++) {
scanf("%d %d", &items[i].weight, &items[i].value);
items[i].ratio = (float)items[i].value / items[i].weight;
}

float capacity;
printf("Enter knapsack capacity: ");
scanf("%f", &capacity);

// Sort items by value/weight ratio in descending order

for (int i = 0; i < n - 1; i++)
for (int j = 0; j < n - i - 1; j++)
if (items[j].ratio < items[j + 1].ratio) {
struct Item temp = items[j];
items[j] = items[j + 1];
items[j + 1] = temp;
}

float totalValue = 0;
for (int i = 0; i < n && capacity > 0; i++) {
if (items[i].weight <= capacity) {
capacity -= items[i].weight;
totalValue += items[i].value;
} else {
totalValue += items[i].ratio * capacity;
capacity = 0;
}
}

printf("Output: Maximum value obtained = %.2f\n", totalValue);

return 0;
}

Sample Input / Output:

Input: 3 items (10,60)(20,100)(30,120), capacity=50 -> Output: Maximum value = 240.00
15. Hamiltonian Cycle
A Hamiltonian Cycle visits every vertex of the graph exactly once and returns to the starting vertex. We
use backtracking to try building such a cycle.

C Program:
#include <stdio.h>

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

int isSafe(int v, int pos) {

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

int solve(int pos) {

if (pos == V)
return graph[path[pos - 1]][path[0]]; // must connect back to start

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

if (isSafe(v, pos)) {
path[pos] = v;
if (solve(pos + 1))
return 1;
path[pos] = -1; // backtrack
}
}
return 0;
}

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

printf("Enter adjacency matrix (%dx%d):\n", V, V);

for (int i = 0; i < V; i++)
for (int j = 0; j < V; j++)
scanf("%d", &graph[i][j]);

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

path[0] = 0; // always start at vertex 0

if (solve(1)) {
printf("Output: Hamiltonian Cycle found:\n");
for (int i = 0; i < V; i++)
printf("%d -> ", path[i]);
printf("%d\n", path[0]);
} else {
printf("Output: No Hamiltonian Cycle exists\n");
}

return 0;
}

Sample Input / Output:

Input: 5-vertex graph adjacency matrix -> Output: cycle like 0->1->2->4->3->0
16. Dijkstra's Algorithm
Finds the shortest path from a source vertex to all other vertices in a graph with NON-NEGATIVE edge
weights, by always expanding the nearest unvisited vertex.

C Program:
#include <stdio.h>
#define INF 999999

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

int graph[20][20];
printf("Enter adjacency matrix (0 if no edge, %dx%d):\n", V, V);
for (int i = 0; i < V; i++)
for (int j = 0; j < V; j++)
scanf("%d", &graph[i][j]);

int src;
printf("Enter source vertex: ");
scanf("%d", &src);

int dist[20], visited[20] = {0};

for (int i = 0; i < V; i++)
dist[i] = INF;
dist[src] = 0;

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

// Pick the unvisited vertex with smallest distance
int u = -1, minDist = INF;
for (int v = 0; v < V; v++)
if (!visited[v] && dist[v] < minDist) {
minDist = dist[v];
u = v;
}
if (u == -1) break;
visited[u] = 1;

for (int v = 0; v < V; 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("Output: Shortest distances from source %d:\n", src);

for (int i = 0; i < V; i++)
printf("Vertex %d -> Distance %d\n", i, dist[i]);

return 0;
}

Sample Input / Output:

Input: 5-vertex weighted graph, source=0 -> Output: shortest distance to each vertex
17. Floyd-Warshall Algorithm
Finds the SHORTEST PATH between EVERY pair of vertices in a graph, using Dynamic Programming by
gradually allowing each vertex as an intermediate stop.

C Program:
#include <stdio.h>
#define INF 999999

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

int dist[20][20];
printf("Enter adjacency matrix (use %d for no edge, %dx%d):\n", INF, V, V);
for (int i = 0; i < V; i++)
for (int j = 0; j < V; j++)
scanf("%d", &dist[i][j]);

// Try every vertex k as an intermediate point

for (int k = 0; k < V; k++)
for (int i = 0; i < V; i++)
for (int j = 0; j < V; j++)
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];

printf("Output: Shortest distance matrix between all pairs:\n");

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

return 0;
}

Sample Input / Output:

Input: 4-vertex graph matrix (999999 = no edge) -> Output: shortest path matrix
18. Max-Min using Divide and Conquer
Finds the maximum and minimum element in an array by splitting the array into two halves, solving each
half, and combining the results, instead of scanning linearly.

C Program:
#include <stdio.h>

int arr[100];

// Returns max and min through pointers using Divide and Conquer
void maxMin(int low, int high, int *max, int *min) {
if (low == high) {
*max = *min = arr[low];
return;
}
if (high == low + 1) {
if (arr[low] > arr[high]) { *max = arr[low]; *min = arr[high]; }
else { *max = arr[high]; *min = arr[low]; }
return;
}

int mid = (low + high) / 2;

int lmax, lmin, rmax, rmin;
maxMin(low, mid, &lmax, &lmin);
maxMin(mid + 1, high, &rmax, &rmin);

*max = (lmax > rmax) ? lmax : rmax;

*min = (lmin < rmin) ? lmin : rmin;
}

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

printf("Enter elements: ");

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

int maxVal, minVal;

maxMin(0, n - 1, &maxVal, &minVal);

printf("Output: Maximum = %d, Minimum = %d\n", maxVal, minVal);

return 0;
}

Sample Input / Output:

Input: 5 2 8 1 9 3 -> Output: Maximum = 9, Minimum = 1
19. Heuristic Algorithm (Nearest Neighbour for TSP)
A Heuristic algorithm gives a fast, 'good enough' answer instead of guaranteeing the best one. Here, for
the Travelling Salesman Problem, we always move to the NEAREST unvisited city.

C Program:
#include <stdio.h>
#define INF 999999

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

int dist[20][20];
printf("Enter distance matrix (%dx%d):\n", n, n);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
scanf("%d", &dist[i][j]);

int start;
printf("Enter starting city (0 to %d): ", n - 1);
scanf("%d", &start);

int visited[20] = {0};

int current = start, totalCost = 0;
visited[current] = 1;

printf("Output: Path -> %d ", current);

for (int step = 1; step < n; step++) {
int next = -1, minDist = INF;
for (int j = 0; j < n; j++) {
if (!visited[j] && dist[current][j] < minDist) {
minDist = dist[current][j];
next = j;
}
}
visited[next] = 1;
totalCost += minDist;
printf("-> %d ", next);
current = next;
}

totalCost += dist[current][start]; // return to start

printf("-> %d\n", start);
printf("Output: Approximate total tour cost = %d\n", totalCost);

return 0;
}

Sample Input / Output:

Input: 4-city distance matrix, start=0 -> Output: an approximate shortest tour
20. External Sort (using runs and merging)
External Sort is used when data is too big to fit in memory. The idea: break data into small sorted 'runs',
then merge those sorted runs together. Here we simulate it in memory.

C Program:
#include <stdio.h>

void merge(int arr[], int l, int m, int r) {

int n1 = m - l + 1, n2 = r - m;
int L[100], R[100];
for (int i = 0; i < n1; i++) L[i] = arr[l + i];
for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j];

int i = 0, j = 0, k = l;
while (i < n1 && j < n2)
arr[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
}

void sortRun(int arr[], int l, int r) {

// Simple insertion sort for a small "run" (block that fits in memory)
for (int i = l + 1; i <= r; i++) {
int key = arr[i], j = i - 1;
while (j >= l && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}

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

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

printf("Enter run (block) size that fits in memory: ");

scanf("%d", &runSize);

// Step 1: Sort each run individually

for (int i = 0; i < n; i += runSize) {
int end = (i + runSize - 1 < n - 1) ? i + runSize - 1 : n - 1;
sortRun(arr, i, end);
}

// Step 2: Merge the sorted runs together

for (int size = runSize; size < n; size *= 2) {
for (int left = 0; left < n - 1; left += 2 * size) {
int mid = (left + size - 1 < n - 1) ? left + size - 1 : n - 1;
int right = (left + 2 * size - 1 < n - 1) ? left + 2 * size - 1 : n - 1;
if (mid < right)
merge(arr, left, mid, right);
}
}

printf("Output (Externally Sorted): ");

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

return 0;
}

Sample Input / Output:

Input: 8 5 3 9 1 6 2 7, run size=2 -> Output: 1 2 3 5 6 7 8 9
21. Prim's and Kruskal's Algorithm (Minimum Spanning Tree)
Both find a Minimum Spanning Tree (MST) - a subset of edges connecting all vertices with minimum total
weight. Prim's grows the tree one vertex at a time. Kruskal's picks the smallest edges first (using
Union-Find to avoid cycles).

C Program:
#include <stdio.h>
#define INF 999999
#define MAXV 20

int parent[MAXV];
int find(int x) { return (parent[x] == x) ? x : (parent[x] = find(parent[x])); }
void unionSet(int x, int y) { parent[find(x)] = find(y); }

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

int graph[MAXV][MAXV];
printf("Enter adjacency matrix (0 = no edge, %dx%d):\n", V, V);
for (int i = 0; i < V; i++)
for (int j = 0; j < V; j++)
scanf("%d", &graph[i][j]);

// ---------- Prim's Algorithm ----------

int selected[MAXV] = {0}, primCost = 0;
selected[0] = 1;
printf("Output (Prim's MST edges):\n");
for (int e = 0; e < V - 1; e++) {
int minEdge = INF, u = -1, v = -1;
for (int i = 0; i < V; i++) {
if (selected[i]) {
for (int j = 0; j < V; j++) {
if (!selected[j] && graph[i][j] && graph[i][j] < minEdge) {
minEdge = graph[i][j];
u = i; v = j;
}
}
}
}
printf("%d - %d weight %d\n", u, v, minEdge);
selected[v] = 1;
primCost += minEdge;
}
printf("Output: Prim's Total MST cost = %d\n\n", primCost);

// ---------- Kruskal's Algorithm ----------

int eu[MAXV*MAXV], ev[MAXV*MAXV], ew[MAXV*MAXV], ec = 0;
for (int i = 0; i < V; i++)
for (int j = i + 1; j < V; j++)
if (graph[i][j]) { eu[ec]=i; ev[ec]=j; ew[ec]=graph[i][j]; ec++; }

// Sort edges by weight

for (int i = 0; i < ec - 1; i++)
for (int j = 0; j < ec - i - 1; j++)
if (ew[j] > ew[j+1]) {
int t;
t=ew[j]; ew[j]=ew[j+1]; ew[j+1]=t;
t=eu[j]; eu[j]=eu[j+1]; eu[j+1]=t;
t=ev[j]; ev[j]=ev[j+1]; ev[j+1]=t;
}

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

int kruskalCost = 0;
printf("Output (Kruskal's MST edges):\n");
for (int i = 0; i < ec; i++) {
if (find(eu[i]) != find(ev[i])) {
printf("%d - %d weight %d\n", eu[i], ev[i], ew[i]);
unionSet(eu[i], ev[i]);
kruskalCost += ew[i];
}
}
printf("Output: Kruskal's Total MST cost = %d\n", kruskalCost);

return 0;
}

Sample Input / Output:

Input: 5-vertex weighted graph -> Output: MST edges & total cost from both algorithms
22. BFS and DFS (Graph Traversal)
BFS (Breadth First Search) explores level by level using a queue. DFS (Depth First Search) explores as
deep as possible before backtracking, using a stack (or recursion).

C Program:
#include <stdio.h>
#define MAXV 20

int graph[MAXV][MAXV], visited[MAXV], V;

void bfs(int start) {

int queue[MAXV], front = 0, rear = 0;
int vis[MAXV] = {0};

vis[start] = 1;
queue[rear++] = start;

printf("Output (BFS traversal): ");

while (front < rear) {
int u = queue[front++];
printf("%d ", u);
for (int v = 0; v < V; v++) {
if (graph[u][v] && !vis[v]) {
vis[v] = 1;
queue[rear++] = v;
}
}
}
printf("\n");
}

void dfsUtil(int u, int vis[]) {

vis[u] = 1;
printf("%d ", u);
for (int v = 0; v < V; v++)
if (graph[u][v] && !vis[v])
dfsUtil(v, vis);
}

void dfs(int start) {

int vis[MAXV] = {0};
printf("Output (DFS traversal): ");
dfsUtil(start, vis);
printf("\n");
}

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

printf("Enter adjacency matrix (%dx%d):\n", V, V);

for (int i = 0; i < V; i++)
for (int j = 0; j < V; j++)
scanf("%d", &graph[i][j]);

int start;
printf("Enter starting vertex: ");
scanf("%d", &start);

bfs(start);
dfs(start);

return 0;
}

Sample Input / Output:

Input: 5-vertex graph, start=0 -> Output: BFS order and DFS order
23. Max Flow / Min Cut (Edmonds-Karp using BFS)
Finds the Maximum Flow possible from a source to a sink in a network. By the Max-Flow Min-Cut theorem,
this value also equals the capacity of the smallest 'cut' separating source and sink.

C Program:
#include <stdio.h>
#include <string.h>
#define MAXV 20
#define INF 999999

int capacity_[MAXV][MAXV], V;

int bfsFindPath(int s, int t, int parent[]) {

int visited[MAXV] = {0};
int queue[MAXV], front = 0, rear = 0;
queue[rear++] = s;
visited[s] = 1;
parent[s] = -1;

while (front < rear) {

int u = queue[front++];
for (int v = 0; v < V; v++) {
if (!visited[v] && capacity_[u][v] > 0) {
queue[rear++] = v;
visited[v] = 1;
parent[v] = u;
if (v == t) return 1;
}
}
}
return 0;
}

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

printf("Enter capacity matrix (0 = no edge, %dx%d):\n", V, V);

for (int i = 0; i < V; i++)
for (int j = 0; j < V; j++)
scanf("%d", &capacity_[i][j]);

int s, t;
printf("Enter source and sink: ");
scanf("%d %d", &s, &t);

int parent[MAXV], maxFlow = 0;

while (bfsFindPath(s, t, parent)) {

// Find the smallest capacity (bottleneck) along this path
int pathFlow = INF;
for (int v = t; v != s; v = parent[v])
if (capacity_[parent[v]][v] < pathFlow)
pathFlow = capacity_[parent[v]][v];

// Update capacities along the path

for (int v = t; v != s; v = parent[v]) {
capacity_[parent[v]][v] -= pathFlow;
capacity_[v][parent[v]] += pathFlow;
}
maxFlow += pathFlow;
}

printf("Output: Maximum Flow (= Minimum Cut capacity) = %d\n", maxFlow);

return 0;
}

Sample Input / Output:

Input: 6-vertex flow network, source=0, sink=5 -> Output: Maximum Flow value
24. KMP Algorithm (Knuth-Morris-Pratt)
An efficient string matching algorithm. It pre-computes a 'failure function' (LPS array) for the pattern so it
never re-checks characters it has already matched, making it faster than the naive method.

C Program:
#include <stdio.h>
#include <string.h>

void computeLPS(char *pattern, int m, int *lps) {

int len = 0;
lps[0] = 0;
int i = 1;
while (i < m) {
if (pattern[i] == pattern[len]) {
len++;
lps[i] = len;
i++;
} else if (len != 0) {
len = lps[len - 1];
} else {
lps[i] = 0;
i++;
}
}
}

int main() {
char text[1000], pattern[100];
printf("Enter text: ");
scanf("%s", text);
printf("Enter pattern to search: ");
scanf("%s", pattern);

int n = strlen(text), m = strlen(pattern);

int lps[100];
computeLPS(pattern, m, lps);

int i = 0, j = 0, found = 0;
printf("Output: Pattern found at index: ");
while (i < n) {
if (text[i] == pattern[j]) {
i++; j++;
if (j == m) {
printf("%d ", i - j);
found = 1;
j = lps[j - 1];
}
} else if (j != 0) {
j = lps[j - 1];
} else {
i++;
}
}
if (!found) printf("Not found");
printf("\n");

return 0;
}

Sample Input / Output:

Input: text="ABABDABACDABABCABAB", pattern="ABABCABAB" -> Output: index 10
25. Naive String Matching
The simplest string matching method: slide the pattern over the text one position at a time and check for a
match at every position (Brute Force approach).

C Program:
#include <stdio.h>
#include <string.h>

int main() {
char text[1000], pattern[100];
printf("Enter text: ");
scanf("%s", text);
printf("Enter pattern to search: ");
scanf("%s", pattern);

int n = strlen(text), m = strlen(pattern);

int found = 0;

printf("Output: Pattern found at index: ");

for (int i = 0; i <= n - m; i++) {
int j;
for (j = 0; j < m; j++) {
if (text[i + j] != pattern[j])
break;
}
if (j == m) {
printf("%d ", i);
found = 1;
}
}
if (!found) printf("Not found");
printf("\n");

return 0;
}

Sample Input / Output:

Input: text="AABAACAADAABAABA", pattern="AABA" -> Output: indices 0 9 12
26. Ford-Fulkerson Algorithm (using DFS)
Finds the Maximum Flow in a network by repeatedly finding an 'augmenting path' from source to sink
using DFS, and pushing as much flow as possible along it, until no path remains.

C Program:
#include <stdio.h>
#define MAXV 20
#define INF 999999

int capacity_[MAXV][MAXV], V, visited[MAXV];

int dfsFindPath(int u, int t, int flow, int parent[]) {

if (u == t) return flow;
visited[u] = 1;

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

if (!visited[v] && capacity_[u][v] > 0) {
int minFlow = (flow < capacity_[u][v]) ? flow : capacity_[u][v];
int result = dfsFindPath(v, t, minFlow, parent);
if (result > 0) {
parent[v] = u;
return result;
}
}
}
return 0;
}

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

printf("Enter capacity matrix (0 = no edge, %dx%d):\n", V, V);

for (int i = 0; i < V; i++)
for (int j = 0; j < V; j++)
scanf("%d", &capacity_[i][j]);

int s, t;
printf("Enter source and sink: ");
scanf("%d %d", &s, &t);

int maxFlow = 0, parent[MAXV];

while (1) {
for (int i = 0; i < V; i++) visited[i] = 0;
int flow = dfsFindPath(s, t, INF, parent);
if (flow == 0) break;

// Update capacities backwards along the found path

int v = t;
while (v != s) {
int u = parent[v];
capacity_[u][v] -= flow;
capacity_[v][u] += flow;
v = u;
}
maxFlow += flow;
}

printf("Output: Maximum Flow = %d\n", maxFlow);

return 0;
}

Sample Input / Output:

Input: 6-vertex flow network, source=0, sink=5 -> Output: Maximum Flow value
27. Transitive Closure of a Graph (Warshall's Algorithm)
Tells us which vertices can reach which other vertices, directly or indirectly (through any path). Uses the
same idea as Floyd-Warshall but with reachability (1/0) instead of distances.

C Program:
#include <stdio.h>

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

int reach[20][20];
printf("Enter adjacency matrix (1 = edge, 0 = no edge, %dx%d):\n", V, V);
for (int i = 0; i < V; i++)
for (int j = 0; j < V; j++)
scanf("%d", &reach[i][j]);

// Warshall's algorithm: try every vertex k as an intermediate step

for (int k = 0; k < V; k++)
for (int i = 0; i < V; i++)
for (int j = 0; j < V; j++)
reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j]);

printf("Output: Transitive Closure matrix (1 = i can reach j):\n");

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

return 0;
}

Sample Input / Output:

Input: 4-vertex directed graph matrix -> Output: reachability matrix (1/0)
28. Fast Fourier Transform (FFT)
FFT quickly converts a sequence of numbers from the 'time domain' into the 'frequency domain'. It uses
Divide and Conquer to do in O(n log n) what would normally take O(n^2). Array size must be a power of 2.

C Program:
#include <stdio.h>
#include <math.h>

#define MAXN 64

typedef struct { double re, im; } Complex;

Complex add_c(Complex a, Complex b) { Complex r = {[Link]+[Link], [Link]+[Link]}; return r; }

Complex sub_c(Complex a, Complex b) { Complex r = {[Link], [Link]}; return r; }
Complex mul_c(Complex a, Complex b) {
Complex r = {[Link]*[Link] - [Link]*[Link], [Link]*[Link] + [Link]*[Link]};
return r;
}

// Recursive Cooley-Tukey FFT (n must be a power of 2)

void fft(Complex x[], int n) {
if (n <= 1) return;

Complex even[MAXN], odd[MAXN];

for (int i = 0; i < n / 2; i++) {
even[i] = x[2 * i];
odd[i] = x[2 * i + 1];
}

fft(even, n / 2);
fft(odd, n / 2);

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

double angle = -2 * M_PI * k / n;
Complex t = { cos(angle), sin(angle) };
t = mul_c(t, odd[k]);
x[k] = add_c(even[k], t);
x[k + n / 2] = sub_c(even[k], t);
}
}

int main() {
int n;
printf("Enter number of samples (must be a power of 2, e.g. 4, 8, 16): ");
scanf("%d", &n);

Complex x[MAXN];
printf("Enter %d real-valued samples:\n", n);
for (int i = 0; i < n; i++) {
scanf("%lf", &x[i].re);
x[i].im = 0;
}

fft(x, n);

printf("Output: FFT result (real + imaginary parts):\n");

for (int i = 0; i < n; i++)
printf("X[%d] = %.2f + %.2fi\n", i, x[i].re, x[i].im);

return 0;
}

Sample Input / Output:

Input: 4 samples: 1 2 3 4 -> Output: 4 complex frequency values X[0]..X[3]
29. Strassen's Matrix Multiplication
A faster way to multiply two matrices using Divide and Conquer. For 2x2 matrices, it computes the product
using only 7 multiplications instead of the usual 8, saving work.

C Program:
#include <stdio.h>

int main() {
int a[2][2], b[2][2], c[2][2];

printf("Enter elements of 2x2 Matrix A (row by row):\n");

for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
scanf("%d", &a[i][j]);

printf("Enter elements of 2x2 Matrix B (row by row):\n");

for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
scanf("%d", &b[i][j]);

// Strassen's 7 multiplications
int m1 = (a[0][0] + a[1][1]) * (b[0][0] + b[1][1]);
int m2 = (a[1][0] + a[1][1]) * b[0][0];
int m3 = a[0][0] * (b[0][1] - b[1][1]);
int m4 = a[1][1] * (b[1][0] - b[0][0]);
int m5 = (a[0][0] + a[0][1]) * b[1][1];
int m6 = (a[1][0] - a[0][0]) * (b[0][0] + b[0][1]);
int m7 = (a[0][1] - a[1][1]) * (b[1][0] + b[1][1]);

c[0][0] = m1 + m4 - m5 + m7;
c[0][1] = m3 + m5;
c[1][0] = m2 + m4;
c[1][1] = m1 - m2 + m3 + m6;

printf("Output: Resultant Matrix C = A x B:\n");

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

return 0;
}

Sample Input / Output:

Input: A=[[1,2],[3,4]], B=[[5,6],[7,8]] -> Output: C=[[19,22],[43,50]]
30. 15-Puzzle (Solvability Check + Move Simulation)
The 15-puzzle is a 4x4 grid with tiles 1-15 and one blank space; tiles slide into the blank to reach the goal
order. Solving it fully needs advanced search (like A*), but this program checks whether a given
arrangement CAN be solved, and lets you simulate sliding moves.

C Program:
#include <stdio.h>

int puzzle[4][4], blankRow, blankCol;

// Count inversions to check solvability (classic 15-puzzle rule)

int countInversions(int arr[16]) {
int inv = 0;
for (int i = 0; i < 16; i++)
for (int j = i + 1; j < 16; j++)
if (arr[i] && arr[j] && arr[i] > arr[j])
inv++;
return inv;
}

void printPuzzle() {
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++)
printf("%2d ", puzzle[i][j]);
printf("\n");
}
}

int main() {
int arr[16];
printf("Enter 16 numbers for the 4x4 puzzle (use 0 for the blank tile):\n");
for (int i = 0; i < 16; i++) {
scanf("%d", &arr[i]);
puzzle[i / 4][i % 4] = arr[i];
if (arr[i] == 0) { blankRow = i / 4; blankCol = i % 4; }
}

printf("Output: Initial arrangement:\n");

printPuzzle();

int inversions = countInversions(arr);

int blankRowFromBottom = 4 - blankRow;

// Solvability rule for a 4x4 (even width) puzzle

int solvable;
if (blankRowFromBottom % 2 == 0)
solvable = (inversions % 2 == 1);
else
solvable = (inversions % 2 == 0);

if (!solvable) {
printf("Output: This arrangement is NOT solvable.\n");
return 0;
}
printf("Output: This arrangement IS solvable!\n");

int moves;
printf("Enter number of moves to simulate: ");
scanf("%d", &moves);

printf("Enter moves as U/D/L/R (move blank Up/Down/Left/Right):\n");

for (int m = 0; m < moves; m++) {
char dir;
scanf(" %c", &dir);
int nr = blankRow, nc = blankCol;
if (dir == 'U') nr--;
else if (dir == 'D') nr++;
else if (dir == 'L') nc--;
else if (dir == 'R') nc++;

if (nr >= 0 && nr < 4 && nc >= 0 && nc < 4) {

puzzle[blankRow][blankCol] = puzzle[nr][nc];
puzzle[nr][nc] = 0;
blankRow = nr; blankCol = nc;
} else {
printf("Invalid move, skipped.\n");
 }
}

printf("Output: Puzzle after moves:\n");

printPuzzle();

return 0;
}

Sample Input / Output:

Input: 16 tile values (0=blank) -> Output: solvability + puzzle state after moves