1. Write a program to implement Linear Search.

2. Write a program to implement Binary Search using Iterative and Recursive methods.

Iterative method:
Recursive method:
 3. Write a program to implement Heap sort.

def heapify(array, a, b):

largest = b

l=2*b+1

root = 2 * b + 2

if l < a and array[b] < array[l]:

largest = l

if root < a and array[largest] < array[root]:

largest = root

# Change root

if largest != b:

array[b], array[largest] = array[largest], array[b]

# sort an array of given size

def Heap_Sort(array):

a = len(array)

# maxheap..

for b in range(a // 2 - 1, -1, -1):

heapify(array, a, b)

# extract elements

for b in range(a-1, 0, -1):

array[b], array[0] = array[0], array[b] # swap

heapify(array, b, 0)

# Driver code

array = [ 7, 2, 5, 6, 3, 1, 8, 4]

print("The original array is: ", array)

Heap_Sort(array)

a = len(array)

print ("Array after sorting is: ", array)

Output

The original array is: [7, 2, 5, 6, 3, 1, 8, 4]

Array after sorting is: [1, 2, 3, 4, 5, 6, 7, 8]

4. Write a program to implement quick sort.

def quicksort(arr):

if len(arr) <= 1:

return arr

else:

pivot = arr[0]

left = [x for x in arr[1:] if x < pivot]

right = [x for x in arr[1:] if x >= pivot]

return quicksort(left) + [pivot] + quicksort(right)

# Example usage

arr = [1, 7, 4, 1, 10, 9, -2]

sorted_arr = quicksort(arr)

print("Sorted Array in Ascending Order:")

Output

Sorted Array in Ascending Order:

[-2, 1, 1, 4, 7, 9, 10]

5. Write a program to implement Merge sort

def merge(arr, l, m, r):

n1 = m - l + 1

n2 = r - m

L = [0] * (n1)

R = [0] * (n2)

for i in range(0, n1):

L[i] = arr[l + i]

for j in range(0, n2):

R[j] = arr[m + 1 + j]

i=0 # Initial index of first subarray

j=0 # Initial index of second subarray

k=l # Initial index of merged subarray

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):

m = l+(r-l)//2

mergeSort(arr, l, m)

mergeSort(arr, m+1, r)

merge(arr, l, m, r)

# Driver code to test above

arr = [12, 11, 13, 5, 6, 7]

n = len(arr)

print("Given array is")

for i in range(n):

print("%d" % arr[i],end=" ")

mergeSort(arr, 0, n-1)

print("\n\nSorted array is")

for i in range(n):

print("%d" % arr[i],end=" ")

Output

Given array is

12 11 13 5 6 7

Sorted array is

5 6 7 11 12 13

6. Write a program to implement selection sort

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

# swapping the elements to sort the array

(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('The array after sorting in Ascending Order by selection sort is:')

print(arr)
Output

The array after sorting in Ascending Order by selection sort is:

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

7. Write a program to implement insertion sort

def insertion_sort(arr):

for i in range(1, len(arr)):

key = arr[i]

j=i-1

while j >= 0 and arr[j] > key:

arr[j + 1] = arr[j]

j -= 1

arr[j + 1] = key

# Example usage

array = [5, 2, 8, 12, 1]

print("Original Array:", array)

insertion_sort(array)

print("Sorted Array:", array)

Output

Original Array: [5, 2, 8, 12, 1]

Sorted Array: [1, 2, 5, 8, 12]

8. Write a program to implement Knapsack problem using greedy technique.

class Item:

def __init__(self, value, weight):

self.value = value

self.weight = weight

self.ratio = value / weight

def knapsack_greedy(items, capacity):

# Sort items by value-to-weight ratio in descending order

items.sort(key=lambda x: x.ratio, reverse=True)

total_value = 0.0

for item in items:

if capacity >= item.weight:

# Take the whole item

capacity -= item.weight
 total_value += item.value

else:

# Take the fraction of the remaining capacity

total_value += item.ratio * capacity

break

return total_value

# Example usage

items = [Item(60, 10), Item(100, 20), Item(120, 30)]

capacity = 50

max_value = knapsack_greedy(items, capacity)

print(f"Maximum value in Knapsack = {max_value}")

Output

Maximum value in Knapsack = 240.0

9. Write a program to implement Prim’s algorithm

import heapq

class Graph:

def __init__(self, vertices):

self.V = vertices

self.graph = [[] for _ in range(vertices)]

def add_edge(self, u, v, weight):

self.graph[u].append((v, weight))

self.graph[v].append((u, weight))

def prim_mst(self):

mst_set = [False] * self.V

edge_heap = [(0, 0)] # (weight, vertex)

mst_edges = []

total_weight = 0

while edge_heap:

weight, u = heapq.heappop(edge_heap)

if mst_set[u]:

continue

mst_set[u] = True

total_weight += weight

for v, w in self.graph[u]:
 if not mst_set[v]:

heapq.heappush(edge_heap, (w, v))

mst_edges.append((u, v, w))

print("Edges in MST:")

for u, v, weight in mst_edges:

print(f"{u} - {v}: {weight}")

print(f"Total weight of MST: {total_weight}")

# Example usage:

g = Graph(5)

g.add_edge(0, 1, 2)

g.add_edge(0, 3, 6)

g.add_edge(1, 2, 3)

g.add_edge(1, 3, 8)

g.add_edge(1, 4, 5)

g.add_edge(2, 4, 7)

g.add_edge(3, 4, 9)

g.prim_mst()

Output

Edges in MST:

0 - 1: 2

0 - 3: 6

1 - 2: 3

1 - 3: 8

1 - 4: 5

2 - 4: 7

4 - 3: 9

Total weight of MST: 16