Algorithm Lab Experiments: Sorting, Searching, Greedy, DP and String Matching

Posted on Oct 27, 2026 in Computer Engineering

Experiment 1: Insertion Sort

Aim: To implement Insertion Sort.

Theory: Insertion sort builds the sorted array one element at a time, like arranging playing cards in your hand. Each element (key) is inserted into its correct place in the already sorted left part by shifting larger elements right. It is stable, in-place and works best on small or nearly sorted data.

Algorithm:

1. Start.
2. Read n and the array A.
3. For i = 2 to n, set key = A[i] and j = i - 1.
4. While j ≥ 1 and A[j] > key, shift A[j] to A[j+1] and decrease j.
5. Put the key at A[j+1].
6. Display the sorted array.
7. Stop.

Time Complexity: Best O(n), Average O(n²), Worst O(n²). Space O(1).

Conclusion: Insertion sort was implemented successfully. It is simple and efficient for small or nearly sorted data but slow for large inputs.

Experiment 2: Merge Sort

Aim: To implement Merge Sort.

Theory: Merge sort uses the Divide and Conquer strategy. The array is divided into two halves, each half is sorted recursively, and then the two sorted halves are merged into one. It is stable and always takes O(n log n) time, but needs extra space for merging.

Algorithm:

1. Start.
2. Read n and the array A.
3. If the array has one element or none, it is already sorted, so return.
4. Find the middle: mid = (low + high) / 2.
5. Recursively sort the left half A[low..mid].
6. Recursively sort the right half A[mid+1..high].
7. Merge the two halves: compare the front elements of both, copy the smaller one into a temporary array, and repeat. Then copy any remaining elements.
8. Copy the temporary array back to A and display it.
9. Stop.

Time Complexity: Best, Average and Worst all O(n log n). Space O(n).

Conclusion: Merge sort was implemented successfully. It gives guaranteed O(n log n) performance, which makes it suitable for large data sets.

Experiment 3: Binary Search

Aim: To implement Binary Search.

Theory: Binary search finds an element in a sorted array. It compares the key with the middle element. If they are equal, the search ends. If the key is smaller, it searches the left half, otherwise the right half. The search space halves at every step.

Algorithm:

1. Start.
2. Read the sorted array A and the key to search.
3. Set low = 0 and high = n - 1.
4. Repeat while low ≤ high:
   • Find mid = (low + high) / 2.
   • If A[mid] = key, print the position and stop.
   • If key < A[mid], set high = mid - 1.
   • Otherwise, set low = mid + 1.
5. If the loop ends, print “Element not found”.
6. Stop.

Time Complexity: Best O(1), Average O(log n), Worst O(log n). Space O(1) (iterative).

Conclusion: Binary search was implemented successfully. It is much faster than linear search but needs the array to be sorted.

Experiment 4: Dijkstra’s Algorithm

Aim: To implement the Single Source Shortest Path problem using the Greedy strategy (Dijkstra’s algorithm).

Theory: Dijkstra’s algorithm finds the shortest path from one source vertex to all other vertices in a weighted graph with non-negative edge weights. It is greedy: at each step it picks the unvisited vertex with the smallest known distance, then relaxes (updates) the distances of its neighbours.

Algorithm:

1. Start.
2. Read the graph and the source vertex s.
3. Set dist[s] = 0 and dist[v] = ∞ for all other vertices. Mark all vertices unvisited.
4. Pick the unvisited vertex u with the minimum dist, and mark it visited.
5. For each neighbour v of u: if dist[u] + w(u,v) < dist[v], update dist[v] = dist[u] + w(u,v).
6. Repeat Steps 4 and 5 until all vertices are visited.
7. Display the shortest distances.
8. Stop.

Time Complexity (n = number of vertices, using an adjacency matrix):

• Best case: O(n²)
• Average case: O(n²)
• Worst case: O(n²)
• Space: O(n)

Conclusion: Dijkstra’s algorithm was implemented successfully and the shortest paths from the source were found. It does not work with negative edge weights.

Experiment 5: Fractional Knapsack

Aim: To implement the Fractional Knapsack problem using the Greedy method.

Theory: Given items with weights and values and a knapsack of capacity W, we maximize the total value. Items can be broken into fractions. The greedy choice is to sort items by value/weight ratio in descending order and take them in that order. If an item does not fit, take the fraction that fills the remaining capacity.

Algorithm:

1. Start.
2. Read n, the weights, the values, and the capacity W.
3. Calculate the ratio value / weight for each item.
4. Sort the items in decreasing order of ratio.
5. Set total value = 0.
6. For each item in sorted order:
   • If its weight ≤ remaining capacity, take the whole item, add its value, and reduce the capacity.
   • Otherwise, take the fraction remaining capacity / weight, add that fraction of the value, and stop.
7. Display the total value.
8. Stop.

Time Complexity (n = number of items):

• Best case: O(n log n)
• Average case: O(n log n)
• Worst case: O(n log n)
• Space: O(1)

Conclusion: The fractional knapsack problem was solved successfully using the greedy method. Greedy gives the optimal answer here because items can be divided.

Experiment 6: Floyd’s Algorithm (All-Pairs Shortest Paths)

Aim: To implement the All-Pairs Shortest Path problem using Floyd’s algorithm (Dynamic Programming).

Theory: Floyd’s algorithm finds the shortest distance between every pair of vertices. It takes each vertex k as a possible intermediate vertex and updates D[i][j] if the path through k is shorter: D[i][j] = min(D[i][j], D[i][k] + D[k][j]). It works with negative edges but not negative cycles.

Algorithm:

1. Start.
2. Read the number of vertices n and the weight matrix D (∞ where there is no edge, 0 on the diagonal).
3. For k = 1 to n:
   • For i = 1 to n:
     • For j = 1 to n:
       • If D[i][k] + D[k][j] < D[i][j], set D[i][j] = D[i][k] + D[k][j].
4. Display the final matrix D.
5. Stop.

Time Complexity (n = number of vertices):

• Best case: O(n³)
• Average case: O(n³)
• Worst case: O(n³)
• Space: O(n²)

Conclusion: Floyd’s algorithm was implemented successfully and the shortest distances between all pairs of vertices were found using dynamic programming.

Experiment 7: Travelling Salesperson Problem

Aim: To implement the Travelling Salesperson Problem using Dynamic Programming.

Theory: A salesperson must visit every city exactly once and return to the start with minimum total cost. The DP approach stores the minimum cost of reaching city j after visiting a subset S of cities: C(S, j) = min over i in S of [C(S - {j}, i) + cost(i, j)]. Reusing subproblems makes it far better than brute force O(n!).

Algorithm:

1. Start.
2. Read n and the cost matrix.
3. Take city 1 as the start and set C({1}, 1) = 0.
4. For subset sizes 2 to n, for every subset S containing city 1 and every city j in S (j ≠ 1), find the minimum cost of reaching j by trying every other city i in S as the previous city.
5. Find the minimum of C(all cities, j) + cost(j, 1) over all j.
6. Display the minimum tour cost and the path.
7. Stop.

Time Complexity (n = number of cities):

• Best case: O(n² · 2ⁿ)
• Average case: O(n² · 2ⁿ)
• Worst case: O(n² · 2ⁿ)
• Space: O(n · 2ⁿ)

Conclusion: The Travelling Salesperson Problem was solved successfully using dynamic programming. It is faster than brute force but still exponential, so it is practical only for small n.

Experiment 8: N-Queens Problem

Aim: To implement the N-Queens problem using Backtracking.

Theory: The goal is to place n queens on an n × n chessboard so that no two queens attack each other, meaning no two share a row, column or diagonal. Backtracking places queens one row at a time. If a queen cannot be safely placed in a row, it goes back to the previous row and moves that queen to the next column.

Algorithm:

1. Start.
2. Read n and create an n × n board.
3. Start with row 0.
4. For each column in the current row, check if placing a queen is safe (no queen in the same column or either diagonal above).
5. If safe, place the queen and move to the next row.
6. If all n queens are placed, print the board as a solution.
7. If no column in the row is safe, remove the previous queen (backtrack) and try its next column.
8. Stop when all possibilities are tried.

Time Complexity (n = number of queens / board size):

• Best case: O(n) (a solution found without much backtracking)
• Average case: O(n!)
• Worst case: O(n!)
• Space: O(n) for the recursion stack (O(n²) if the full board is stored)

Conclusion: The N-Queens problem was solved successfully using backtracking. Backtracking rejects invalid placements early, so it is more efficient than trying every arrangement.

Experiment 9: Naive String Matching

Aim: To implement the Naive String Matching algorithm.

Theory: The naive algorithm finds all occurrences of a pattern P in a text T. It slides the pattern over the text one position at a time and compares characters left to right at each position. If all characters match, the position is reported. It needs no preprocessing but is slow.

Algorithm:

1. Start.
2. Read the text T and the pattern P. Find their lengths n and m.
3. For i = 0 to n - m:
   • Set j = 0.
   • While j < m and T[i + j] = P[j], increase j.
   • If j = m, print “Pattern found at index i”.
4. If no match was found, print “Pattern not found”.
5. Stop.

Time Complexity (n = length of the text, pattern length treated as comparable to n in the worst case):

• Best case: O(n)
• Average case: O(n)
• Worst case: O(n²)
• Space: O(1)

Conclusion: The naive string matching algorithm was implemented successfully. It is easy to understand but inefficient for long texts because it rechecks characters.

Experiment 10: Rabin-Karp Algorithm

Aim: To implement the Rabin-Karp string matching algorithm.

Theory: Rabin-Karp compares the hash value of the pattern with the hash of each window of the text instead of comparing characters directly. The next window’s hash is computed quickly from the previous one using a rolling hash. If the hashes match, the characters are compared to rule out a false match (spurious hit).

Algorithm:

1. Start.
2. Read the text T, pattern P, a base d and a prime q. Find their lengths n and m.
3. Calculate the hash of the pattern and of the first window of the text.
4. For i = 0 to n - m:
   • If the pattern hash equals the current window hash, compare the characters one by one. If all match, print “Pattern found at index i”.
   • Calculate the hash of the next window by removing the leading character and adding the next one.
5. If no match was found, print “Pattern not found”.
6. Stop.

Time Complexity (n = length of the text, pattern length treated as comparable to n in the worst case):

• Best case: O(n)
• Average case: O(n)
• Worst case: O(n²) (when many spurious hits occur)
• Space: O(1)

Conclusion: The Rabin-Karp algorithm was implemented successfully. Hashing makes it fast on average, and it is useful for searching multiple patterns.