Index:

1)Kruskal

2)Prims

3)Dijkstra

4)Floyd

5)Rabin Karp

6)Knuth Morris

7)Naïve String

8)Quick sort

9)Merge sort

10)Heap sort

11)Insertion sort

1)Kruskal algorithm

Kruskal’s Algorithm is a greedy algorithm used to find the Minimum Spanning Tree (MST) of a
connected, undirected, weighted graph. It ensures all vertices are connected with minimum total
edge weight and no cycles.

Pseudocode:

3. Explanation:
Kruskal's algorithm follows a greedy strategy, always choosing the smallest weight edge that does
not form a cycle.

It starts with each node in its own group (forest).

Edges are sorted by weight.

One by one, it picks the smallest edge.

If the edge connects two different groups (i.e., no cycle), it's added to the MST.

It uses the Disjoint Set (Union-Find) to check if two vertices are already connected.

This continues until the MST has V - 1 edges (where V = number of vertices).

4. Example
Graph:

Vertices: A, B, C, D
Edges:
A-B (1), B-C (4), A-C (3), C-D (2), B-D (5)
Step-by-step:

Sort edges: A-B(1), C-D(2), A-C(3), B-C(4), B-D(5)

Pick A-B(1) → no cycle → add to MST

Pick C-D(2) → no cycle → add to MST

Pick A-C(3) → A and C in different trees → add to MST

Now we have 3 edges (V-1 = 4-1 = 3) → Done!

✅ MST = A-B, C-D, A-C

Total weight = 1 + 2 + 3 = 6

2)Prims algorithm:

1. Problem Statement

Prim's Algorithm is a greedy algorithm used to find the Minimum Spanning Tree (MST) of a
connected, undirected, weighted graph. It starts with a single vertex and grows the MST by adding
the minimum weight edge that connects a vertex inside the tree to a vertex outside.

2. Pseudocode

PRIM(G, start):
1. Initialize MST = {}, visited[] = false for all vertices
2. Use a min-heap (priority queue) to store edges with weights
3. Insert all edges from the starting vertex into the heap
4. While heap is not empty and MST has < V-1 edges:
a. Extract minimum edge (u, v) from heap
b. If v is not visited:
i. Add (u, v) to MST
ii. Mark v as visited
 iii. Insert all edges from v to heap (if the other end is not visited)
5. Return MST

3. Explanation
Start from any vertex (say, A).

Maintain a set of visited nodes (initially empty).

Always pick the lowest-weight edge from the current MST that connects to an unvisited vertex.

Keep growing the MST until all vertices are connected (the MST will have V-1 edges).

It ensures there are no cycles, and all nodes are reached with the minimum total weight.

This algorithm works better with an adjacency matrix or priority queues for efficient edge selection.

4. Example
Graph:

Vertices: A, B, C, D
Edges:
A-B (1), A-C (3), B-C (4), B-D (2), C-D (5)
Start at A:

A → B (1), A → C (3) → pick A-B (1)

MST: A-B

From B: B-C (4), B-D (2) → pick B-D (2)

MST: A-B, B-D

From D: D-C (5), A-C (3) → pick A-C (3)

MST: A-B, B-D, A-C

✅ MST edges: A-B, B-D, A-C

Total weight = 1 + 2 + 3 = 6

⏱ Time Complexity:
Depends on how the graph is represented:

Representation Time Complexity

Adjacency Matrix O(V²)
Adjacency List + Min-Heap O(E log V)
3)Dijkstra algorithm:

1. Problem Statement
Dijkstra’s algorithm is used to find the shortest paths from a single source vertex to all other vertices
in a graph with non-negative edge weights. It follows a greedy approach and ensures the shortest
distance to each node is found step by step.

2. Pseudocode:
DIJKSTRA(G, source):
1. Set distance[] = ∞ for all vertices
2. distance[source] = 0
3. Create a min-priority queue and insert (source, 0)
4. While the queue is not empty:
a. u = vertex with smallest distance
b. For each neighbor v of u:
i. if distance[u] + weight(u, v) < distance[v]:
- distance[v] = distance[u] + weight(u, v)
- Insert (v, distance[v]) into the queue
5. Return distance[]

3. Explanation
Dijkstra starts by setting the distance of all nodes to ∞, except the source node (set to 0).

It uses a priority queue (min-heap) to always choose the closest unvisited node.

From that node, it relaxes the distances to its neighbors (i.e., checks if there’s a shorter path to reach
them).

This process continues until all nodes have been visited, ensuring we always pick the current
shortest known path.

🔒 Works only with non-negative weights.

4. Example
Graph:

Vertices: A, B, C, D
Edges:
A-B (1), A-C (4), B-C (2), B-D (6), C-D (3)
Start from A:

Step Node Update Distances

Init A A=0, B=∞, C=∞, D=∞
1 A A=0, B=1, C=4
2 B A=0, B=1, C=3 (via B), D=7 (via B)
3 C A=0, B=1, C=3, D=6 (via C)
4 D Final distances: A=0, B=1, C=3, D=6
✅ Shortest distances from A:
A→A=0

A→B=1

A→C=3

A→D=6

⏱ Time Complexity:
Data Structure Used Time Complexity
Array (simple version) O(V²)
Min-Heap (Binary Heap)O((V + E) log V)
Fibonacci Heap (advanced) O(E + V log V)

4)Floyd warshall algorithm:

1. Problem Statement
Floyd-Warshall is a dynamic programming algorithm used to find the shortest distances between
every pair of vertices in a weighted graph. It works for both directed and undirected graphs, and
supports negative edge weights (but not negative cycles).
2. Pseudocode
FLOYD-WARSHALL(dist[][]):
1. Let dist[i][j] be the initial weight of edge (i, j)
- If there is no edge, set dist[i][j] = ∞
- Set dist[i][i] = 0 for all i

2. for k = 1 to n:
for i = 1 to n:
for j = 1 to n:
if dist[i][j] > dist[i][k] + dist[k][j]:
dist[i][j] = dist[i][k] + dist[k][j]

3. Return dist[][]

3. Explanation
We use a distance matrix dist[i][j] that stores the current shortest distance from vertex i to vertex j.

The core idea: for each pair (i, j), check if going through a third vertex k gives a shorter path.

Repeat this for every possible k (1 to n).

After n iterations, all shortest paths are found.

This approach is simple to implement and works well for dense graphs.

4. Example
Graph (4 vertices):
Adjacency Matrix (initial dist[][]):

A B C D
A [ 0, 3, INF, 7 ]
B [ 8, 0, 2, INF ]
C [ 5, INF, 0, 1 ]
D [ 2, INF, INF, 0 ]
After running Floyd-Warshall:

A B C D
A [ 0, 3, 5, 6 ]
B [ 7, 0, 2, 3 ]
C [ 5, 8, 0, 1 ]
D [ 2, 5, 7, 0 ]
✅ This final matrix gives shortest distances between every pair of vertices.

⏱ Time Complexity:
Operation Complexity
Triple nested loop O(V³)
✅ Works best for small/medium graphs where V is not too large.

5)Rabin Karp
1. Problem Statement
Rabin-Karp is a string matching algorithm used to find occurrences of a pattern in a text. It uses
hashing to compare the pattern with substrings of the text, making the matching process faster in
many cases.

It is especially efficient when searching for multiple patterns in a text.

2. Pseudocode
RABIN-KARP(text, pattern, d, q):
Input:
- text[0...n-1], pattern[0...m-1]
- d = number of characters in input alphabet (e.g. 256 for ASCII)
- q = a large prime number for modulo operation

1. Compute hash value of pattern (p) and first window of text (t0)
2. For i = 0 to n - m:
a. If p == ti:
- Check characters one by one
- If all match, report match at index i
b. If i < n - m:
- Calculate hash for next window using rolling hash:
ti+1 = (d*(ti - text[i]*h) + text[i+m]) mod q
where h = d^(m-1) mod q

3. Explanation
Step 1: Calculate a hash value for the pattern and for the first window of the text.

Step 2: Slide the window one character at a time:

If hash values match, verify the substring matches character-by-character.

Use a rolling hash to efficiently compute hash of next window from the previous one.

This avoids recalculating hash from scratch every time.

It reduces unnecessary comparisons and is especially fast when we expect fewer matches.

4. Example
Let’s say:

Text = "ABCCDDAEFG"

Pattern = "CDD"

Use d = 256, q = 101 (common prime for hashing)

Steps:

Calculate hash of "CDD"

Slide through the text:

Compare each substring of length 3

If hash matches → check character by character

✅ Output: Pattern found at position 3 (0-based index)

⏱ Time Complexity
Case Time
Best / Average O(n + m) (with good hash and few collisions)
Worst Case O(n * m) (if too many hash collisions)
Where:

n = length of text

m = length of pattern

6)Knuth morris algorithm:

1. Problem Statement
KMP (Knuth-Morris-Pratt) is a string matching algorithm used to efficiently search for a pattern in a
text. It avoids redundant comparisons by preprocessing the pattern to build an LPS (Longest Prefix
Suffix) array, which allows the algorithm to skip characters after a mismatch.

2. Pseudocode
KMP_SEARCH(text, pattern):
1. Compute LPS[] array for the pattern
2. Initialize i = 0 (text index), j = 0 (pattern index)
3. While i < n:
a. If text[i] == pattern[j]:
- i++, j++
- If j == m: Pattern found at (i - j), set j = LPS[j-1]
b. Else:
- If j != 0: set j = LPS[j - 1]
- Else: i++

BUILD_LPS(pattern):
1. Initialize LPS[0] = 0, len = 0
2. For i = 1 to m - 1:
a. If pattern[i] == pattern[len]:
- len++, LPS[i] = len, i++
b. Else:
- If len != 0: len = LPS[len - 1]
- Else: LPS[i] = 0, i++
3. Explanation
Step 1: Preprocess the pattern to create the LPS array:

LPS[i] tells us the length of the longest prefix which is also a suffix up to position i.

Step 2: Scan the text using the LPS array:

On a mismatch, instead of starting from the beginning of the pattern, jump to a smarter position
using LPS[j-1].

This saves time, especially when patterns have repetitive parts.

✅ No need to re-check characters you already matched!

4. Example
Text = "ABABDABACDABABCABAB"
Pattern = "ABABCABAB"

LPS[] for pattern:

Index (i) Pattern[i] LPS[i]
0 A 0
1 B 0
2 A 1
3 B 2
4 C 0
5 A 1
6 B 2
7 A 3
8 B 4
Now use the LPS to search in text.

✅ Pattern found at index 10!

⏱ Time Complexity
Step Time
Build LPS array O(m)
Pattern search O(n)
Total O(n + m)
Where:

n = length of text

m = length of pattern

✅ Very efficient even with long strings and repeated patterns.

7)Naive string matching:

1. Problem Statement
The Naive String Matching Algorithm is a straightforward approach to find all occurrences of a
pattern in a given text. It compares the pattern with all substrings of the text, one by one, and
checks for a match.

2. Pseudocode
NAIVE_STRING_MATCH(text, pattern):
1. n = length of text
2. m = length of pattern
3. for i = 0 to n - m:
a. for j = 0 to m - 1:
if text[i + j] != pattern[j]:
break
b. if j == m:
print("Pattern found at index", i)

3. Explanation
The algorithm slides the pattern over the text from left to right, one character at a time.

At each position i, it checks whether the substring text[i...i+m-1] matches the pattern.

If all characters match → pattern found

Otherwise → shift pattern by one and try again

✅ No preprocessing, no extra space — just basic comparisons.

4. Example
Text: "AABAACAADAABAABA"
Pattern: "AABA"

Steps:

Check index 0 → Match ✅

Check index 1 → Mismatch ❌

Check index 2 → Mismatch ❌

Check index 3 → Match ✅

✅ Output: Pattern found at indices 0, 9, and 12

⏱ Time Complexity
Case Time
Best Case O(n)
Worst Case O(n * m)
Where:

n = length of text

m = length of pattern

✅ Not efficient for large strings or repetitive patterns

⚠ Gets beaten by KMP, Rabin-Karp, or Boyer-Moore in most real cases.

8)Quick sort:

1. Problem Statement:
Quick Sort is a Divide and Conquer algorithm used to sort an array. It works by selecting a pivot
element, then partitioning the array such that:

Elements less than pivot go to the left

Elements greater than pivot go to the right

Then it recursively applies the same strategy to subarrays.

2. Pseudocode:
QUICKSORT(arr, low, high):
 if low < high:
1. pi = PARTITION(arr, low, high)
2. QUICKSORT(arr, low, pi - 1)
3. QUICKSORT(arr, pi + 1, high)

PARTITION(arr, low, high):

1. pivot = arr[high]
2. i = low - 1
3. for j = low to high - 1:
if arr[j] < pivot:
i++
swap arr[i] and arr[j]
4. swap arr[i+1] and arr[high]
5. return i + 1

3. Explanation
Choose a pivot (commonly the last element).

Partition the array so that:

All elements < pivot go to the left

All elements > pivot go to the right

After partitioning, the pivot is in its correct sorted position

Recursively apply Quick Sort to the left and right subarrays.

This way, the array becomes sorted without using any extra space (in-place sort).

4. Example
Array: [10, 80, 30, 90, 40, 50, 70]

Pivot = 70

After partition: [10, 30, 40, 50, 70, 90, 80] → Pivot 70 is at correct place

Recursively sort [10, 30, 40, 50] and [90, 80]

Eventually, we get: [10, 30, 40, 50, 70, 80, 90] ✅

⏱ Time Complexity
Case Time
Best Case O(n log n)
Average O(n log n)
Worst Case O(n²) (when pivot is always smallest/largest)
Space Complexity = O(log n) (for recursion stack)
✅ In-place, no extra array needed
⚠ Can degrade to O(n²) without good pivot choice

9)Merge sort:

1. Problem Statement
Merge Sort is a Divide and Conquer sorting algorithm that divides the array into two halves, sorts
each half recursively, and then merges the two sorted halves to produce the final sorted array.

2. Pseudocode:
MERGE_SORT(arr, left, right):
if left < right:
1. mid = (left + right) / 2
2. MERGE_SORT(arr, left, mid)
3. MERGE_SORT(arr, mid+1, right)
4. MERGE(arr, left, mid, right)

MERGE(arr, left, mid, right):

1. Create two temporary arrays L[] and R[]
- L = arr[left...mid]
- R = arr[mid+1...right]
2. Compare elements from L and R, and copy the smaller one into the main array
3. Copy any remaining elements from L and R

3. Explanation
Divide the array into two halves.

Recursively sort both halves using MERGE_SORT.

Use the MERGE function to combine them into one sorted array.

Merging is done by comparing elements from both halves and inserting the smaller ones first.

✅ It is stable (maintains the original order of equal elements).

✅ Perfect when guaranteed performance is needed.

4. Example
Array: [38, 27, 43, 3, 9, 82, 10]

Step-by-step breakdown:

Divide:

[38, 27, 43, 3] and [9, 82, 10]

Further divide:

[38, 27] → [38], [27] → Merge to [27, 38]

[43, 3] → [3, 43]

So [38, 27, 43, 3] → [3, 27, 38, 43]

[9, 82, 10] → [9], [82, 10] → [10, 82] → Final → [9, 10, 82]

Final merge:

[3, 27, 38, 43] and [9, 10, 82] → [3, 9, 10, 27, 38, 43, 82]

✅ Sorted result!

⏱ Time Complexity
Case Time
Best Case O(n log n)
Average O(n log n)
Worst Case O(n log n)
Space Complexity = O(n) (extra space for temporary arrays)

✅ Stable
✅ Good for linked lists and external sorting
⚠ Uses more memory than Quick Sort

10)Heap sort:

1. Problem Statement
Heap Sort is a comparison-based sorting algorithm that uses a binary heap (usually a max-heap) to
sort elements.
It works by:

Building a max-heap from the input array.

Repeatedly removing the largest element (root of the heap) and placing it at the end of the array.

Re-heapifying the remaining heap until it’s sorted.

HEAPSORT(arr, n):
1. BUILD_MAX_HEAP(arr, n)
2. for i = n-1 down to 1:
swap arr[0] and arr[i]
HEAPIFY(arr, 0, i)

BUILD_MAX_HEAP(arr, n):
for i = n/2 - 1 down to 0:
HEAPIFY(arr, i, n)

HEAPIFY(arr, i, n):
 largest = i
left = 2*i + 1
right = 2*i + 2

if left < n and arr[left] > arr[largest]:

largest = left

if right < n and arr[right] > arr[largest]:

largest = right

if largest != i:
swap arr[i] and arr[largest]
HEAPIFY(arr, largest, n)

3. Explanation
A heap is a complete binary tree with a specific ordering (max-heap: parent ≥ children).

Step 1: Build a max-heap from the input array.

Step 2: Swap the root (maximum value) with the last element, shrink the heap, and heapify again to
restore the max-heap.

Repeat until the heap is reduced to size 1.

Since max element is always at the top, the array gets sorted from end to start.

✅ It’s in-place (no extra arrays), but not stable.

4. Example
Array: [4, 10, 3, 5, 1]

Step 1: Build Max Heap

Transforms into: [10, 5, 3, 4, 1]

Step 2: Sort Process

Swap 10 with 1 → [1, 5, 3, 4, 10]

Heapify → [5, 4, 3, 1, 10]

Swap 5 with 1 → [1, 4, 3, 5, 10]

Heapify → [4, 1, 3, 5, 10]

Swap 4 with 3 → [3, 1, 4, 5, 10]

Heapify → [3, 1, 4, 5, 10] → finally sorted: [1, 3, 4, 5, 10] ✅

⏱ Time & Space Complexity

Operation Time
Build Heap O(n)
Heapify (per node) O(log n)
Total Sorting O(n log n)
Space Complexity: O(1) (in-place sorting)
✅ Efficient, in-place
⚠ Not stable (relative order of equal elements may change)

11)Insertion sort:

1. Problem Statement
Insertion Sort is a simple comparison-based sorting algorithm that builds the final sorted array one
element at a time by inserting elements into their correct position in the sorted portion of the array.

2. Pseudocode:
INSERTION_SORT(arr, n):
for i = 1 to n-1:
key = arr[i]
j=i-1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j=j-1
arr[j + 1] = key

3. Explanation
Start from the second element (index 1), treat the first element as a sorted part.

For each element, compare it backward with the sorted part and insert it in the correct place.

Elements are shifted one by one to make space for insertion.

✅ Great for small or nearly sorted arrays

✅ Works in-place and is stable

4. Example
Array: [5, 3, 4, 1, 2]

Step-by-step:

i=1 → key = 3 → insert before 5 → [3, 5, 4, 1, 2]

i=2 → key = 4 → insert before 5 → [3, 4, 5, 1, 2]

i=3 → key = 1 → insert before all → [1, 3, 4, 5, 2]

i=4 → key = 2 → insert after 1 → [1, 2, 3, 4, 5] ✅ Sorted!

⏱ Time & Space Complexity

Case Time
Best Case O(n) (Already sorted)
Average Case O(n²)
Worst Case O(n²) (Reverse order)
Space Complexity: O(1) (in-place)

✅ Stable
✅ Simple
✅ Good for small arrays or online sorting (real-time insertion)
⚠ Not good for large datasets due to quadratic time