Lab 1: Greatest Common Divisor (GCD) - Iterative

Objective: To find the Greatest Common Divisor (GCD) of two input numbers using the
iterative Euclidean method and analyze its complexity.

1. Theory

The GCD of two integers is the largest positive integer that divides each of the integers without a
remainder. The Euclidean Algorithm is the most efficient method to calculate this. It relies on
the mathematical property that $\text{GCD}(a, b) = \text{GCD}(b, a \pmod b)$. By repeatedly
applying this logic in a loop until the remainder becomes zero, the last non-zero divisor is
identified as the GCD.

2. Algorithm

1. Read two integers a and b.

2. While b is not equal to 0:
o Calculate the remainder: remainder = a % b.
o Update a to the value of b.
o Update b to the value of the remainder.
3. The value of a is the GCD.
4. Print the result.

3. Source Code
#include <stdio.h>
#include <stdlib.h>

int findGCD(int a, int b)

{
while (b != 0)
{
int temp = a % b;
a = b;
b = temp;
}
return a;
}

int main()
{
int n1, n2;

printf("--- GCD Iterative Method ---\n");

printf("Enter first number: ");
if (scanf("%d", &n1) != 1)
return 1;
printf("Enter second number: ");
if (scanf("%d", &n2) != 1)
 return 1;

// Handle negative inputs by taking absolute values

int absN1 = abs(n1);
int absN2 = abs(n2);

int result = findGCD(absN1, absN2);

printf("The GCD of %d and %d is: %d\n", n1, n2, result);

return 0;
}

4. Complexity Analysis

• Time Complexity: $O(\log(\min(a, b)))$. This is extremely efficient because the values
of $a$ and $b$ decrease geometrically in each iteration.
• Space Complexity: $O(1)$. The algorithm uses a fixed amount of space (only a few
integer variables) regardless of the size of the input numbers.

5. Output

6. Conclusion

The iterative method for finding the GCD is robust and performs significantly better than the
brute-force approach (checking all numbers from 1 to $n$). It avoids the stack overhead
associated with recursion, making it the preferred choice for performance-critical applications.
Lab 2: nth Term of Fibonacci Sequence - Iterative
Objective: To find the $n^{th}$ term of the Fibonacci sequence using an iterative approach and
analyze its time and space complexity.

1. Theory

The Fibonacci sequence is a series of numbers where each number is the sum of the two
preceding ones, typically starting with 0 and 1. Mathematically, it is defined as:

• $F(0) = 0$
• $F(1) = 1$
• $F(n) = F(n-1) + F(n-2)$ for $n > 1$

While a recursive solution is elegant, it has an exponential time complexity $O(2^n)$ due to
repeated calculations of the same sub-problems. The iterative method is more efficient as it
computes each term exactly once in a single pass, using three variables to keep track of the
sequence progress.

2. Algorithm

1. Read the input integer n.

2. If n is 0, the result is 0.
3. If n is 1, the result is 1.
4. Initialize a = 0 (first term) and b = 1 (second term).
5. Loop from i = 2 up to n:
o Calculate the next term: c = a + b.
o Update a = b.
o Update b = c.
6. The value of b is the $n^{th}$ Fibonacci term.
7. Print the result.

3. Source Code
#include <stdio.h>

/**

• Function to find the nth Fibonacci term iteratively

• Time Complexity: O(n)
• Space Complexity: O(1)
*/ long long findFibonacci(int n) { if (n <= 1) return n;

long long a = 0, b = 1, c;

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

c = a + b;
 a = b;
b = c;
}

return b;

int main() { int n;

printf("--- Fibonacci Iterative Method ---\n");

printf("Enter the value of n: ");
scanf("%d", &n);

if (n < 0) {
printf("Error: Fibonacci sequence is not defined for negative numbers.\n");
} else {
long long result = findFibonacci(n);
printf("The %dth term of the Fibonacci sequence is: %lld\n", n, result);
}

return 0;

4. Complexity Analysis

• Time Complexity: $O(n)$. The algorithm uses a single loop that iterates from 2 to $n$,
performing constant-time additions in each step.
• Space Complexity: $O(1)$. We only store a fixed number of variables (a, b, c, and i)
regardless of how large $n$ is.

5. Output

6. Conclusion

The iterative approach to finding the Fibonacci sequence is highly efficient for practical use. By
avoiding the recursion stack and redundant calculations, we achieve linear time complexity,
which is a massive improvement over the naive recursive method, especially as $n$ grows larger.

Lab 3: Sequential Search - Iterative Method

Objective: To implement the Sequential (Linear) Search algorithm to find a target element
within an array and analyze its performance.

1. Theory

Sequential Search, also known as Linear Search, is the simplest searching algorithm. It works
by starting at the beginning of a data structure (like an array or list) and comparing the target
value with each element sequentially until a match is found or the end of the structure is reached.

This method does not require the data to be sorted, making it versatile for unsorted collections.
However, its efficiency decreases as the size of the dataset increases.

2. Algorithm

1. Read the size of the array n.

2. Input n elements into the array arr.
3. Read the target value to be searched.
4. Initialize a flag found = -1.
5. Loop from i = 0 to n-1:
o If arr[i] == target:
▪ Set found = i.
▪ Break the loop.

6. If found != -1, print the index where the element was found.
7. Else, print that the element is not present in the array.

3. Source Code (C++)

#include <stdio.h>

/**

• Function to perform Sequential Search

• Time Complexity: O(n)
• Space Complexity: O(1)
*/ int sequentialSearch(int arr[], int n, int target) { for (int i = 0; i < n; i++) { if (arr[i] == target) { return i; //
Return the index if found } } return -1; // Return -1 if not found }

int main() { int n, target;

printf("--- Sequential Search (Linear Search) ---\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]);
}

printf("Enter the element to search for: ");

scanf("%d", &target);

int result = sequentialSearch(arr, n, target);

if (result != -1) {
printf("Element %d found at index: %d\n", target, result);
} else {
printf("Element %d not found in the array.\n", target);
}

return 0;

4. Complexity Analysis

• Time Complexity:
o Best Case: $O(1)$ (The target is the first element).
o Average Case: $O(n)$ (The target is somewhere in the middle).
o Worst Case: $O(n)$ (The target is at the last position or not present).
• Space Complexity: $O(1)$ since no additional data structures are used that scale with
input size.

5. Output

6. Conclusion

Sequential search is easy to implement and works on any array regardless of order. While it is
inefficient for large datasets compared to algorithms like Binary Search, it remains a fundamental
tool for small lists or unsorted data.
Lab 4: Bubble Sort - Iterative Method
Objective: To implement the Bubble Sort algorithm to sort an array of integers in ascending
order and analyze its time and space complexity.

1. Theory

Bubble Sort is a simple comparison-based sorting algorithm. It works by repeatedly stepping

through the list, comparing adjacent elements, and swapping them if they are in the wrong order.
This process is repeated until the entire list is sorted. The algorithm gets its name because smaller
elements "bubble" to the top of the list (beginning of the array) while larger elements sink to the
bottom (end of the array) with each pass.

2. Algorithm

1. Read the size of the array n.

2. Input n elements into the array arr.
3. Use two nested loops:
o The outer loop i runs from 0 to n-1.
o The inner loop j runs from 0 to n-i-1.
4. In the inner loop, compare adjacent elements: if arr[j] > arr[j+1]:
o Swap arr[j] and arr[j+1].
5. After the loops finish, the array is sorted.
6. Print the sorted array.

3. Source Code (C++)

#include <stdio.h>

/**

• Function to perform Bubble Sort

• Time Complexity: O(n^2)
• Space Complexity: O(1)
/ void bubbleSort(int arr[], int n) { for (int i = 0; i < n - 1; i++) { / Flag to optimize: if no two elements were
swapped by inner loop, then break */ int swapped = 0;

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

if (arr[j] > arr[j + 1]) {
/* Swap arr[j] and arr[j+1] */
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = 1;
}
 }

/* If no elements were swapped, array is already sorted */

if (!swapped)
break;
}

int main() { int n;

printf("--- Bubble Sort Iterative ---\n");

printf("Enter 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]);
}

bubbleSort(arr, n);

printf("Sorted array: ");

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

return 0;

}
4. Complexity Analysis

• Time Complexity:
o Best Case: $O(n)$ (Occurs when the array is already sorted and we use a swapped
flag).
o Average Case: $O(n^2)$.
o Worst Case: $O(n^2)$ (Occurs when the array is sorted in reverse order).
• Space Complexity: $O(1)$ because it is an in-place sorting algorithm, requiring only a
constant amount of extra space for the temp variable.

5. Output

6. Conclusion

While Bubble Sort is easy to understand and implement, its $O(n^2)$ time complexity makes it
inefficient for large datasets. However, its ability to detect a sorted list early (with optimization)
and its minimal space requirement make it a useful educational tool for understanding the basics
of sorting logic.
Lab 5: Selection Sort - Iterative Method
Objective: To implement the Selection Sort algorithm to sort an array of integers and analyze its
performance.

1. Theory

Selection Sort is an in-place comparison sorting algorithm. It divides the input list into two parts:
a sorted sublist of items which is built up from left to right, and a sublist of the remaining
unsorted items. In each iteration, the algorithm finds the smallest (or largest) element from the
unsorted sublist and swaps it with the leftmost unsorted element, moving the sublist boundary
one element to the right.

2. Algorithm

1. Read the size of the array n.

2. Input n elements into the array arr.
3. Loop from i = 0 to n-2 (the boundary between sorted and unsorted parts):
o Assume the current element at i is the minimum: min_idx = i.
o Inner loop from j = i+1 to n-1:
▪ If arr[j] < arr[min_idx], update min_idx = j.
o If min_idx is not equal to i, swap arr[i] and arr[min_idx].
4. Print the sorted array.

3. Source Code (C++)

#include <stdio.h>

/**

• Function to perform Selection Sort

• Time Complexity: O(n^2)
• Space Complexity: O(1)
/ void selectionSort(int arr[], int n) { for (int i = 0; i < n - 1; i++) { / Find the minimum element in unsorted
array */ int min_idx = i;

for (int j = i + 1; j < n; j++) {

if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}

/* Swap the found minimum element with the first element */

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

int main() { int n;

printf("--- Selection Sort Iterative ---\n");

printf("Enter 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]);
}

selectionSort(arr, n);

printf("Sorted array: ");

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

return 0;

}
4. Complexity Analysis

• Time Complexity:
o Best Case: $O(n^2)$ (Even if the array is sorted, it still scans the unsorted part).
o Average Case: $O(n^2)$.
o Worst Case: $O(n^2)$.
• Space Complexity: $O(1)$. It is an in-place algorithm as it only requires a constant
amount of extra space for indices and swapping.

5. Output

6. Conclusion

Selection Sort is notable for its simplicity and the fact that it performs a maximum of $O(n)$
swaps. While it has the same asymptotic time complexity as Bubble Sort ($O(n^2)$), it generally
performs better in practice because it minimizes the number of writes to memory (swaps).
However, it remains inefficient for large datasets.
Lab 6: Insertion Sort - Iterative Method
Objective: To implement the Insertion Sort algorithm to sort an array of integers and analyze its
performance in different scenarios.

1. Theory

Insertion Sort is a simple sorting algorithm that works similarly to the way you sort playing cards
in your hands. The array is virtually split into a sorted and an unsorted part. Values from the
unsorted part are picked and placed at the correct position in the sorted part. It is an adaptive
algorithm, meaning it is very efficient for datasets that are already substantially sorted.

2. Algorithm

1. Read the size of the array n.

2. Input n elements into the array arr.
3. Loop from i = 1 to n-1 (assume the first element is already sorted):
o Pick the current element: key = arr[i].
o Set j = i - 1.
o While j >= 0 and arr[j] > key:
▪ Shift arr[j] to the right: arr[j + 1] = arr[j].
▪ Decrement j.
o Place the key at its correct position: arr[j + 1] = key.
4. Print the sorted array.

3. Source Code (C++)

#include <stdio.h>

/**

• Function to perform Insertion Sort

• Time Complexity: O(n^2)
• Space Complexity: O(1)
*/ void insertionSort(int arr[], int n) { for (int i = 1; i < n; i++) { int key = arr[i]; int 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;
}

}
int main() { int n;

printf("--- Insertion Sort Iterative ---\n");

printf("Enter 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]);
}

insertionSort(arr, n);

printf("Sorted array: ");

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

return 0;

}
4. Complexity Analysis

• Time Complexity:
o Best Case: $O(n)$ (Occurs when the array is already sorted; the inner loop never
runs).
o Average Case: $O(n^2)$.
o Worst Case: $O(n^2)$ (Occurs when the array is sorted in reverse order).
• Space Complexity: $O(1)$. Like Selection and Bubble sort, this is an in-place algorithm.

5. Output

6. Conclusion

Insertion Sort is highly efficient for small data sets and is often used as the building block for
more complex algorithms (like Timsort). Its main advantage is its efficiency on "nearly sorted"
data, where it outperforms more complex algorithms like Quick Sort or Merge Sort.
Lab 7: Binary Search - Divide and Conquer
Objective: To implement the Binary Search algorithm using the Divide and Conquer approach
and analyze its logarithmic efficiency.

1. Theory

Binary Search is a highly efficient searching algorithm that works on a sorted array. It follows
the Divide and Conquer paradigm by repeatedly dividing the search interval in half.

• If the value of the search key is less than the item in the middle of the interval, the search
continues in the lower half.
• Otherwise, it continues in the upper half.
• This process continues until the value is found or the interval is empty.

2. Algorithm

1. Read a sorted array arr of size n and the target element.

2. Set low = 0 and high = n - 1.
3. While low <= high:
o Calculate mid = low + (high - low) / 2 (to prevent integer overflow).
o If arr[mid] == target, return mid.
o If target < arr[mid], set high = mid - 1 (Search in the left half).
o If target > arr[mid], set low = mid + 1 (Search in the right half).
4. If the loop ends without a match, return -1.

3. Source Code
#include <stdio.h>

/**

• Function to perform Binary Search using Divide and Conquer

• Time Complexity: O(log n)
• Space Complexity: O(1)
*/ int binarySearch(int arr[], int low, int high, int target) { while (low <= high) { int mid = low + (high - low)
/ 2;

/* Check if target is present at mid */

if (arr[mid] == target)
return mid;

/* If target is smaller, ignore right half */

if (arr[mid] > target)
high = mid - 1;
 /* If target is larger, ignore left half */
else
low = mid + 1;
}

/* Element not found */

return -1;

int main() { int n, target;

printf("--- Binary Search (Divide & Conquer) ---\n");

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

int arr[n];

printf("Enter %d sorted elements:\n", n);

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

printf("Enter element to search for: ");

scanf("%d", &target);

int result = binarySearch(arr, 0, n - 1, target);

if (result != -1)
printf("Element %d found at index: %d\n", target, result);
else
printf("Element %d not found in the array.\n", target);

return 0;

4. Complexity Analysis

• Time Complexity:
o Best Case: $O(1)$ (Target is exactly at the middle).
o Average Case: $O(\log n)$.
 o Worst Case: $O(\log n)$ (Target is at the ends or not present).
• Space Complexity: $O(1)$ for the iterative implementation. (Note: Recursive
implementation would take $O(\log n)$ due to the call stack).

5. Output

6. Conclusion

Binary Search is significantly faster than Sequential Search for large datasets, as it reduces the
search space by half in every step. Its logarithmic time complexity makes it a fundamental
algorithm in computer science, though it strictly requires the input data to be sorted beforehand.
Lab 8: Merge Sort - Divide and Conquer
Objective: To implement the Merge Sort algorithm using the Divide and Conquer approach and
analyze its $O(n \log n)$ efficiency.

1. Theory

Merge Sort is a classic Divide and Conquer algorithm. It works by:

1. Dividing the unsorted list into $n$ sublists, each containing one element (a list of one
element is considered sorted).
2. Conquering by repeatedly merging sublists to produce new sorted sublists until there is
only one sublist remaining.

It is a stable sort and is particularly efficient for large datasets and linked lists. Unlike Quick
Sort, its worst-case performance is guaranteed to be $O(n \log n)$.

2. Algorithm

MergeSort(arr, left, right):

1. If left < right:

o Find the middle point: mid = left + (right - left) / 2.
o Recursively call MergeSort(arr, left, mid).
o Recursively call MergeSort(arr, mid + 1, right).
o Call Merge(arr, left, mid, right) to merge the two halves.

Merge(arr, left, mid, right):

1. Create two temporary arrays L[] and R[].

2. Copy data from arr to L[] (from left to mid) and R[] (from mid+1 to right).
3. Merge the two temporary arrays back into the original arr in sorted order by comparing
elements one by one.

3. Source Code (C++)

#include <stdio.h>

/* Function to merge two halves */ void merge(int arr[], int l, int m, int r) { int n1 = m - l + 1; int n2 = r -
m;

int L[n1], R[n2];

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) {

if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}

while (i < n1) {

arr[k] = L[i];
i++;
k++;
}

while (j < n2) {

arr[k] = R[j];
j++;
k++;
}

/* Main Merge Sort function */ 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;

printf("--- Merge Sort (Divide & Conquer) ---\n");

printf("Enter 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]);
}

mergeSort(arr, 0, n - 1);

printf("Sorted array: ");

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

return 0;

4. Complexity Analysis

• Time Complexity:
o Best Case: $O(n \log n)$
o Average Case: $O(n \log n)$
o Worst Case: $O(n \log n)$
o Note: The time complexity is always $O(n \log n)$ as the array is always divided
into halves and takes linear time to merge.
• Space Complexity: $O(n)$ due to the temporary arrays used during the merge process.

5. Output

6. Conclusion
Merge Sort is a highly reliable sorting algorithm with a consistent time complexity. While it
requires more memory than in-place algorithms like Quick Sort, its stability and predictable
performance make it ideal for sorting large datasets and external sorting.
Lab 9: Quick Sort - Divide and Conquer
Objective: To implement the Quick Sort algorithm using the Divide and Conquer approach and
analyze its performance.

1. Theory

Quick Sort is a highly efficient, in-place sorting algorithm that uses a Divide and Conquer
strategy. It works by selecting a 'pivot' element from the array and partitioning the other elements
into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-
arrays are then sorted recursively.

The choice of pivot can vary (first element, last element, median, or random). In this
implementation, we use the last element as the pivot.

2. Algorithm

QuickSort(arr, low, high):

1. If low < high:

o pi = Partition(arr, low, high)
o QuickSort(arr, low, pi - 1) (Recursive call for left side)
o QuickSort(arr, pi + 1, high) (Recursive call for right side)

Partition(arr, low, high):

1. Set pivot = arr[high].

2. Initialize i = low - 1 (index of the smaller element).
3. Loop j from low to high - 1:
o If arr[j] < pivot:
▪ Increment i.
▪ Swap arr[i] and arr[j].
4. Swap arr[i + 1] and arr[high] (put pivot in its correct place).
5. Return i + 1.

3. Source Code
#include <stdio.h>

/* Function to swap two elements */ void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; }

/* Partition function to place pivot at correct position */ int partition(int arr[], int low, int high) { int pivot
= arr[high]; int i = low - 1;

for (int 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;

/* Main Quick Sort function */ 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("--- Quick Sort (Divide & Conquer) ---\n");

printf("Enter 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: ");

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

return 0;

}
4. Complexity Analysis

• Time Complexity:
o Best Case: $O(n \log n)$ (Occurs when the partition process always picks the
middle element as pivot).
o Average Case: $O(n \log n)$.
o Worst Case: $O(n^2)$ (Occurs when the pivot is always the smallest or largest
element, e.g., in an already sorted array).
• Space Complexity: $O(\log n)$ due to the recursive stack space. Unlike Merge Sort, it is
an in-place algorithm as it doesn't require extra arrays.

5. Output

6. Conclusion

Quick Sort is often faster than Merge Sort in practice because it has a smaller constant factor and
is in-place. However, its worst-case $O(n^2)$ performance is a disadvantage, which can be
mitigated by using a randomized pivot.
Lab 10: Randomized Quick Sort
Objective: To implement the Randomized Quick Sort algorithm and analyze how random pivot
selection helps avoid the $O(n^2)$ worst-case scenario.

1. Theory

Standard Quick Sort can degrade to $O(n^2)$ time complexity if the input array is already sorted
or nearly sorted, as the pivot (often the last or first element) creates highly unbalanced partitions.

Randomized Quick Sort introduces a degree of randomness by picking a random index as the
pivot. This ensures that on average, the partitions are reasonably balanced regardless of the initial
order of the data. This technique makes the $O(n^2)$ worst-case extremely unlikely, maintaining
an expected time complexity of $O(n \log n)$.

2. Algorithm

Randomized_Partition(arr, low, high):

1. Generate a random number r between low and high.

2. Swap arr[r] with arr[high].
3. Call the standard Partition function (using high as pivot).

QuickSort(arr, low, high):

1. If low < high:

o pi = Randomized_Partition(arr, low, high).
o Recursively call QuickSort(arr, low, pi - 1).
o Recursively call QuickSort(arr, pi + 1, high).

3. Source Code (C++)

#include <stdio.h> #include <stdlib.h> /* For rand() and srand() / #include <time.h> / For time() */

/* Function to swap two elements */ void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; }

/* Standard partition function */ int partition(int arr[], int low, int high) { int pivot = arr[high]; int i = low -
1;

for (int 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;

/* Function to pick a random pivot and swap with the last element */ int partition_random(int arr[], int
low, int high) { int random = low + rand() % (high - low + 1);

swap(&arr[random], &arr[high]);
return partition(arr, low, high);

/* Main Randomized Quick Sort function */ void quickSort(int arr[], int low, int high) { if (low < high) { int
pi = partition_random(arr, low, high);

quickSort(arr, low, pi - 1);

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

int main() { int n;

/* Seed the random number generator once */

srand(time(NULL));

printf("--- Randomized Quick Sort ---\n");

printf("Enter 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: ");

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

4. Complexity Analysis

• Time Complexity:
o Average Case: $O(n \log n)$.
o Best Case: $O(n \log n)$.
o Worst Case: $O(n^2)$ (Mathematically possible but practically non-existent with
random pivots).
• Space Complexity: $O(\log n)$ for the recursive stack. It remains an in-place sorting
algorithm.

5. Output

6. Conclusion

Randomized Quick Sort is a robust version of the algorithm that provides high performance
across all types of input distributions. By using a random pivot, we eliminate the vulnerability to
pre-sorted data, making it one of the most reliable and widely used sorting techniques in modern
computing.
Lab 11: Heap Sort - Comparison-Based Sorting
Objective: To implement the Heap Sort algorithm using a binary heap data structure and analyze
its $O(n \log n)$ efficiency.

1. Theory

Heap Sort is a comparison-based sorting technique based on a Binary Heap data structure. It is
similar to selection sort where we first find the maximum element and place it at the end. We
repeat the same process for the remaining elements.

• Max-Heap: A complete binary tree where the value of the root node is greater than or
equal to the values of its children.
• Heapify: The process of creating a heap data structure from a binary tree.

2. Algorithm

HeapSort(arr):

1. Build a max heap from the input data.

2. At this point, the largest item is stored at the root of the heap. Replace it with the last item
of the heap followed by reducing the size of the heap by 1.
3. Heapify the root of the tree.
4. Repeat step 2 while the size of the heap is greater than 1.

Heapify(arr, n, i):

1. Initialize largest as i.
2. Left child: l = 2*i + 1, Right child: r = 2*i + 2.
3. If left child is larger than root, update largest.
4. If right child is larger than largest, update largest.
5. If largest is not root, swap root with largest and recursively heapify the affected sub-
tree.

3. Source Code (C++)

#include <stdio.h>

/* Function to swap two elements */ void swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp; }

/* To heapify a subtree rooted with node i */ void heapify(int arr[], int n, int i) { int largest = i; int l = 2 * i
+ 1; int 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);
}

/* 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);

/* One by one extract elements from heap */

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

int main() { int n;

printf("--- Heap Sort ---\n");

printf("Enter 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]);

heapSort(arr, n);

printf("Sorted array: ");

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

return 0;

}
4. Complexity Analysis

• Time Complexity: $O(n \log n)$ for all cases (Best, Average, and Worst). Building the
heap takes $O(n)$ and each of the $n$ extractions takes $O(\log n)$.
• Space Complexity: $O(1)$. It is an in-place sorting algorithm as it requires no extra
storage space beyond the original array.

5. Output

6. Conclusion

Heap Sort is a very efficient and reliable algorithm. While it is often slightly slower in practice
than a well-implemented Quick Sort, its worst-case time complexity of $O(n \log n)$ and $O(1)$
space complexity make it ideal for systems with strict memory constraints or where guaranteed
performance is required.
Lab 12: Fractional Knapsack Problem - Greedy Approach
Objective: To implement the Fractional Knapsack problem using a Greedy strategy to maximize
the total value of items in a knapsack of limited capacity.

1. Theory

The Fractional Knapsack Problem differs from the 0/1 Knapsack problem because it allows us
to take fractions of an item rather than having to take the item as a whole. This property makes it
solvable using a Greedy Approach.

The greedy strategy is to calculate the Value-to-Weight ratio ($\frac{v_i}{w_i}$) for every
item and sort the items in descending order of this ratio. We then take as much as possible of the
item with the highest ratio, then the next, and so on, until the knapsack is full.

2. Algorithm

1. Define a structure Item with value and weight.

2. Calculate the ratio value/weight for each item.
3. Sort all items in decreasing order of this ratio.
4. Initialize totalValue = 0.0 and currentWeight = 0.
5. Iterate through the sorted items:
o If adding the whole item doesn't exceed capacity:
▪ Add the whole item's value to totalValue.
▪ Add item's weight to currentWeight.
o Else (if the knapsack can only take a fraction):
▪ Add the fraction of the item's value that fits the remaining capacity.
▪ Break the loop.
6. Return totalValue.

3. Source Code (C++)

#include <stdio.h>

/* Structure for an item */ struct Item { int value, weight; };

/* Swap two items */ void swap(struct Item *a, struct Item *b) { struct Item temp = *a; *a = *b; *b =
temp; }

/* Comparison function for sorting by value/weight ratio */ int compare(struct Item a, struct Item b) {
double r1 = (double)[Link] / [Link]; double r2 = (double)[Link] / [Link]; return r1 > r2; }
/* Simple bubble sort to sort items by ratio (descending) */ void sortItems(struct Item arr[], int n) { for
(int i = 0; i < n - 1; i++) { for (int j = 0; j < n - i - 1; j++) { if (!compare(arr[j], arr[j + 1])) { swap(&arr[j], &arr[j
+ 1]); } } } }

/* Fractional Knapsack function */ double fractionalKnapsack(int W, struct Item arr[], int n) {

sortItems(arr, n);

int curWeight = 0;
double finalValue = 0.0;

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

if (curWeight + arr[i].weight <= W) {
curWeight += arr[i].weight;
finalValue += arr[i].value;
} else {
int remain = W - curWeight;
finalValue += arr[i].value * ((double)remain / arr[i].weight);
break;
}
}

return finalValue;

int main() { int n, W;

printf("--- Fractional Knapsack (Greedy) ---\n");

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

printf("Enter capacity of knapsack: ");

scanf("%d", &W);

struct Item arr[n];

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

printf("Enter value and weight for item %d: ", i + 1);
scanf("%d %d", &arr[i].value, &arr[i].weight);
}

printf("Maximum value in Knapsack = %.2f\n",

fractionalKnapsack(W, arr, n));

return 0;
}

4. Complexity Analysis

• Time Complexity: $O(n \log n)$. This is primarily due to sorting the items based on their
value-to-weight ratio. The subsequent greedy loop runs in $O(n)$.
• Space Complexity: $O(1)$ if sorting is done in-place (or $O(n)$ if we count the storage
of the item structures).

5. Output

6. Conclusion

The Greedy approach provides an optimal solution for the Fractional Knapsack problem. By
prioritizing items with the highest "density" of value, we ensure that every unit of capacity in the
knapsack is utilized as efficiently as possible. Note that this greedy logic does not work for the
0/1 Knapsack problem, which requires Dynamic Programming.
Lab 13: Kruskal’s Algorithm for Minimum Spanning Tree
(MST)
Objective: To implement Kruskal’s algorithm using the Greedy approach and Disjoint Set Union
(DSU) to find the Minimum Spanning Tree of a connected, weighted graph.

1. Theory

Kruskal’s algorithm is a Greedy algorithm that finds an MST for a connected weighted graph.
An MST is a subset of edges that connects all vertices together, without any cycles, and with the
minimum possible total edge weight.

The algorithm works by:

1. Sorting all edges in non-decreasing order of their weight.

2. Picking the smallest edge.
3. Checking if adding the edge forms a cycle using the Union-Find (Disjoint Set) data
structure.
4. If no cycle is formed, include the edge in the MST.
5. Repeat until there are $(V-1)$ edges in the MST.

2. Algorithm

1. Create a graph structure with V vertices and a list of edges.

2. Sort all edges from low weight to high weight.
3. Initialize a Disjoint Set where each vertex is its own parent.
4. Iterate through the sorted edges:
o Find the root of the sets containing the two endpoints of the edge.
o If the roots are different (meaning they belong to different components):
▪ Add the edge to the results.
▪ Perform a Union operation on the two sets.
5. Print the edges of the MST and the total weight.

3. Source Code (C++)

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

/* Structure to represent an edge */ struct Edge { int src, dest, weight; };

/* Disjoint Set structure */ struct DisjointSets { int *parent, *rank; int n; };

/* Create Disjoint Set / struct DisjointSets createDSU(int n) { struct DisjointSets* ds = (struct
DisjointSets*)malloc(sizeof(struct DisjointSets)); ds->n = n;

ds->parent = (int*)malloc((n + 1) * sizeof(int));

ds->rank = (int*)malloc((n + 1) * sizeof(int));

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

ds->parent[i] = i;
ds->rank[i] = 0;
}

return ds;

/* Find with path compression / int find(struct DisjointSets ds, int i) { if (ds->parent[i] == i) return i; return
ds->parent[i] = find(ds, ds->parent[i]); }

/* Union by rank / void unite(struct DisjointSets ds, int x, int y) { int rootX = find(ds, x); int rootY = find(ds,
y);

if (rootX != rootY) {
if (ds->rank[rootX] < ds->rank[rootY]) {
ds->parent[rootX] = rootY;
} else if (ds->rank[rootX] > ds->rank[rootY]) {
ds->parent[rootY] = rootX;
} else {
ds->parent[rootY] = rootX;
ds->rank[rootX]++;
}
}

/* Compare edges for sorting */ int compareEdges(const void *a, const void *b) { struct Edge e1 = (struct
Edge)a; struct Edge e2 = (struct Edge)b; return e1->weight - e2->weight; }

/* Kruskal's Algorithm */ void kruskalMST(struct Edge edges[], int V, int E) { qsort(edges, E, sizeof(struct
Edge), compareEdges);

struct DisjointSets* ds = createDSU(V);

struct Edge mst[E];

int mstWeight = 0;
int mstSize = 0;
for (int i = 0; i < E; i++) {
int u = edges[i].src;
int v = edges[i].dest;

if (find(ds, u) != find(ds, v)) {

unite(ds, u, v);
mst[mstSize++] = edges[i];
mstWeight += edges[i].weight;
}
}

printf("Edges in the MST:\n");

for (int i = 0; i < mstSize; i++) {
printf("%d -- %d == %d\n",
mst[i].src, mst[i].dest, mst[i].weight);
}

printf("Minimum Spanning Tree Weight: %d\n", mstWeight);

int main() { int V, E;

printf("--- Kruskal's Algorithm for MST ---\n");

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

struct Edge edges[E];

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

printf("Enter src, dest, and weight for edge %d: ", i + 1);
scanf("%d %d %d", &edges[i].src, &edges[i].dest, &edges[i].weight);
}

kruskalMST(edges, V, E);

return 0;

4. Complexity Analysis
• Time Complexity: $O(E \log E)$ or $O(E \log V)$. Sorting the edges takes $O(E \log
E)$. The Union-Find operations take $O(E \alpha(V))$, where $\alpha$ is the nearly
constant inverse Ackermann function.
• Space Complexity: $O(V + E)$ to store the edges and the Disjoint Set structure.
5. Output

6. Conclusion

Kruskal’s algorithm is efficient for sparse graphs (graphs with fewer edges). By greedily
selecting the smallest edges and using a Disjoint Set to prevent cycles, it guarantees an optimal
Minimum Spanning Tree.
Lab 14: Prim’s Algorithm for Minimum Spanning Tree
(MST)
Objective: To implement Prim’s algorithm using a Greedy approach to find the Minimum
Spanning Tree of a connected, weighted, and undirected graph.

1. Theory

Prim’s algorithm is a Greedy algorithm that builds the MST one vertex at a time. It starts from
an arbitrary root vertex and grows the tree by repeatedly adding the cheapest edge from the tree
to a vertex not yet in the tree.

Unlike Kruskal's, which focuses on edges, Prim's focuses on vertices. It is particularly efficient
for dense graphs (graphs with many edges relative to the number of vertices).

2. Algorithm

1. Initialize a set mstSet to keep track of vertices included in MST.

2. Assign a key value to all vertices in the graph. Initialize all keys as infinite ($\infty$),
except for the first vertex which is set to 0.
3. While mstSet does not include all vertices:
o Pick a vertex u which is not in mstSet and has the minimum key value.
o Include u in mstSet.
o Update the key value of all adjacent vertices of u. To update, iterate through the
adjacent vertices; for every adjacent vertex v, if the weight of edge (u, v) is less
than the current key value of v, update the key value as the weight of (u, v).
4. Store the parent of each vertex to reconstruct the MST.

3. Source Code (C++)

#include <stdio.h> #include <limits.h>

#define V 5

/* Function to find the vertex with minimum key value */ int minKey(int key[], int mstSet[]) { int min =
INT_MAX; int min_index = -1;

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

if (mstSet[v] == 0 && key[v] < min) {
min = key[v];
min_index = v;
}
}

return min_index;
}

/* Function to print the constructed MST */ void printMST(int parent[], int graph[V][V]) { printf("Edge
\tWeight\n");

int totalWeight = 0;

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

printf("%d - %d \t%d\n", parent[i], i, graph[i][parent[i]]);
totalWeight += graph[i][parent[i]];
}

printf("Minimum Spanning Tree Weight: %d\n", totalWeight);

void primMST(int graph[V][V]) { int parent[V]; int key[V]; int mstSet[V];

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

key[i] = INT_MAX;
mstSet[i] = 0;
}

key[0] = 0;
parent[0] = -1;

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

int u = minKey(key, mstSet);
mstSet[u] = 1;

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

if (graph[u][v] &&
mstSet[v] == 0 &&
graph[u][v] < key[v]) {

parent[v] = u;
key[v] = graph[u][v];
}
}
}

printMST(parent, graph);

int main() { int graph[V][V] = { {0, 2, 0, 6, 0}, {2, 0, 3, 8, 5}, {0, 3, 0, 0, 7}, {6, 8, 0, 0, 9}, {0, 5, 7, 9, 0} };
printf("--- Prim's Algorithm for MST ---\n");

primMST(graph);

return 0;

4. Complexity Analysis

• Time Complexity:
o $O(V^2)$ with Adjacency Matrix (as implemented above).
o $O(E \log V)$ with Adjacency List and Min-Priority Queue (Fibonacci Heap can
reduce this further).
• Space Complexity: $O(V)$ to store the keys, parents, and the set of included vertices.

5. Output

6. Conclusion

Prim’s algorithm effectively finds the MST by expanding a single tree component. Its
performance on dense graphs makes it a superior choice over Kruskal's in such scenarios. By
consistently choosing the edge with the lowest weight connected to the current tree, it ensures a
global minimum total weight.
Lab 15: Dijkstra’s Algorithm - Single Source Shortest Path
(SSSP)
Objective: To implement Dijkstra’s algorithm to find the shortest path from a starting vertex to
all other vertices in a weighted graph with non-negative edge weights.

1. Theory

Dijkstra’s algorithm is a Greedy algorithm used to solve the single-source shortest path
problem. It maintains a set of visited vertices and a set of unvisited vertices. It repeatedly picks
the unvisited vertex with the minimum distance from the source, "relaxes" its neighbors by
updating their distances, and marks the vertex as visited.

It works on the principle that the shortest path to a vertex $v$ can be found by evaluating the
shortest paths to all its neighbors $u$ and adding the weight of the edge $(u, v)$.

2. Algorithm

1. Initialize distances to all vertices as infinity ($\infty$) and the source distance as 0.
2. Create a visited array (or set) to keep track of vertices included in the shortest-path tree.
3. While there are unvisited vertices:
oPick a vertex u that has the minimum distance and is not yet visited.
oMark u as visited.
oFor each neighbor v of u:
▪ If dist[u] + weight(u, v) < dist[v]:
▪ Update dist[v] = dist[u] + weight(u, v).
4. Print the final distance array.

3. Source Code (C++)

#include <stdio.h> #include <limits.h>

#define V 9

/* Function to find the vertex with minimum distance value */ int minDistance(int dist[], int sptSet[]) { int
min = INT_MAX; int min_index = -1;

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

if (sptSet[v] == 0 && dist[v] <= min) {
min = dist[v];
min_index = v;
}
}

return min_index;
}

/* Function to print the constructed distance array */ void printSolution(int dist[]) { printf("Vertex \t
Distance from Source\n");

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

printf("%d \t\t %d\n", i, dist[i]);
}

void dijkstra(int graph[V][V], int src) { int dist[V]; int sptSet[V];

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

dist[i] = INT_MAX;
sptSet[i] = 0;
}

dist[src] = 0;

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

int u = minDistance(dist, sptSet);
sptSet[u] = 1;

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

if (!sptSet[v] &&
graph[u][v] &&
dist[u] != INT_MAX &&
dist[u] + graph[u][v] < dist[v]) {

dist[v] = dist[u] + graph[u][v];

}
}
}

printSolution(dist);

int main() { int graph[V][V] = { {0, 4, 0, 0, 0, 0, 0, 8, 0}, {4, 0, 8, 0, 0, 0, 0, 11, 0}, {0, 8, 0, 7, 0, 4, 0, 0, 2}, {0,
0, 7, 0, 9, 14, 0, 0, 0}, {0, 0, 0, 9, 0, 10, 0, 0, 0}, {0, 0, 4, 14, 10, 0, 2, 0, 0}, {0, 0, 0, 0, 0, 2, 0, 1, 6}, {8, 11, 0,
0, 0, 0, 1, 0, 7}, {0, 0, 2, 0, 0, 0, 6, 7, 0} };

printf("--- Dijkstra's Algorithm (SSSP) ---\n");

dijkstra(graph, 0);
return 0;

4. Complexity Analysis

• Time Complexity:
o $O(V^2)$ with an Adjacency Matrix (as shown above).
o $O(E \log V)$ with an Adjacency List and a binary heap (priority queue).
• Space Complexity: $O(V)$ to store the distances and the visited status of vertices.

5. Output

6. Conclusion

Dijkstra’s algorithm is the gold standard for finding the shortest path when all edge weights are
non-negative. Its greedy nature ensures that once a vertex is added to the "Shortest Path Tree
Set," its minimum distance from the source is finalized. However, it does not work correctly with
negative edge weights, for which algorithms like Bellman-Ford must be used.
Lab 16: Bellman-Ford Algorithm - Single Source Shortest
Path
Objective: To implement the Bellman-Ford algorithm to find the shortest paths from a single
source vertex to all other vertices in a weighted graph, even in the presence of negative edge
weights.

1. Theory

While Dijkstra’s algorithm is efficient, it fails when a graph contains negative edge weights. The
Bellman-Ford algorithm solves this by relaxing all edges of the graph $V-1$ times (where $V$ is
the number of vertices).

A key feature of Bellman-Ford is its ability to detect negative weight cycles. If we can still relax
an edge after $V-1$ iterations, it means a negative cycle exists, and a shortest path cannot be
defined because we could infinitely decrease the path weight by traversing the cycle.

2. Algorithm

1. Initialize distances from the source to all vertices as infinity ($\infty$) and source distance
as 0.
2. Relaxation Phase: Repeat the following $V-1$ times:
o For every edge $(u, v)$ with weight $w$:
▪ If dist[u] + w < dist[v]:
▪ Update dist[v] = dist[u] + w.
3. Detection Phase: For every edge $(u, v)$ with weight $w$:
o If dist[u] + w < dist[v]:
▪ Report "Graph contains a negative weight cycle."

4. If no cycle is detected, print the distances.

3. Source Code (C++)

#include <stdio.h> #include <limits.h>

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

void bellmanFord(int V, int E, int src, struct Edge edges[]) { int dist[V];

/* Initialize distances */
for (int i = 0; i < V; i++)
dist[i] = INT_MAX;

dist[src] = 0;

/* Step 1: Relax all edges V - 1 times */

for (int i = 1; i <= V - 1; i++) {
 for (int j = 0; j < E; j++) {
int u = edges[j].src;
int v = edges[j].dest;
int weight = edges[j].weight;

if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {

dist[v] = dist[u] + weight;
}
}
}

/* Step 2: Check for negative-weight cycles */

for (int i = 0; i < E; i++) {
int u = edges[i].src;
int v = edges[i].dest;
int weight = edges[i].weight;

if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {

printf("Graph contains a negative weight cycle!\n");
return;
}
}

/* Print result */
printf("Vertex \t Distance from Source\n");

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

if (dist[i] == INT_MAX)
printf("%d \t\t -1\n", i);
else
printf("%d \t\t %d\n", i, dist[i]);
}

int main() { int V, E, src;

printf("--- Bellman-Ford Algorithm ---\n");

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

struct Edge edges[E];

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

printf("Edge %d (src dest weight): ", i + 1);
 scanf("%d %d %d",
&edges[i].src,
&edges[i].dest,
&edges[i].weight);
}

printf("Enter source vertex: ");

scanf("%d", &src);

bellmanFord(V, E, src, edges);

return 0;

}
4. Complexity Analysis

• Time Complexity: $O(V \times E)$. Since we relax all $E$ edges $V-1$ times, the
complexity is proportional to the product of vertices and edges.
• Space Complexity: $O(V)$ to store the distance array.

5. Output

6. Conclusion

The Bellman-Ford algorithm is more versatile than Dijkstra’s because it handles negative weights
and identifies problematic cycles. Although it is slower ($O(VE)$ vs $O(E \log V)$), it is a
fundamental tool for network routing protocols (like RIP) where negative costs or edge changes
might occur.
Lab 17: Floyd-Warshall Algorithm - All-Pairs Shortest Path
Objective: To implement the Floyd-Warshall algorithm using Dynamic Programming to find the
shortest distances between every pair of vertices in a weighted graph.

1. Theory

Unlike Dijkstra or Bellman-Ford, which find the shortest path from a single source, the Floyd-
Warshall algorithm finds the shortest paths between all pairs of vertices in $O(V^3)$ time.

It works by iteratively considering each vertex $k$ as an intermediate point. For every pair of
vertices $(i, j)$, the algorithm checks if passing through $k$ provides a shorter path than the
current known path from $i$ to $j$. The state transition is defined as:
$$dist[i][j] = \min(dist[i][j], dist[i][k] + dist[k][j])$$

2. Algorithm

1. Initialize a distance matrix dist[V][V] with the weights of the edges.

2. Set dist[i][i] = 0 and dist[i][j] = ∞ if there is no direct edge between $i$ and $j$.
3. Use three nested loops:
oThe outermost loop k represents the intermediate vertex (from $0$ to $V-1$).
oThe inner loops i (source) and j (destination) iterate through all pairs.
4. Update dist[i][j] using the transition formula.
5. After the loops finish, the matrix contains the all-pairs shortest paths.

3. Source Code (C++)

#include <stdio.h>

#define INF 99999 #define V 4

void printSolution(int dist[V][V]) { printf("Shortest distances between every pair of vertices:\n");

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

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

void floydWarshall(int graph[V][V]) { int dist[V][V];

/* Initialize solution matrix same as input graph */
for (int i = 0; i < V; i++)
for (int j = 0; j < V; j++)
dist[i][j] = graph[i][j];

/* Add all vertices one by one as intermediate nodes */

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] != INF &&
dist[k][j] != INF &&
dist[i][k] + dist[k][j] < dist[i][j]) {

dist[i][j] = dist[i][k] + dist[k][j];

}
}
}
}

printSolution(dist);

int main() { int graph[V][V] = { {0, 5, INF, 10}, {INF, 0, 3, INF}, {INF, INF, 0, 1}, {INF, INF, INF, 0} };

printf("--- Floyd-Warshall Algorithm (All-Pairs Shortest Path) ---\n");

floydWarshall(graph);

return 0;

}
4. Complexity Analysis

• Time Complexity: $O(V^3)$. The three nested loops each run $V$ times.
• Space Complexity: $O(V^2)$ to maintain the 2D distance matrix.

5. Output

6. Conclusion

Floyd-Warshall is an elegant application of Dynamic Programming. While $O(V^3)$ is slower

than running Dijkstra multiple times for sparse graphs, its simplicity and ability to handle
negative edge weights (as long as there are no negative cycles) make it a standard choice for all-
pairs shortest path problems.
Lab 18: Matrix Chain Multiplication (MCM)
Objective: To implement the Matrix Chain Multiplication algorithm using Dynamic
Programming to find the most efficient way to multiply a given sequence of matrices.

1. Theory

Matrix multiplication is associative, meaning the order in which we parenthesize the product
affects the number of scalar multiplications required. For example, if we have three matrices $A,
B,$ and $C$, we can compute $(AB)C$ or $A(BC)$. The total number of multiplications can
vary significantly between these choices.

The Matrix Chain Multiplication problem does not actually perform the multiplication; its goal
is to find the optimal parenthesis arrangement that minimizes the total cost (scalar
multiplications). This is a classic Dynamic Programming problem because it exhibits
overlapping subproblems and optimal substructure.

2. Algorithm

1. Let the dimensions of $n$ matrices be given in an array $P[]$ where matrix $A_i$ has
dimensions $P[i-1] \times P[i]$.
2. Create a 2D table m[n][n] where m[i][j] stores the minimum number of multiplications
needed to compute the matrix $A_i \dots A_j$.
3. Base Case: m[i][i] = 0 (cost to multiply one matrix is zero).
4. Recursive Step: For a chain of length L (from 2 to $n$):
o For each subchain (i, j) of length L:
▪ Try every possible split point k between i and j.
▪ m[i][j] = min(m[i][k] + m[k+1][j] + P[i-1]*P[k]*P[j]).
5. The value in m[1][n-1] will be the minimum cost.

3. Source Code (C++)

#include <stdio.h> #include <limits.h>

/**

• Function to find minimum number of scalar multiplications

• needed to multiply a chain of matrices.
*/ int matrixChainOrder(int p[], int n) { int m[n][n];

/* Cost is 0 when multiplying one matrix */

for (int i = 1; i < n; i++)
m[i][i] = 0;

/* L is chain length */
for (int L = 2; L < n; L++) {
for (int i = 1; i < n - L + 1; i++) {
 int j = i + L - 1;
m[i][j] = INT_MAX;

for (int k = i; k <= j - 1; k++) {

int q = m[i][k] + m[k + 1][j]
+ p[i - 1] * p[k] * p[j];

if (q < m[i][j])
m[i][j] = q;
}
}
}

return m[1][n - 1];

int main() { int n;

printf("--- Matrix Chain Multiplication ---\n");

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

int p[n + 1];

printf("Enter the dimensions (sequence of %d values):\n", n + 1);

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

printf("Minimum number of multiplications is: %d\n",

matrixChainOrder(p, n + 1));

return 0;

}
4. Complexity Analysis

• Time Complexity: $O(n^3)$. There are three nested loops: one for the chain length, one
for the starting index, and one for the split point.
• Space Complexity: $O(n^2)$ to store the m table that holds the minimum costs for all
subchains.

5. Output

6. Conclusion

Matrix Chain Multiplication demonstrates how Dynamic Programming can optimize processes
by solving smaller sub-problems and storing their results. By calculating the cost of smaller
chains first, we can efficiently determine the optimal parenthesization for the entire sequence,
avoiding the exponential complexity of a brute-force approach.
Lab 19: Longest Common Subsequence (LCS)
Objective: To implement the Longest Common Subsequence algorithm using Dynamic
Programming to find the length of the longest subsequence present in two strings.

1. Theory

A subsequence is a sequence that appears in the same relative order, but not necessarily
contiguously. For example, "abc", "abd", and "ace" are subsequences of "abcdef". The Longest
Common Subsequence (LCS) problem is to find the longest subsequence common to two given
strings.

This problem follows the Dynamic Programming approach because it has:

• Optimal Substructure: The solution to the problem can be defined in terms of solutions
to its subproblems.
• Overlapping Subproblems: The same subproblems are solved multiple times if a simple
recursive approach is used.

2. Algorithm

1. Let the two strings be X of length m and Y of length n.

2. Create a 2D table L[m+1][n+1].
3. Iterate through the strings using nested loops (i from 0 to m, j from 0 to n):
o
If i == 0 or j == 0, set L[i][j] = 0.
o
If X[i-1] == Y[j-1], the characters match: L[i][j] = L[i-1][j-1] + 1.
o
If X[i-1] != Y[j-1], the characters do not match: L[i][j] = max(L[i-1][j],
L[i][j-1]).
4. The value L[m][n] contains the length of the LCS.

3. Source Code (C++)

#include <stdio.h> #include <string.h>

/* Function to find maximum of two numbers */ int max(int a, int b) { return (a > b) ? a : b; }

/* Function to find the length of LCS */ int lcs(char X[], char Y[]) { int m = strlen(X); int n = strlen(Y);

int L[m + 1][n + 1];

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

for (int j = 0; j <= n; j++) {
if (i == 0 || j == 0)
L[i][j] = 0;
else if (X[i - 1] == Y[j - 1])
L[i][j] = L[i - 1][j - 1] + 1;
 else
L[i][j] = max(L[i - 1][j], L[i][j - 1]);
}
}

return L[m][n];

int main() { char s1[100], s2[100];

printf("--- Longest Common Subsequence ---\n");

printf("Enter first string: ");
scanf("%s", s1);

printf("Enter second string: ");

scanf("%s", s2);

printf("Length of LCS is: %d\n", lcs(s1, s2));

return 0;

4. Complexity Analysis

• Time Complexity: $O(m \times n)$, where $m$ and $n$ are the lengths of the two
strings. We fill every cell in the $(m+1) \times (n+1)$ table.
• Space Complexity: $O(m \times n)$ to store the 2D table.

5. Output

6. Conclusion

The Dynamic Programming approach to LCS is significantly more efficient than the naive
recursive approach, which has exponential time complexity. This algorithm is widely used in
bioinformatics for DNA sequence alignment and in revision control systems (like diff) to
compare files.
Lab 20: 0/1 Knapsack Problem - Dynamic Programming
Objective: To implement the 0/1 Knapsack problem using Dynamic Programming to find the
maximum value that can be carried in a knapsack of a specific capacity.

1. Theory

In the 0/1 Knapsack problem, you are given a set of items, each with a weight and a value. You
need to determine the number of each item to include in a collection so that the total weight is
less than or equal to a given limit and the total value is as large as possible.

Unlike the Fractional Knapsack problem (Lab 12), you cannot break items; you either take the
item (1) or leave it (0). This "all-or-nothing" property makes the greedy approach fail, requiring
Dynamic Programming to find the optimal solution by exploring subproblems.

2. Algorithm

1. Let W be the capacity and n be the number of items.

2. Create a 2D array K[n+1][W+1].
3. Iterate through each item i from 0 to n and each weight w from 0 to W:
o If i == 0 or w == 0, set K[i][w] = 0.
o If weight of the current item wt[i-1] <= w:
▪ K[i][w] = max(val[i-1] + K[i-1][w - wt[i-1]], K[i-1][w])
o Else:
▪ K[i][w] = K[i-1][w]
4. The result is stored in K[n][W].

3. Source Code (C++)

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

/**

• Function to solve 0/1 Knapsack problem using DP

• Time Complexity: O(n * W)
• Space Complexity: O(n * W)
*/ int knapSack(int W, int wt[], int val[], int n) { int i, w;

/* Create DP table */
int **K = (int **)malloc((n + 1) * sizeof(int *));
for (i = 0; i <= n; i++) {
K[i] = (int *)malloc((W + 1) * sizeof(int));
}
/* Build table K[][] in bottom-up manner */
for (i = 0; i <= n; i++) {
for (w = 0; w <= W; w++) {
if (i == 0 || w == 0)
K[i][w] = 0;
else if (wt[i - 1] <= w)
K[i][w] = (val[i - 1] + K[i - 1][w - wt[i - 1]] > K[i - 1][w])
? (val[i - 1] + K[i - 1][w - wt[i - 1]])
: K[i - 1][w];
else
K[i][w] = K[i - 1][w];
}
}

int result = K[n][W];

/* Free memory */
for (i = 0; i <= n; i++)
free(K[i]);
free(K);

return result;

int main() { int n, W;

printf("--- 0/1 Knapsack (Dynamic Programming) ---\n");

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

int val[n], wt[n];

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

printf("Enter value and weight for item %d: ", i + 1);
scanf("%d %d", &val[i], &wt[i]);
}

printf("Enter capacity of knapsack: ");

scanf("%d", &W);

printf("Maximum value in Knapsack = %d\n", knapSack(W, wt, val, n));

return 0;
}

4. Complexity Analysis

• Time Complexity: $O(n \times W)$, where $n$ is the number of items and $W$ is the
capacity of the knapsack.
• Space Complexity: $O(n \times W)$ to maintain the 2D table. (Note: This can be
optimized to $O(W)$ using a 1D array).

5. Output

6. Conclusion

Dynamic Programming ensures that we find the global maximum for the 0/1 Knapsack problem
by considering the trade-offs between including and excluding each item. This approach is highly
effective for problems with small to moderate capacities, though it belongs to the class of pseudo-
polynomial time algorithms.
Lab 21: N-Queens Problem - Backtracking
Objective: To implement the N-Queens problem using the Backtracking approach to place $N$
queens on an $N \times N$ chessboard such that no two queens attack each other.

1. Theory

The N-Queens problem is a classic puzzle that involves placing $N$ chess queens on an $N
\times N$ chessboard so that no two queens threaten each other. This means:

• No two queens can be in the same row.

• No two queens can be in the same column.
• No two queens can be on the same diagonal.

This problem is solved using Backtracking, a refined brute-force approach. The algorithm places
queens one by one in different columns, starting from the leftmost column. When placing a queen
in a column, we check for clashes with already placed queens. If we find a row with no clashes,
we mark this row and column as part of the solution. If we cannot find such a row in the current
column due to clashes, we backtrack and change the position of the queen in the previous
column.

2. Algorithm

1. Start in the leftmost column.

2. If all queens are placed (column index == $N$), return true.
3. Try all rows in the current column. For every row:
o Check if the queen can be placed safely at board[row][col].
o If safe:
▪ Mark board[row][col] = 1.
▪ Recursively try to place the rest of the queens in the next column.
▪ If placing the queen leads to a solution, return true.
▪If not, unmark board[row][col] = 0 (backtrack) and try the next row.
4. If all rows have been tried and nothing worked, return false to trigger backtracking in the
previous column.

3. Source Code (C++)

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

/* Function to print the chessboard */ void printSolution(int **board, int 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"); } }

/* Check if a queen can be placed at board[row][col] */ int isSafe(int **board, int row, int col, int N) { int
i, j;
/* Check this row on left side */
for (i = 0; i < col; i++)
if (board[row][i])
return 0;

/* Check upper diagonal on left side */

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

/* Check lower diagonal on left side */

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

return 1;

/* Recursive utility to solve N-Queens */ int solveNQUtil(int **board, int col, int N) { if (col >= N) return 1;

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

if (isSafe(board, i, col, N)) {
board[i][col] = 1;

if (solveNQUtil(board, col + 1, N))

return 1;

/* BACKTRACK */
board[i][col] = 0;
}
}

return 0;

int main() { int N;

printf("--- N-Queens Problem (Backtracking) ---\n");

printf("Enter the value of N: ");
scanf("%d", &N);

/* Dynamic allocation of board */

int **board = (int **)malloc(N * sizeof(int *));
for (int i = 0; i < N; i++) {
board[i] = (int *)calloc(N, sizeof(int));
}

if (!solveNQUtil(board, 0, N)) {
printf("Solution does not exist\n");
} else {
printSolution(board, N);
}

/* Free memory */
for (int i = 0; i < N; i++) {
free(board[i]);
}
free(board);

return 0;

4. Complexity Analysis

• Time Complexity: $O(N!)$. In the worst case, the algorithm explores all permutations of
row placements, though the pruning (isSafe check) significantly reduces the actual
number of states visited.
• Space Complexity: $O(N^2)$ for the chessboard and $O(N)$ for the recursion stack.

5. Output

6. Conclusion

The N-Queens problem is an excellent demonstration of how backtracking can find a valid
configuration among a large set of possibilities. By systematically exploring and discarding paths
that lead to invalid states, we find solutions much faster than a standard brute-force search.
Lab 22: Graph Coloring Problem - Backtracking
Objective: To implement the Graph Coloring problem using Backtracking to determine if the
vertices of a graph can be colored with at most $m$ colors such that no two adjacent vertices
share the same color.

1. Theory

The Graph Coloring problem (specifically the $m$-Coloring problem) involves assigning
colors to each vertex of a graph. The fundamental constraint is that no two adjacent vertices
(vertices connected by an edge) can have the same color.

This is a classic optimization and constraint satisfaction problem used in:

• Scheduling: Avoiding conflicts in exam timetables or task assignments.

• Register Allocation: In compiler optimization to assign variables to a limited number of
CPU registers.
• Map Coloring: Ensuring adjacent regions on a map have different colors.

2. Algorithm

The backtracking approach attempts to assign colors one by one to different vertices, starting
from vertex 0.

1. Check Safety: Before assigning a color to a vertex, check if any adjacent vertex already
has that color.
2. Recursive Step:
o Assign a color to the current vertex.

o Recursively move to the next vertex.

o If the assignment leads to a solution (all vertices colored), return true.
3. Backtrack: If no color can be assigned to the current vertex that leads to a solution,
remove the assigned color (reset to 0) and return false to the previous recursive call.

3. Source Code (C++)

#include <stdio.h>

#define V 4

/* Function to print the color assignment */ void printSolution(int color[]) { printf("Assigned Colors for
vertices:\n");

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

printf("Vertex %d ---> Color %d\n", i, color[i]);
}

/* Check if assigning color c to vertex v is safe */ int isSafe(int v, int graph[V][V], int color[], int c) { for (int
i = 0; i < V; i++) { if (graph[v][i] && color[i] == c) return 0; } return 1; }

/* Recursive utility for graph coloring / int graphColoringUtil(int graph[V][V], int m, int color[], int v) { / If
all vertices are assigned a color */ if (v == V) return 1;

/* Try all colors */

for (int c = 1; c <= m; c++) {
if (isSafe(v, graph, color, c)) {
color[v] = c;

if (graphColoringUtil(graph, m, color, v + 1))

return 1;

/* Backtrack */
color[v] = 0;
}
}

return 0;

/* Main driver function */ int graphColoring(int graph[V][V], int m) { int color[V] = {0};

if (!graphColoringUtil(graph, m, color, 0)) {

printf("Solution does not exist with %d colors.\n", m);
return 0;
}

printSolution(color);
return 1;

int main() { /* Graph: (3)---(2) | / | | / | (0)---(1) */ int graph[V][V] = { {0, 1, 1, 1}, {1, 0, 1, 0}, {1, 1, 0, 1},
{1, 0, 1, 0} };

int m = 3;

printf("--- Graph Coloring (Backtracking) ---\n");

graphColoring(graph, m);

return 0;

4. Complexity Analysis

• Time Complexity: $O(m^V)$. In the worst case, for every vertex, we try $m$ colors.
• Space Complexity: $O(V)$ for the recursion stack and the array used to store assigned
colors.

5. Output
Plaintext

6. Conclusion

Graph coloring demonstrates the utility of backtracking in solving constraint-based problems.

While the time complexity is exponential, it is a practical approach for many real-world
scheduling and allocation tasks where the graph size is manageable. For larger graphs, heuristic-
based greedy algorithms are often used to find "good enough" colorings.
Lab 23: Hamiltonian Cycle - Backtracking
Objective: To implement the Hamiltonian Cycle algorithm using Backtracking to find a path in
an undirected graph that visits every vertex exactly once and returns to the starting vertex.

1. Theory

A Hamiltonian Cycle (or Hamiltonian Circuit) is a closed loop in a graph where every node is
visited exactly once. Finding such a cycle is a classic problem in graph theory and is related to
the Traveling Salesperson Problem.

Unlike the Eulerian circuit (which visits every edge), the Hamiltonian cycle focuses on vertices.
This problem is NP-complete, meaning there is no known efficient way to find a solution for all
graphs, making Backtracking a suitable approach for finding solutions in smaller graphs by
systematically searching and pruning invalid paths.

2. Algorithm

1. Create an empty path array and add vertex 0 as the starting point.
2. For every remaining vertex (from 1 to $V-1$):
o Check Safety: Verify if the vertex is adjacent to the previously added vertex and
has not been visited yet.
o If safe, add the vertex to the path and recursively attempt to build the rest of the
path.
o If adding the vertex leads to a solution (all vertices visited once and the last vertex
connects back to vertex 0), return true.
3. Backtrack: If the vertex does not lead to a solution, remove it from the path and try the
next available vertex.
4. If no vertex can be added, return false.

3. Source Code (C++)

#include <stdio.h>

#define V 5

/* Function to print the Hamiltonian Cycle */ void printSolution(int path[]) { printf("Hamiltonian Cycle
exists: ");

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

printf("%d -> ", path[i]);
}

printf("%d\n", path[0]);
}

/* Check if vertex v can be added at position pos / int isSafe(int v, int graph[V][V], int path[], int pos) { /
Check if adjacent to previous vertex */ if (graph[path[pos - 1]][v] == 0) return 0;

/* Check if already included in path */

for (int i = 0; i < pos; i++) {
if (path[i] == v)
return 0;
}

return 1;

/* Recursive utility function / int hamCycleUtil(int graph[V][V], int path[], int pos) { if (pos == V) { / Check
edge from last to first */ return graph[path[pos - 1]][path[0]] == 1; }

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

if (isSafe(v, graph, path, pos)) {
path[pos] = v;

if (hamCycleUtil(graph, path, pos + 1))

return 1;

/* BACKTRACK */
path[pos] = -1;
}
}

return 0;

/* Main function */ int hamCycle(int graph[V][V]) { int path[V];

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

path[i] = -1;

path[0] = 0;

if (!hamCycleUtil(graph, path, 1)) {

printf("Solution does not exist\n");
return 0;
}
printSolution(path);
return 1;

int main() { int graph[V][V] = { {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} };

printf("--- Hamiltonian Cycle (Backtracking) ---\n");

hamCycle(graph);

return 0;

4. Complexity Analysis

• Time Complexity: $O(N!)$ in the worst case. The algorithm explores various
permutations of vertices, though adjacency constraints prune many branches.
• Space Complexity: $O(V)$ to store the path array and manage the recursion stack.

5. Output

6. Conclusion

The Hamiltonian Cycle problem highlights the power of backtracking in navigating complex
graph constraints. By ensuring each step adheres to both adjacency and uniqueness rules, the
algorithm effectively identifies cycles or concludes their absence, even when a brute-force search
would be unfeasible for larger structures.