. Write a Program to implement linear search algorithm.

Linear Search checks each element of a list one by one until the desired element is found or the
list ends. Given an array, arr of n elements, and an element x, find whether element x is present
in the array. Return the index of the first occurrence of x in the array, or -1 if it doesn’t exist.
Examples:
Input: arr[] = [10, 50, 30, 70, 80, 20, 90, 40], x = 30
Output : 2

Explanation: For array [10, 50, 30, 70, 80, 20, 90, 40], the element to be searched is 30 and it is at index
2. So, the output is 2.

Using Iterative Approach

This takes an array arr and a target element to search. Iterates through each element of the array and compares
it with the target. If the target is found, it returns its index; otherwise, it returns -1.
def linear_search(arr, x):
for i in range(len(arr)):
if arr[i] == x:
return i
return -1
arr = [10, 23, 45, 70, 11, 15]
x = 70
res = linear_search(arr, x)
if res != -1:
print("Element found at index:", res)
else:
print("Element not found in the array")

The iterative method of binary search has a time complexity of O(logn n). This logarithmic performance occurs
because the algorithm repeatedly divides the search space in half during each iteration of the loop until the
target is found or the range is exhausted.
 1. Write a program to implement binary search algorithm.

Binary Search is an efficient searching algorithm used to find an element in a sorted array by repeatedly dividing
the search interval in half. It reduces the time complexity to O(log N), making it much faster than linear search.
Here is working of Binary Search
1. Find the middle element of the array.
2. Compare the middle element with the target key. If equal: return index.
3. If the key is smaller: search the left half.
4. If the key is larger: search the right half.
5. Repeat until the element is found or the search space is empty.

Iterative Binary Search

This version manually performs binary search using a while loop - efficient in both time and space.

Explanation:
 Using a while loop to implement iterative binary search .
  Initialize low and high pointers to define the search range.
 Calculates the middle index mid = low + (high - low) // 2.
 If arr[mid] is less than x, moves search to the right half.
 If arr[mid] is greater than x, moves search to the left half.
 If arr[mid] == x, returns the index.
 Returns -1 if the element is not found.

def binary_search(arr, x):

low = 0
high = len(arr) - 1
while low <= high:
mid = low + (high - low) // 2
if arr[mid] < x:
low = mid + 1
elif arr[mid] > x:
high = mid - 1
else:
return mid
return -1
arr = [2, 3, 4, 10, 40]
x = 10
result = binary_search(arr, x)
if result != -1:
print("Element is present at index", result)
else:
print("Element is not present in array")

2. Write a program to find the factorial of a number using recursive function

A factorial is positive integer n, and denoted by n!. Then the product of all positive integers less than or equal
to n.
n !=n∗(n−1)∗(n−2)∗(n−3)∗....∗1
For example:
calculate the factorial of a number using recursion.
Examples:
Input: 5
Output: 120

Input: 6
Output: 720
Implementation:
If fact(5) is called, it will call fact(4), fact(3), fact(2) and fact(1). So it means keeps calling itself by reducing value
by one till it reaches 1.

# Python 3 program to find

# factorial of given number
def factorial(n):
# Checking the number
# is 1 or 0 then
# return 1
# other wise return
# factorial
if (n==1 or n==0):
return 1
else:
return (n * factorial(n - 1))
# Driver Code
num = 5;
print("number : ",num)
print("Factorial : ",factorial(num))

Time complexity: O(n)

Space complexity: O(n)

3. Write a program to implement matrix multiplication

Given two matrices, the task is to multiply them together to form a new matrix. Each element in the result is
obtained by multiplying the corresponding elements of a row from the first matrix and a column from the
second matrix.
For Example:
Input: A = [[1, 2], [3, 4]], B = [[5, 6], [7, 8]]
Output: [[19, 22], [43, 50]]
Explanation: 1×5 + 2×7 = 19,
1×6 + 2×8 = 22,
3×5 + 4×7 = 43,
3×6 + 4×8 = 50

Using NumPy
NumPy handles matrix multiplication internally using optimized C-based operations. It takes the rows of matrix
A and the columns of matrix B, performs vectorized dot-products, and produces the result efficiently without
manual loops.

import numpy as np
A = [[12, 7, 3],
[4, 5, 6],
[7, 8, 9]]
B = [[5, 8, 1, 2],
[6, 7, 3, 0],
[4, 5, 9, 1]]
r = [Link](A, B)
for row in r:
print(row)

Output
[114 160 60 27]
[74 97 73 14]
[119 157 112 23]
Explanation: [Link](A, B) computes all row × column dot-products internally using vectorized, compiled code.

Using Nested Loops

This method uses the classic three-loop approach: the outer loop picks a row from A, the middle loop picks a
column from B, and the inner loop multiplies corresponding elements and adds them up. It directly follows the
mathematical definition of matrix multiplication.

A = [[12, 7, 3],
[4, 5, 6],
[7, 8, 9]]
B = [[5, 8, 1, 2],
[6, 7, 3, 0],
[4, 5, 9, 1]]
r = [[0]*len(B[0]) for _ in range(len(A))]
for i in range(len(A)):
for j in range(len(B[0])):
for k in range(len(B)):
r[i][j] += A[i][k] * B[k][j]
for row in r:
print(row)

Output
[114, 160, 60, 27]
[74, 97, 73, 14]
[89, 109, 106, 11]
Explanation:
 r = [[0]*len(B[0]) for _ in range(len(A))] initializes a result matrix with zeros.
  Triple loop: outer i -> selects row of A, middle j -> selects column index of B and inner k -> multiplies
A[i][k] * B[k][j] and accumulates into r[i][j].

4. Write a program to sort a given set of numbers using bubble sort algorithm
Bubble Sort is one of the simplest sorting algorithms. It repeatedly compares adjacent elements in the
list and swaps them if they are in the wrong order.
How Bubble Sort Works
1. Compare each pair of adjacent elements.
2. If the first element is greater than the second, swap them.
3. After each full pass, the largest unsorted element "bubbles up" to its correct position at the end.
4. Repeat this process for the remaining unsorted portion of the list.
5. The algorithm stops early if no swaps occur in a pass, meaning the array is already sorted.

Python Implementation
def bubbleSort(arr):
n = len(arr)
for i in range(n):
swapped = False
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
if not swapped:
break
arr = [64, 34, 25, 12, 22, 11, 90]
bubbleSort(arr)
print(arr)

Explanation:
 for i in range(n): Runs multiple passes; each pass positions the next largest element at the end.
 swapped = False: Flag to detect if any swap occurs in the current pass.
 for j in range(0, n - i - 1): Iterates through unsorted elements; range shrinks as the end becomes sorted.
 if arr[j] > arr[j + 1]: Checks for inversion between adjacent elements.
  arr[j], arr[j + 1] = arr[j + 1], arr[j]: Swaps elements in place using tuple unpacking.
 if not swapped: break, Stops early if no swaps occur, indicating the array is already sorted.

6. Write a program to sort a given set of numbers using Merge sort algorithm.

Merge Sort
The Merge Sort algorithm is a divide-and-conquer algorithm that sorts an array by first breaking it down into
smaller arrays, and then building the array back together the correct way so that it is sorted.
Divide: The algorithm starts with breaking up the array into smaller and smaller pieces until one such sub-array
only consists of one element.
Conquer: The algorithm merges the small pieces of the array back together by putting the lowest values first,
resulting in a sorted array.

The breaking down and building up of the array to sort the array is done recursively.
In the animation above, each time the bars are pushed down represents a recursive call, splitting the array into
smaller pieces. When the bars are lifted up, it means that two sub-arrays have been merged together.
The Merge Sort algorithm can be described like this:
How it works:
1. Divide the unsorted array into two sub-arrays, half the size of the original.
2. Continue to divide the sub-arrays as long as the current piece of the array has more than one element.
3. Merge two sub-arrays together by always putting the lowest value first.
4. Keep merging until there are no sub-arrays left.
Take a look at the drawing below to see how Merge Sort works from a different perspective. As you can see, the
array is split into smaller and smaller pieces until it is merged back together. And as the merging happens,
values from each sub-array are compared so that the lowest value comes first.

Manual Run Through

Let's try to do the sorting manually, just to get an even better understanding of how Merge Sort works before
actually implementing it in a Python program.
Step 1: We start with an unsorted array, and we know that it splits in half until the sub-arrays only consist of
one element. The Merge Sort function calls itself two times, once for each half of the array. That means that the
first sub-array will split into the smallest pieces first.
[ 12, 8, 9, 3, 11, 5, 4]
[ 12, 8, 9] [ 3, 11, 5, 4]
[ 12] [ 8, 9] [ 3, 11, 5, 4]
[ 12] [ 8] [ 9] [ 3, 11, 5, 4]

Step 2: The splitting of the first sub-array is finished, and now it is time to merge. 8 and 9 are the first two
elements to be merged. 8 is the lowest value, so that comes before 9 in the first merged sub-array.
[ 12] [ 8, 9] [ 3, 11, 5, 4]

Step 3: The next sub-arrays to be merged is [ 12] and [ 8, 9]. Values in both arrays are compared from the start.
8 is lower than 12, so 8 comes first, and 9 is also lower than 12.
[ 8, 9, 12] [ 3, 11, 5, 4]

Step 4: Now the second big sub-array is split recursively.

[ 8, 9, 12] [ 3, 11, 5, 4]
[ 8, 9, 12] [ 3, 11] [ 5, 4]
[ 8, 9, 12] [ 3] [ 11] [ 5, 4]

Step 5: 3 and 11 are merged back together in the same order as they are shown because 3 is lower than 11.
[ 8, 9, 12] [ 3, 11] [ 5, 4]

Step 6: Sub-array with values 5 and 4 is split, then merged so that 4 comes before 5.
[ 8, 9, 12] [ 3, 11] [ 5] [ 4]
[ 8, 9, 12] [ 3, 11] [ 4, 5]

Step 7: The two sub-arrays on the right are merged. Comparisons are done to create elements in the new
merged array:
1. 3 is lower than 4
2. 4 is lower than 11
3. 5 is lower than 11
4. 11 is the last remaining value
[ 8, 9, 12] [ 3, 4, 5, 11]

Step 8: The two last remaining sub-arrays are merged. Let's look at how the comparisons are done in more
detail to create the new merged and finished sorted array:
3 is lower than 8:
Before [ 8, 9, 12] [ 3, 4, 5, 11]
After: [ 3, 8, 9, 12] [ 4, 5, 11]

Step 9: 4 is lower than 8:

Before [ 3, 8, 9, 12] [ 4, 5, 11]
After: [ 3, 4, 8, 9, 12] [ 5, 11]

Step 10: 5 is lower than 8:

Before [ 3, 4, 8, 9, 12] [ 5, 11]
After: [ 3, 4, 5, 8, 9, 12] [ 11]

Step 11: 8 and 9 are lower than 11:

Before [ 3, 4, 5, 8, 9, 12] [ 11]
After: [ 3, 4, 5, 8, 9, 12] [ 11]

Step 12: 11 is lower than 12:

Before [ 3, 4, 5, 8, 9, 12] [ 11]
After: [ 3, 4, 5, 8, 9, 11, 12]
The sorting is finished!

----------------------------------or------------------------------------------------------------------------------------------------------------
Merge Sort is one of the most efficient and stable sorting algorithms based on the Divide and Conquer
technique. It divides an input array into two halves, recursively sorts them, and then merges the two sorted
halves using a function called merge().
The key function, merge(arr, l, m, r), assumes that both halves arr[l..m] (left half) and arr[m+1..r] (right half) are
already sorted and merges them into one sorted array.

How Merge Sort Works

Here’s the step-by-step breakdown:
1. Divide: Recursively split the array into two halves until each subarray has only one element.
2. Conquer: Sort each subarray individually (they’re already sorted if they contain one element).
3. Merge: Combine the sorted subarrays into a single sorted array in the correct order.
Illustration of Merge Sort:
Let’s sort the array or list [38, 27, 43, 10] using Merge Sort
Let’s look at the working of above example:
Divide:
 [38, 27, 43, 10] is divided into [38, 27 ] and [43, 10] .
 [38, 27] is divided into [38] and [27] .
 [43, 10] is divided into [43] and [10] .
Conquer:
 [38] is already sorted.
 [27] is already sorted.
 [43] is already sorted.
 [10] is already sorted.
Merge:
 Merge [38] and [27] to get [27, 38] .
 Merge [43] and [10] to get [10,43] .
 Merge [27, 38] and [10,43] to get the final sorted list [10, 27, 38, 43]
Therefore, the sorted list is [10, 27, 38, 43].

Python Implementation
def merge(arr, l, m, r):
n1 = m - l + 1
n2 = r - m
L = [0] * n1
R = [0] * n2

for i in range(n1):
L[i] = arr[l + i]
for j in range(n2):
R[j] = arr[m + 1 + j]
i=j=0
k=l
while i < n1 and j < n2:
if L[i] <= R[j]:
arr[k] = L[i]
i += 1
 else:
arr[k] = R[j]
j += 1
k += 1
while i < n1:
arr[k] = L[i]
i += 1
k += 1
while j < n2:
arr[k] = R[j]
j += 1
k += 1
def mergeSort(arr, l, r):
if l < r:
m = l + (r - l) // 2
mergeSort(arr, l, m)
mergeSort(arr, m + 1, r)
merge(arr, l, m, r)
arr = [12, 11, 13, 5, 6, 7]
print("Given array is:", arr)
mergeSort(arr, 0, len(arr) - 1)
print("Sorted array is:", arr)

Output
Given array is: [12, 11, 13, 5, 6, 7]
Sorted array is: [5, 6, 7, 11, 12, 13]
Explanation:
Divide:
 In mergeSort(arr, l, r), the condition if l < r: ensures the array is divided only when it has more than one
element.
 The midpoint is calculated as m = l + (r - l) // 2.
 The array is divided into two halves by recursive calls:
mergeSort(arr, l, m) → sorts the left half.
mergeSort(arr, m + 1, r) → sorts the right half.
Conquer:
 Each recursive call continues dividing until the subarrays have a single element (automatically sorted).
 Once divided, recursion starts returning — at each level, the two sorted halves are ready to be merged.
Merge:
 The merge(arr, l, m, r) function merges the two sorted halves.
 n1 = m - l + 1 and n2 = r - m calculate the sizes of the left and right subarrays.
 Temporary arrays L and R store these elements using loops.
 Variables i, j, and k are initialized for left array, right array, and merged array indices.
  The loop while i < n1 and j < n2: compares L[i] and R[j], placing the smaller into arr[k].
 After one list is exhausted, remaining elements from L or R are copied back into arr.
 This merging continues recursively until the full array becomes sorted.
Advantages of Merge Sort
 Efficient for large datasets.
 Guarantees O(n log n) performance.
 Stable sorting (preserves order of equal elements).
 Works well with linked lists.
Disadvantages
 Requires additional space (O(n)).
 Slower for small datasets compared to simpler algorithms like Insertion Sort.

7. Write a program to sort a given set of numbers using Insertion Sort algorithm.
Insertion sort is a simple sorting algorithm that works by iteratively inserting each element of an
unsorted list into its correct position in a sorted portion of the list. It is like sorting playing cards in your
hands. You split the cards into two groups: the sorted cards and the unsorted cards. Then, you pick a
card from the unsorted group and put it in the right place in the sorted group.

 Start with the second element as the first element is assumed to be sorted.
 Compare the second element with the first if the second is smaller then swap them.
 Move to the third element, compare it with the first two, and put it in its correct position
 Repeat until the entire array is sorted.
# Python program for implementation of Insertion Sort
# Function to sort array using insertion sort
def insertionSort(arr):
for i in range(1, len(arr)):
key = arr[i]
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 and key < arr[j]:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
# A utility function to print array of size n
def printArray(arr):
for i in range(len(arr)):
print(arr[i], end=" ")
print()
# Driver method
if __name__ == "__main__":
arr = [12, 11, 13, 5, 6]
insertionSort(arr)
printArray(arr)

Output
5 6 11 12 13
 arr = {23, 1, 10, 5, 2}
Initial:
 Current element is 23
 The first element in the array is assumed to be sorted.
 The sorted part until 0th index is : [23]
First Pass:
 Compare 1 with 23 (current element with the sorted part).
 Since 1 is smaller, insert 1 before 23 .
 The sorted part until 1st index is: [1, 23]
Second Pass:
 Compare 10 with 1 and 23 (current element with the sorted part).
 Since 10 is greater than 1 and smaller than 23 , insert 10 between 1 and 23 .
 The sorted part until 2nd index is: [1, 10, 23]
Third Pass:
 Compare 5 with 1 , 10 , and 23 (current element with the sorted part).
 Since 5 is greater than 1 and smaller than 10 , insert 5 between 1 and 10
 The sorted part until 3rd index is : [1, 5, 10, 23]
Fourth Pass:
 Compare 2 with 1, 5, 10 , and 23 (current element with the sorted part).
 Since 2 is greater than 1 and smaller than 5 insert 2 between 1 and 5 .
 The sorted part until 4th index is: [1, 2, 5, 10, 23]
Final Array:
 The sorted array is: [1, 2, 5, 10, 23]

Complexity Analysis of Insertion Sort

Time Complexity
 Best case: O(n), If the list is already sorted, where n is the number of elements in the list.
 Average case: O(n2), If the list is randomly ordered
 Worst case: O(n2), If the list is in reverse order
Space Complexity
 Auxiliary Space: O(1), Insertion sort requires O(1) additional space, making it a space-efficient sorting
algorithm.

Advantages and Disadvantages of Insertion Sort

Advantages
 Simple and easy to implement.
 Stable sorting algorithm.
 Efficient for small lists and nearly sorted lists.
 Space-efficient as it is an in-place algorithm.
 Adoptive. the number of inversions is directly proportional to number of swaps. For example, no
swapping happens for a sorted array and it takes O(n) time only.

Disadvantages
 Inefficient for large lists.
 Not as efficient as other sorting algorithms (e.g., merge sort, quick sort) for most cases.

Applications of Insertion Sort
Insertion sort is commonly used in situations where:
 The list is small or nearly sorted.
 Simplicity and stability are important.
 Used as a subroutine in Bucket Sort
 Can be useful when array is already almost sorted (very few inversions)
 Since Insertion sort is suitable for small sized arrays, it is used in Hybrid Sorting algorithms along with
other efficient algorithms like Quick Sort and Merge Sort. When the subarray size becomes small, we
switch to insertion sort in these recursive algorithms. For example IntroSort and TimSort use insertions
sort.

What are the Boundary Cases of the Insertion Sort algorithm?

Insertion sort takes the maximum time to sort if elements are sorted in reverse order. And it takes
minimum time (Order of n) when elements are already sorted.

What is the Algorithmic Paradigm of the Insertion Sort algorithm?

The Insertion Sort algorithm follows an incremental approach.

Is Insertion Sort an in-place sorting algorithm?

Yes, insertion sort is an in-place sorting algorithm.

Is Insertion Sort a stable algorithm?

Yes, insertion sort is a stable sorting algorithm.
 When is the Insertion Sort algorithm used?
Insertion sort is used when number of elements is small. It can also be useful when the input array is
almost sorted, and only a few elements are misplaced in a complete big array.

8. Write a program to sort a given set of numbers using Selection sort algorithm.

Selection Sort is one of the simplest comparison-based sorting algorithms. It sorts an array by repeatedly
finding the smallest (or largest) element from the unsorted portion and placing it in its correct position.
Working of Selection Sort
1. Start from the first element and find the smallest element in the entire array by iterating over it.
2. Swap this smallest element with the first element.
3. Now, move to the second element find the next smallest in the remaining unsorted portion and swap it
with the second position.
4. Repeat this process until the entire array becomes sorted.
Python Implementation
def selectionSort(array, size):
for ind in range(size):
min_index = ind
for j in range(ind + 1, size):
if array[j] < array[min_index]:
min_index = j
array[ind], array[min_index] = array[min_index], array[ind]
arr = [-2, 45, 0, 11, -9, 88, -97, -202, 747]
size = len(arr)
selectionSort(arr, size)
print(arr)

Output
[-202, -97, -9, -2, 0, 11, 45, 88, 747]

Explanation:
 for ind in range(size) (Outer loop): Iterates through each index, treating it as the start of the unsorted
portion.
 min_index = ind: Assumes the current index holds the smallest element.
 for j in range(ind + 1, size) (Inner loop): Finds the index of the minimum element in the unsorted part of
the array.
 if array[j] < array[min_index]: Updates min_index whenever a smaller element is found.
 Swap step: Exchanges the smallest found element with the first element of the unsorted section.

9. Write a program to find the minimum spanning tree of a given graph using Prim’s algorithm
Prim’s algorithm is a Greedy algorithm like Kruskal's algorithm. This algorithm always starts with a single
node and moves through several adjacent nodes, in order to explore all of the connected edges along
the way.
 The algorithm starts with an empty spanning tree.
 The idea is to maintain two sets of vertices. The first set contains the vertices already included in the
MST, and the other set contains the vertices not yet included.
 At every step, it considers all the edges that connect the two sets and picks the minimum weight edge
from these edges. After picking the edge, it moves the other endpoint of the edge to the set containing
MST.
Working of the Prim's Algorithm
1. Determine an arbitrary vertex as the starting vertex of the MST. We pick 0 in the above diagram.
2. Follow steps 3 to 5 till there are vertices that are not included in the MST (known as fringe vertex).
3. Find edges connecting any tree vertex with the fringe vertices.
4. Find the minimum among these edges.
5. Add the chosen edge to the MST. Since we consider only the edges that connect fringe vertices with the
rest, we never get a cycle.
6. Return the MST and exit

Simple Implementation for Adjacency Matrix Representation

Follow the given steps to utilize the Prim's Algorithm mentioned above for finding MST of a graph:
 Create a set mstSet that keeps track of vertices already included in MST.
 Assign a key value to all vertices in the input graph. Initialize all key values as INFINITE. Assign the key
value as 0 for the first vertex so that it is picked first.
 While mstSet doesn't include all vertices
=> Pick a vertex u that is not there in mstSet and has a minimum key value.
=> Include u in the mstSet.
=> Update the key value of all adjacent vertices of u. To update the key values, iterate through all
adjacent vertices. For every adjacent vertex v, if the weight of edge u-v is less than the previous key
value of v, update the key value as the weight of u-v.
The idea of using key values is to pick the minimum weight edge from the cut. The key values are used only for
vertices that are not yet included in MST, the key value for these vertices indicates the minimum weight edges
connecting them to the set of vertices included in MST.

import sys
def primMST(graph):
V = len(graph)
key = [[Link]] * V
parent = [-1] * V
mstSet = [False] * V
key[0] = 0
for _ in range(V):
# Find min key vertex
min_val = [Link]
u = -1
for v in range(V):
if key[v] < min_val and not mstSet[v]:
min_val = key[v]
u=v
mstSet[u] = True
# Update adjacent vertices
for v in range(V):
if 0 < graph[u][v] < key[v] and not mstSet[v]:
key[v] = graph[u][v]
parent[v] = u
print("Edge \tWeight")
for i in range(1, V):
print(f"{parent[i]} - {i} \t{graph[i][parent[i]]}")
# Example Usage
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]
]
primMST(graph)

Prim's algorithm is a greedy method used to find the Minimum Spanning Tree (MST) of a connected, weighted,
and undirected graph. It grows the MST one vertex at a time, starting from an arbitrary initial vertex, by adding
the cheapest possible edge connecting the growing tree to a vertex not yet in the tree.
Here is an example program implemented in Python using an adjacency matrix representation.
# Prim's Algorithm in Python
INF = 9999999
# number of vertices in graph
V=5
# create a 2d array of size 5x5
# for adjacency matrix to represent graph
G = [[0, 9, 75, 0, 0],
[9, 0, 95, 19, 42],
[75, 95, 0, 51, 66],
[0, 19, 51, 0, 31],
[0, 42, 66, 31, 0]]
# create a array to track selected vertex
# selected will become true otherwise false
selected = [0, 0, 0, 0, 0]
# set number of edge to 0
no_edge = 0
# the number of egde in minimum spanning tree will be
# always less than(V - 1), where V is number of vertices in
# graph
# choose 0th vertex and make it true
selected[0] = True
# print for edge and weight
print("Edge : Weight\n")
while (no_edge < V - 1):
# For every vertex in the set S, find the all adjacent vertices
#, calculate the distance from the vertex selected at step 1.
# if the vertex is already in the set S, discard it otherwise
# choose another vertex nearest to selected vertex at step 1.
minimum = INF
x=0
y=0
for i in range(V):
if selected[i]:
for j in range(V):
if ((not selected[j]) and G[i][j]):
# not in selected and there is an edge
if minimum > G[i][j]:
minimum = G[i][j]
x=i
y=j
print(str(x) + "-" + str(y) + ":" + str(G[x][y]))
selected[y] = True
 no_edge += 1

Output

Edge : Weight
0-1:9
1-3:19
3-4:31
3-2:51

Although adjacency matrix representation of graphs is used, this algorithm can also be implemented
using Adjacency List to improve its efficiency.

Prim's vs Kruskal's Algorithm

Kruskal's algorithm is another popular minimum spanning tree algorithm that uses a different logic to find the
MST of a graph. Instead of starting from a vertex, Kruskal's algorithm sorts all the edges from low weight to high
and keeps adding the lowest edges, ignoring those edges that create a cycle.

Prim's Algorithm Complexity

The time complexity of Prim's algorithm is O(V2).

Prim's Algorithm Application

 Laying cables of electrical wiring
 In network designed
 To make protocols in network cycles

Adjacency Matrix
An adjacency matrix is a way of representing a graph as a matrix of booleans (0's and 1's). A finite graph can be
represented in the form of a square matrix on a computer, where the boolean value of the matrix indicates if
there is a direct path between two vertices.
For example, we have a graph below.
An undirected graph

We can represent this graph [Link] matrix form like

Matrix representation of the graph
Each cell in the above table/matrix is represented as Aij, where i and j are vertices. The value of Aij is either 1 or
0 depending on whether there is an edge from vertex i to vertex j.

If there is a path from i to j, then the value of Aij is 1 otherwise its 0. For instance, there is a path from vertex 1
to vertex 2, so A12 is 1 and there is no path from vertex 1 to 3, so A13 is 0.
In case of undirected graphs, the matrix is symmetric about the diagonal because of every edge (i,j), there is
also an edge (j,i).

Pros of Adjacency Matrix

 The basic operations like adding an edge, removing an edge, and checking whether there is an edge
from vertex i to vertex j are extremely time efficient, constant time operations.
 If the graph is dense and the number of edges is large, an adjacency matrix should be the first choice.
Even if the graph and the adjacency matrix is sparse, we can represent it using data structures for sparse
matrices.
 The biggest advantage, however, comes from the use of matrices. The recent advances in hardware
enable us to perform even expensive matrix operations on the GPU.
 By performing operations on the adjacent matrix, we can get important insights into the nature of the
graph and the relationship between its vertices.

Cons of Adjacency Matrix

 The VxV space requirement of the adjacency matrix makes it a memory hog. Graphs out in the wild
usually don't have too many connections and this is the major reason why adjacency lists are the better
choice for most tasks.
 While basic operations are easy, operations like inEdges and outEdges are expensive when using the
adjacency matrix representation.

Adjacency List
An adjacency list represents a graph as an array of linked lists. The index of the array represents a vertex and
each element in its linked list represents the other vertices that form an edge with the vertex.
For example, we have a graph below.
 An undirected graph
We can represent this graph in the form of a linked list on a computer as shown below.

Linked list representation of the graph

Here, 0, 1, 2, 3 are the vertices and each of them forms a linked list with all of its adjacent vertices. For instance,
vertex 1 has two adjacent vertices 0 and 2. Therefore, 1 is linked with 0 and 2 in the figure above.

Pros of Adjacency List

 An adjacency list is efficient in terms of storage because we only need to store the values for the edges.
For a sparse graph with millions of vertices and edges, this can mean a lot of saved space.
 It also helps to find all the vertices adjacent to a vertex easily.

Cons of Adjacency List

 Finding the adjacent list is not quicker than the adjacency matrix because all the connected nodes must
be first explored to find them.

Adjacency List Structure

The simplest adjacency list needs a node data structure to store a vertex and a graph data structure to organize
the nodes.
We stay close to the basic definition of a graph - a collection of vertices and edges {V, E}. For simplicity, we use
an unlabeled graph as opposed to a labeled one i.e. the vertices are identified by their indices 0,1,2,3.

10. Write a program to find the minimum spanning tree of a given graph using Kruskal’s algorithm.

class Graph:
def __init__(self, vertices):
self.V = vertices
 [Link] = []
def add_edge(self, u, v, w):
[Link]([u, v, w])
def kruskal_mst(self):
def find(parent, i):
if parent[i] == i:
return i
return find(parent, parent[i])
def union(parent, rank, x, y):
x_root = find(parent, x)
y_root = find(parent, y)
if rank[x_root] < rank[y_root]:
parent[x_root] = y_root
elif rank[x_root] > rank[y_root]:
parent[y_root] = x_root
else:
parent[y_root] = x_root
rank[x_root] += 1
result = []
i=0
e=0
[Link] = sorted([Link], key=lambda item: item[2])
parent = [i for i in range(self.V)]
rank = [0] * self.V
while e < self.V - 1:
u, v, w = [Link][i]
i += 1
x = find(parent, u)
y = find(parent, v)
if x != y:
e += 1
[Link]([u, v, w])
union(parent, rank, x, y)
return result
# Example usage:
g = Graph(4)
g.add_edge(0, 1, 10)
g.add_edge(0, 2, 6)
g.add_edge(0, 3, 5)
g.add_edge(1, 3, 15)
g.add_edge(2, 3, 4)
mst = g.kruskal_mst()
 for u, v, weight in mst:
print(f"Edge: {u} - {v}, Weight: {weight}")

Output
Edge: 2 - 3, Weight: 4
Edge: 0 - 3, Weight: 5
Edge: 0 - 1, Weight: 10

In this example, we use Kruskal's algorithm to find the Minimum Spanning Tree of a graph represented
by an adjacency list. The algorithm starts with an empty MST and iteratively adds the smallest available
edges while ensuring that no cycles are formed.
Kruskal's algorithm is valuable for optimizing network design, cluster analysis, and various applications
involving connected graphs. It provides an efficient way to find the minimum spanning tree in a graph.

Kruskal's Algorithm
Kruskal's algorithm is a minimum spanning tree algorithm that takes a graph as input and finds the subset of
the edges of that graph which
 form a tree that includes every vertex
 has the minimum sum of weights among all the trees that can be formed from the graph

How Kruskal's algorithm works

It falls under a class of algorithms called greedy algorithms that find the local optimum in the hopes of
finding a global optimum.
We start from the edges with the lowest weight and keep adding edges until we reach our goal.
The steps for implementing Kruskal's algorithm are as follows:
1. Sort all the edges from low weight to high
2. Take the edge with the lowest weight and add it to the spanning tree. If adding the edge created a
cycle, then reject this edge.
3. Keep adding edges until we reach all vertices.

Example of Kruskal's algorithm

Start with a weighted graph

Choose the edge with the least weight, if there are more than 1, choose anyone

Choose the next shortest edge and add it

Choose the next shortest edge that doesn't create a cycle and add it

Choose the next shortest edge that doesn't create a cycle and add it

Repeat until you have a spanning tree

Kruskal's v/s Prim's Algorithm
Prim's algorithm is another popular minimum spanning tree algorithm that uses a different logic to find the
MST of a graph. Instead of starting from an edge, Prim's algorithm starts from a vertex and keeps adding
lowest-weight edges which aren't in the tree, until all vertices have been covered.

Kruskal's Algorithm Complexity

The time complexity Of Kruskal's Algorithm is: O(E log E).

Kruskal's Algorithm Applications

 In order to layout electrical wiring
 In computer network (LAN connection)

11. Write a program to find the binomial co-efficient C(n,k) [Where n and k are integers and n>k] using
brute force based algorithm and also dynamic programming based algorithm.

#Program to perform Binomial Co-efficient using Brute Force Algorithm

def binomialCoeff_bruteForce(n, k):
# C(n, k) = C(n, n-k)
if k < 0 or k > n:
return 0
if k == 0 or k == n:
return 1
if k > n - k:
k=n-k
res = 1
# Calculate value of [n * (n-1) *---* (n-k+1)] / [k * (k-1) *----* 1]
for i in range(k):
 res = res * (n - i)
res = res // (i + 1) # Use integer division
return res
# Example usage:
n=5
k=2
print(f"Brute Force C({n}, {k}) is: {binomialCoeff_bruteForce(n, k)}")

Output
Brute Force C(5, 2) is: 10

#Program to perform Binomial Co-efficient using Dynamic Programming

def binomialCoeff_DP(n, k):
if k < 0 or k > n:
return 0
if k == 0 or k == n:
return 1
# Create a 1D array to store the previous and current row values,
# optimizing space complexity to O(k)
C = [0] * (k + 1)
C[0] = 1 # nC0 is always 1
for i in range(1, n + 1):
# Update dp[] in reverse order to use the previous values from the same array
for j in range(min(i, k), 0, -1):
C[j] = C[j] + C[j-1]
return C[k]
# Example usage:
n=5
k=2
print(f"Dynamic Programming C({n}, {k}) is: {binomialCoeff_DP(n, k)}")

Output
Dynamic Programming C(5, 2) is: 10
[Link] a program to implement BFS Traversal algorithm.

Breadth First Search or BFS for a Graph in Python

Breadth First Search (BFS) is a fundamental graph traversal algorithm. It begins with a node, then first traverses
all its adjacent nodes. Once all adjacent are visited, then their adjacent are traversed.
 BFS is different from DFS in a way that closest vertices are visited before others. We mainly traverse
vertices level by level.
 Popular graph algorithms like Dijkstra’s shortest path, Kahn’s Algorithm, and Prim’s algorithm are based
on BFS.
 BFS itself can be used to detect cycle in a directed and undirected graph, find shortest path in an
unweighted graph and many more problems.
from collections import defaultdict
# This class represents a directed graph
# using adjacency list representation
class Graph:
# Constructor
def __init__(self):
# Default dictionary to store graph
[Link] = defaultdict(list)
# Function to add an edge to graph
def addEdge(self, u, v):
[Link][u].append(v)
# Function to print a BFS of graph
def BFS(self, s):
# Mark all the vertices as not visited
visited = [False] * (max([Link]) + 1)
# Create a queue for BFS
queue = []
# Mark the source node as
# visited and enqueue it
[Link](s)
visited[s] = True
while queue:
# Dequeue a vertex from
# queue and print it
s = [Link](0)
print(s, end=" ")
# Get all adjacent vertices of the
# dequeued vertex s.
# If an adjacent has not been visited,
# then mark it visited and enqueue it
for i in [Link][s]:
if not visited[i]:
[Link](i)
visited[i] = True
# Driver code
if __name__ == '__main__':
# Create a graph given in
# the above diagram
g = Graph()
[Link](0, 1)
[Link](0, 2)
[Link](1, 2)
[Link](2, 0)
[Link](2, 3)
[Link](3, 3)
print("Following is Breadth First Traversal"
" (starting from vertex 2)")
[Link](2)

Output
Following is Breadth First Traversal (starting from vertex 2)
2031

from collections import deque

def bfs(graph, start_node):
"""
Performs a Breadth-First Search (BFS) on a graph starting from a given node.
Args:
graph (dict): An adjacency list representation of the graph.
start_node: The node to start the traversal from.
Returns:
list: A list of nodes in the order they were visited.
"""
# A queue for BFS traversal, initialized with the start node
# deque is a highly efficient double-ended queue data structure
queue = deque([start_node])
# A set to keep track of visited nodes to avoid infinite loops
visited = {start_node}
# List to store the order of visited nodes
traversal_order = []
while queue:
# Dequeue a node from the front of the queue
current_node = [Link]()
traversal_order.append(current_node)
# Explore neighbors of the current node
for neighbor in [Link](current_node, []):
 if neighbor not in visited:
[Link](neighbor)
[Link](neighbor)
return traversal_order
# --- Example Usage ---
# Define the graph using an adjacency list
# The keys are nodes, and values are lists of their neighbors
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
# Define the starting node
start_node = 'A'
# Run BFS
visited_nodes = bfs(graph, start_node)
# Print the result
print(f"Graph representation: {graph}")
print(f"Starting node for BFS: {start_node}")
print(f"BFS Traversal Order: {visited_nodes}")

Output
Graph representation: {'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'F'], 'D': ['B'], 'E': ['B', 'F'], 'F': ['C', 'E']}
Starting node for BFS: B
BFS Traversal Order: ['B', 'A', 'D', 'E', 'C', 'F']

13. Write a program to implement DFS traversal algorithm

Depth First Traversal (or DFS) for a graph is similar to Depth First Traversal of a tree. The only catch here is, that,
unlike trees, graphs may contain cycles (a node may be visited twice). To avoid processing a node more than
once, use a Boolean visited array. A graph can have more than one DFS traversal.
Depth First Search in Python
Python Depth First Search Algorithm is used for traversing or searching tree or graph data structures. The
algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and
explores as far as possible along each branch before backtracking.
Let us understand the working of Depth First Search with the help of the following illustration: for the source as
0.
#Python program implementations
from collections import defaultdict
# This class represents a directed graph using
# adjacency list representation
class Graph:
# Constructor
def __init__(self):
# Default dictionary to store graph
[Link] = defaultdict(list)
# Function to add an edge to graph
 def addEdge(self, u, v):
[Link][u].append(v)
# A function used by DFS
def DFSUtil(self, v, visited):
# Mark the current node as visited
# and print it
[Link](v)
print(v, end=' ')
# Recur for all the vertices
# adjacent to this vertex
for neighbour in [Link][v]:
if neighbour not in visited:
[Link](neighbour, visited)
# The function to do DFS traversal. It uses
# recursive DFSUtil()
def DFS(self, v):
# Create a set to store visited vertices
visited = set()
# Call the recursive helper function
# to print DFS traversal
[Link](v, visited)
# Driver's code
if __name__ == "__main__":
g = Graph()
[Link](0, 1)
[Link](0, 2)
[Link](1, 2)
[Link](2, 0)
[Link](2, 3)
[Link](3, 3)
print("Following is Depth First Traversal (starting from vertex 2)")
# Function call
[Link](2)
Output
Following is Depth First Traversal (starting from vertex 2):
2013
DFS Algorithm Time Complexity: O(V+E) where V is the number of vertices in the graph and E is the number of
edges
Auxiliary Space: O(V+E)