M.Tech (Cyber Security)
- Syllabus
- Previous Year Question
- Study Material
- Divide: Split the array into two equal halves at the midpoint.
- Conquer: Recursively sort each half using the same merge sort.
- Base case: An array of 0 or 1 element is already sorted — return it.
- Merge: Compare elements from both halves and merge them in sorted order.
- Return the fully merged and sorted array.
- Choose pivot: Select the middle element as the pivot.
- Partition: Split array into three parts — elements less than pivot, equal, and greater.
- Conquer: Recursively apply quick sort to the left and right partitions.
- Combine: Concatenate sorted_left + pivot_elements + sorted_right.
- Base case: Array of length ≤ 1 is already sorted.
- Others
Bihar Engineering University · Patna
Advanced
Algorithm
Laboratory
Complete Python Programs — All 10 Experiments
Table of Contents
| P–01 |
Merge Sort
Divide and Conquer · Sort an array
|
O(n log n) |
| P–02 |
Quick Sort
Divide and Conquer · Sort a list
|
O(n log n) avg |
| P–03 |
Max and Min Element
Divide and Conquer · ~3n/2 comparisons
|
O(n) |
| P–04 |
Count Inversions
Modified Merge Sort · count (i,j) pairs
|
O(n log n) |
| P–05 |
Power of a Number
Fast Exponentiation · x^n efficiently
|
O(log n) |
| P–06 |
Knapsack Problem
Greedy Method · Fractional Knapsack
|
O(n log n) |
| P–07 |
Minimum Spanning Tree — Prim's
Greedy · Priority Queue · Start from any vertex
|
O(E log V) |
| P–08 |
Minimum Spanning Tree — Kruskal's
Greedy · Union-Find · Sort edges globally
|
O(E log E) |
| P–09 |
Rod Cutting Problem
Dynamic Programming · Maximum profit
|
O(n²) |
| P–10 |
Fast Fourier Transform
Cooley-Tukey D&C · Complex sequences
|
O(n log n) |
PROGRAM 01
Objective: Write a program to sort an array using Merge Sort algorithm based on the Divide and Conquer technique.
Algorithm Steps
Python Code merge_sort.py
def merge_sort(arr): """ Divide and Conquer — split array into halves recursively, then merge them back in sorted order. Time: O(n log n) | Space: O(n) """ if len(arr) <= 1: return arr mid = len(arr) // 2 left = merge_sort(arr[:mid]) # Recursively sort left half right = merge_sort(arr[mid:]) # Recursively sort right half return merge(left, right) def merge(left, right): """Merge two sorted arrays into one sorted array.""" result = [] i = j = 0 while i < len(left) and j < len(right): if left[i] <= right[j]: result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 result.extend(left[i:]) # Append remaining elements result.extend(right[j:]) return result # ── Test ──────────────────────────────────────────────────── arr = [38, 27, 43, 3, 9, 82, 10] print(f"Original Array : {arr}") sorted_arr = merge_sort(arr) print(f"Sorted Array : {sorted_arr}")
Output console
Original Array : [38, 27, 43, 3, 9, 82, 10]
Sorted Array : [3, 9, 10, 27, 38, 43, 82]
PROGRAM 02
Objective: Implement Quick Sort using Divide and Conquer to sort a list of numbers.
Algorithm Steps
Python Code quick_sort.py
def quick_sort(arr): """ Divide and Conquer — choose a pivot, partition array, then sort each partition recursively. Time: O(n log n) average | O(n²) worst case """ if len(arr) <= 1: return arr pivot = arr[len(arr) // 2] # Choose middle element as pivot left = [x for x in arr if x < pivot] # Elements less than pivot mid = [x for x in arr if x == pivot] # Elements equal to pivot right = [x for x in arr if x > pivot] # Elements greater than pivot return quick_sort(left) + mid + quick_sort(right) # ── Test ──────────────────────────────────────────────────── arr = [64, 34, 25, 12, 22, 11, 90] print(f"Original Array : {arr}") print(f"Sorted Array : {quick_sort(arr)}")
Output console
Original Array : [64, 34, 25, 12, 22, 11, 90]
Sorted Array : [11, 12, 22, 25, 34, 64, 90]
PROGRAM 03
Objective: Write a program using Divide and Conquer to find the maximum and minimum element in an array.
Python Code min_max.py
def find_min_max(arr, low, high): """ Returns (min, max) using Divide and Conquer. Uses only ~3n/2 comparisons vs 2n-2 for linear scan. """ # Base case: single element if low == high: return arr[low], arr[low] # Base case: two elements if high == low + 1: if arr[low] < arr[high]: return arr[low], arr[high] else: return arr[high], arr[low] # Recursive case: divide at midpoint mid = (low + high) // 2 left_min, left_max = find_min_max(arr, low, mid) right_min, right_max = find_min_max(arr, mid + 1, high) return min(left_min, right_min), max(left_max, right_max) # ── Test ──────────────────────────────────────────────────── arr = [3, 1, 9, 7, 5, 2, 8, 4, 6] print(f"Array : {arr}") mn, mx = find_min_max(arr, 0, len(arr) - 1) print(f"Minimum : {mn}") print(f"Maximum : {mx}")
Output console
Array : [3, 1, 9, 7, 5, 2, 8, 4, 6]
Minimum : 1
Maximum : 9
PROGRAM 04
Objective: Write a program using Merge Sort technique to count number of inversions in an array. Example: Array = [2,4,1,3,5] → Inversions = (2,1), (4,1), (4,3) → Count = 3
Python Code count_inversions.py
def count_inversions(arr): """ Modified Merge Sort to count inversions. Inversion: pair (i,j) where i < j but arr[i] > arr[j]. """ if len(arr) <= 1: return arr, 0 mid = len(arr) // 2 left, left_inv = count_inversions(arr[:mid]) right, right_inv = count_inversions(arr[mid:]) merged, split_inv = merge_and_count(left, right) return merged, left_inv + right_inv + split_inv def merge_and_count(left, right): """Merge sorted arrays and count split inversions.""" result, inversions = [], 0 i = j = 0 while i < len(left) and j < len(right): if left[i] <= right[j]: result.append(left[i]); i += 1 else: result.append(right[j]) inversions += (len(left) - i) # All remaining lefts > right[j] j += 1 result.extend(left[i:]); result.extend(right[j:]) return result, inversions # ── Test ──────────────────────────────────────────────────── arr = [2, 4, 1, 3, 5] print(f"Array : {arr}") sorted_arr, count = count_inversions(arr) print(f"Number of Inversions: {count}") print(f"Inversion Pairs : (2,1), (4,1), (4,3)")
Output console
Array : [2, 4, 1, 3, 5]
Number of Inversions: 3
Inversion Pairs : (2,1), (4,1), (4,3)
PROGRAM 05
Objective: Write a program using Divide and Conquer to compute xⁿ efficiently. Example: 2⁸ = 256
Python Code fast_power.py
def power(x, n): """ Fast exponentiation by squaring (Divide and Conquer). x^n = (x^(n/2))² if n is even x^n = x · (x^(n/2))² if n is odd Time: O(log n) vs O(n) for naive multiplication """ if n == 0: return 1 if n < 0: return 1 / power(x, -n) # Handle negatives half = power(x, n // 2) # Recursive call with n/2 if n % 2 == 0: return half * half # Even: just square the result else: return x * half * half # Odd: multiply by x once more # ── Test ──────────────────────────────────────────────────── print(f"2^8 = {power(2, 8)}") # Expected: 256 print(f"3^5 = {power(3, 5)}") # Expected: 243 print(f"2^10 = {power(2, 10)}") print("\nStep trace for 2^8:") print(" 2^8 → (2^4)² → ((2^2)²)² → (((2^1)²)²)²") print(" 2^1=2 → 2^2=4 → 2^4=16 → 2^8=256")
Output console
2^8 = 256
3^5 = 243
2^10 = 1024
Step trace for 2^8:
2^8 → (2^4)² → ((2^2)²)² → (((2^1)²)²)²
2^1=2 → 2^2=4 → 2^4=16 → 2^8=256
PROGRAM 06
Objective: Implement a solution for the Knapsack problem using the Greedy method (Fractional Knapsack — items can be split).
Python Code knapsack_greedy.py
def fractional_knapsack(capacity, weights, values): """ Greedy Fractional Knapsack. Strategy: sort by value/weight ratio, take best items first. Greedy gives OPTIMAL for fractional; use DP for 0/1. """ n = len(values) # Build (ratio, weight, value, item_no) tuples items = [(values[i] / weights[i], weights[i], values[i], i+1) for i in range(n)] items.sort(reverse=True, key=lambda x: x[0]) # Sort by ratio ↓ total_value = 0.0 rem = capacity selection = [] for ratio, w, v, item_no in items: if rem == 0: break if w <= rem: # Take full item total_value += v; rem -= w selection.append((item_no, w, v, "Full")) else: # Take fraction frac = rem / w total_value += v * frac; rem = 0 selection.append((item_no, w, v, f"Fraction: {frac:.2f}")) return total_value, selection # ── Test ──────────────────────────────────────────────────── weights = [2, 3, 5, 7, 1, 4, 1] values = [10, 5, 15, 7, 6, 18, 3] capacity = 15 max_val, selected = fractional_knapsack(capacity, weights, values) print(f"Maximum Value Obtained: {max_val:.2f}")
Output console
Item Weight Value Taken
----------------------------------------
5 1 6 Full
1 2 10 Full
6 4 18 Full
3 5 15 Full
7 1 3 Full
2 3 5 Fraction: 0.67
Maximum Value Obtained: 55.33
PROGRAM 07
Objective: Write a program to find the Minimum Spanning Tree using Prim's Algorithm.
Python Code prims_mst.py
import heapq def prims_mst(graph, start=0): """ Prim's Algorithm — always pick the minimum-weight edge connecting the visited set to an unvisited vertex. Time: O(E log V) with priority queue. """ n = len(graph) visited = [False] * n min_heap = [(0, start, -1)] # (weight, vertex, parent) mst_edges = [] total_wt = 0 while min_heap: weight, u, parent = heapq.heappop(min_heap) if visited[u]: continue visited[u] = True; total_wt += weight if parent != -1: mst_edges.append((parent, u, weight)) for v, w in enumerate(graph[u]): if w > 0 and not visited[v]: heapq.heappush(min_heap, (w, v, u)) return mst_edges, total_wt # ── Test (Adjacency Matrix) ────────────────────────────────── graph = [ [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], ] V = ['A', 'B', 'C', 'D', 'E'] edges, total = prims_mst(graph, start=0) for u, v, w in edges: print(f" {V[u]} -- {V[v]} : {w}") print(f"Total MST Weight: {total}")
Output console
MST Edges (Prim's from vertex A):
A -- B : 2
B -- C : 3
B -- E : 5
A -- D : 6
Total MST Weight: 16
PROGRAM 08
Objective: Write a program to find the Minimum Spanning Tree using Kruskal's Algorithm.
Python Code kruskals_mst.py
class UnionFind: """Disjoint Set Union with path compression and union by rank.""" def __init__(self, n): self.parent = list(range(n)) self.rank = [0] * n def find(self, x): if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) # Path compression return self.parent[x] def union(self, x, y): rx, ry = self.find(x), self.find(y) if rx == ry: return False # Same set → cycle detected if self.rank[rx] < self.rank[ry]: rx, ry = ry, rx self.parent[ry] = rx if self.rank[rx] == self.rank[ry]: self.rank[rx] += 1 return True def kruskals_mst(edges, n): """ Kruskal's — sort all edges by weight, add each edge if it doesn't create a cycle. Stop when n-1 edges added. """ edges_sorted = sorted(edges, key=lambda x: x[2]) uf = UnionFind(n) mst, total = [], 0 for u, v, w in edges_sorted: if uf.union(u, v): mst.append((u, v, w)); total += w if len(mst) == n - 1: break return mst, total # ── Test ──────────────────────────────────────────────────── edges = [(0,1,2),(0,3,6),(1,2,3),(1,3,8), (1,4,5),(2,4,7),(3,4,9)] V = ['A','B','C','D','E'] mst, total = kruskals_mst(edges, len(V)) for u, v, w in mst: print(f" {V[u]} -- {V[v]} : {w}") print(f"Total MST Weight: {total}")
Output console
MST Edges (Kruskal's):
A -- B : 2
B -- C : 3
B -- E : 5
A -- D : 6
Total MST Weight: 16
PROGRAM 09
Objective: Write a program using Dynamic Programming to determine the maximum profit obtained by cutting a rod.
Python Code rod_cutting.py
def rod_cutting(prices, n): """ DP Bottom-up Rod Cutting. dp[i] = max revenue obtainable from rod of length i. For each length i, try all cuts j = 1 to i. """ dp = [0] * (n + 1) # dp[0] = 0 (zero length rod) cut = [0] * (n + 1) # cut[i] = first cut for optimal solution for i in range(1, n + 1): max_val = float('-inf') for j in range(1, i + 1): if j <= len(prices) and prices[j-1] + dp[i-j] > max_val: max_val = prices[j-1] + dp[i-j] cut[i] = j dp[i] = max_val # Traceback the cuts made cuts_made, length = [], n while length > 0: cuts_made.append(cut[length]); length -= cut[length] return dp[n], cuts_made # ── Test ──────────────────────────────────────────────────── prices = [1, 5, 8, 9, 10, 17, 17, 20] rod_length = 8 max_profit, cuts = rod_cutting(prices, rod_length) print(f"Optimal Cuts : {cuts}") print(f"Maximum Profit: {max_profit}")
Output console
Optimal Cuts : [2, 6]
Maximum Profit: 22
DP Table:
Length Max Profit
--------------------
1 1
2 5
3 8
4 10
5 13
6 17
7 18
8 22
PROGRAM 10
Objective: Write a program to compute the Fast Fourier Transform (FFT) of a sequence of complex numbers.
Python Code fft.py
import cmath def fft(x): """ Cooley-Tukey FFT (Divide and Conquer). Recursively splits DFT into even and odd indexed elements. X[k] = Σ x[n]·e^(-j2πkn/N) for k = 0 to N-1 Time: O(n log n) vs O(n²) for naive DFT. """ n = len(x) if n <= 1: return x # Pad to next power of 2 if necessary if n & (n - 1) != 0: next_p2 = 1 while next_p2 < n: next_p2 <<= 1 x = list(x) + [0] * (next_p2 - n); n = next_p2 # Divide: even and odd indexed elements even = fft([x[k] for k in range(0, n, 2)]) odd = fft([x[k] for k in range(1, n, 2)]) # Conquer: combine with twiddle factors T = [cmath.exp(-2j * cmath.pi * k / n) * odd[k] for k in range(n // 2)] return ([even[k] + T[k] for k in range(n // 2)] + [even[k] - T[k] for k in range(n // 2)]) # ── Test ──────────────────────────────────────────────────── signal = [1, 2, 3, 4, 5, 6, 7, 8] print(f"Input Signal: {signal}") result = fft(signal) print(f"\n{'k':<5} {'Real':>10} {'Imag':>12} {'|X[k]|':>10}") print("-" * 42) for k, val in enumerate(result): print(f" {k:3} {val.real:10.4f} {val.imag:+12.4f}j {abs(val):10.4f}")
Output console
Input Signal: [1, 2, 3, 4, 5, 6, 7, 8]
k Real Imag |X[k]|
------------------------------------------
0 36.0000 +0.0000j 36.0000
1 -4.0000 +9.6569j 10.4525
2 -4.0000 +4.0000j 5.6569
3 -4.0000 +1.6569j 4.3296
4 -4.0000 +0.0000j 4.0000
5 -4.0000 -1.6569j 4.3296
6 -4.0000 -4.0000j 5.6569
7 -4.0000 -9.6569j 10.4525
Time Complexity: O(n²) DFT = 64 ops vs O(n log n) FFT = 24 ops → 2.7x faster
Comments
Post a Comment