Analysis and Design of Algorithms Lab File
Submitted By: [Your Name]
Roll Number: [Your Roll Number]
Class: [Your Class/Section]
Subject: Analysis and Design of Algorithms Lab
Submitted To: Prof. Kalicharan (GoG Professor)
Submission Date: 9th June 2025
Index Page
1. Iterative and Recursive Binary Search
2. Merge Sort
3. Quick Sort
4. Strassen's Matrix Multiplication
5. Optimal Merge Patterns
6. Huffman Coding
7. Minimum Spanning Tree using Kruskal's Algorithm
8. Minimum Spanning Tree using Prim's Algorithm
9. Single Source Shortest Path Algorithm (Dijkstra's)
10. Floyd-Warshall Algorithm
11. Traveling Salesman Problem
12. Hamiltonian Cycle Problem
Experiment 1: Iterative and Recursive Binary Search
Algorithm Explanation:
Binary Search is used to find the position of a target value within a sorted array.
C++ Code: [Already included in previous step]
Experiment 2: Merge Sort
Algorithm Explanation:
Merge Sort is a divide-and-conquer algorithm that divides the array into halves, sorts them, and
merges the sorted halves.
C++ Code:
void merge(int arr[], int l, int m, int r) { /* merge logic */ }
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);
}
Experiment 3: Quick Sort
Algorithm Explanation:
Quick Sort selects a pivot and partitions the array such that elements smaller than pivot go left,
larger go right.
C++ Code:
int partition(int arr[], int low, int high) { /* partition logic */ }
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);
}
Experiment 4: Strassen's Matrix Multiplication
Algorithm Explanation:
Uses divide-and-conquer to multiply two matrices in fewer operations than standard matrix
multiplication.
C++ Code:
void strassen(int A[2][2], int B[2][2], int C[2][2]) { /* logic */ }
Experiment 5: Optimal Merge Patterns
Algorithm Explanation:
Combines multiple sorted files into a single sorted file with minimum computation using a priority
queue.
C++ Code:
Use Min-Heap or Priority Queue to combine file sizes optimally.
Experiment 6: Huffman Coding
Algorithm Explanation:
Huffman Coding uses a greedy algorithm to build a prefix code based on frequencies of characters.
C++ Code:
Use priority_queue, struct Node { char data; int freq; ... }
Experiment 7: Minimum Spanning Tree using Kruskal's Algorithm
Algorithm Explanation:
Greedy algorithm that adds edges with the smallest weight, avoiding cycles using Union-Find.
C++ Code:
Sort edges, use union-find to avoid cycles, build MST.
Experiment 8: Minimum Spanning Tree using Prim's Algorithm
Algorithm Explanation:
Greedy algorithm that grows the MST one vertex at a time from a starting point.
C++ Code:
Use priority queue and visited array.
Experiment 9: Single Source Shortest Path (Dijkstra's Algorithm)
Algorithm Explanation:
Finds the shortest path from a source node to all other nodes in a weighted graph.
C++ Code:
Use min-priority queue and distance array.
Experiment 10: Floyd-Warshall Algorithm
Algorithm Explanation:
All-pairs shortest path algorithm using dynamic programming.
C++ Code:
Use 2D matrix dist[i][j] updated with min(dist[i][j], dist[i][k] + dist[k][j])
Experiment 11: Traveling Salesman Problem
Algorithm Explanation:
Finds the shortest possible route that visits each city once and returns to the origin city.
C++ Code:
Use recursion with bitmasking or dynamic programming.
Experiment 12: Hamiltonian Cycle Problem
Algorithm Explanation:
Determines whether a Hamiltonian Cycle exists in a graph.
C++ Code:
Use backtracking to try all possible paths.