1(A)-IMPLEMENT RECURSIVE ALGORITHM

(LINEAR SEARCH)

PROGRAM:

import time
import matplotlib.pyplot as plt

# Linear Search function

def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return -1

# Measure the time taken for linear search

def measure_time(arr, target):
start_time = time.time()
linear_search(arr, target)
end_time = time.time()
return end_time - start_time

# Plotting the graph

list_sizes = []
times_taken = []

# Testing the linear search for different list sizes

for size in range(1000, 10001, 1000): # Increase the size of the list
arr = list(range(size))
 target = size - 1 # Target is the last element for worst-case scenario
time_taken = measure_time(arr, target)

list_sizes.append(size)
times_taken.append(time_taken)

# Plot the graph

plt.plot(list_sizes, times_taken, marker='o')
plt.title('Linear Search Performance')
plt.xlabel('List Size')
plt.ylabel('Time Taken (seconds)')
plt.grid(True)
plt.show()
OUTPUT:
 1(C)-IMPLEMENT OF NON-RECURSIVE ALGORITHM
(BINARY SEARCH)

PROGRAM:

import time
import matplotlib.pyplot as plt

# Binary Search function

def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1

# Measure the time taken for binary search

def measure_time(arr, target):
start_time = time.time()
binary_search(arr, target)
end_time = time.time()
return end_time - start_time

# Plotting the graph

list_sizes = []
times_taken = []

# Testing the binary search for different list sizes

for size in range(1000, 100001, 5000): # Increase the size of the list
arr = list(range(size))
target = size - 1 # Target is the last element for worst-case scenario
time_taken = measure_time(arr, target)

list_sizes.append(size)
times_taken.append(time_taken)

# Plot the graph

plt.plot(list_sizes, times_taken, marker='o')
plt.title('Binary Search Performance')
plt.xlabel('List Size')
plt.ylabel('Time Taken (seconds)')
plt.grid(True)
plt.show()
OUTPUT:
 1(B)-IMPLEMENT OF RECURSIVE ALGORITHM
(FACTORIAL)

PROGRAM:

import time
import math
import matplotlib.pyplot as plt

# Generate a list of factorial numbers up to a certain size

def generate_factorial_list(size):
return [math.factorial(i) for i in range(1, size + 1)]

# Search for a factorial number

def search_factorial(arr, target):
try:
return arr.index(target)
except ValueError:
return -1

# Measure the time taken for the factorial number search

def measure_time(arr, target):
start_time = time.time()
search_factorial(arr, target)
end_time = time.time()
return end_time - start_time

# Plotting the graph

list_sizes = []
times_taken = []

# Testing the search for different list sizes

for size in range(1, 101): # Generate factorials up to 100!
arr = generate_factorial_list(size)
target = math.factorial(size) # Search for the largest factorial in the list
time_taken = measure_time(arr, target)

list_sizes.append(size)
times_taken.append(time_taken)

# Plot the graph

plt.plot(list_sizes, times_taken, marker='o')
plt.title('Factorial Number Search Performance')
plt.xlabel('Factorial N (Factorial of N!)')
plt.ylabel('Time Taken (seconds)')
plt.grid(True)
plt.show()
OUTPUT:
 2-DIVIDE AND CONQUER
STRASSEN’S MATRIX MULTIPLICATION

PROGRAM:

# Function to perform Strassen's Matrix Multiplication for 2x2 matrices

def strassen_2x2(A, B):
# Extract elements from matrix A
a, b = A[0][0], A[0][1]
c, d = A[1][0], A[1][1]

# Extract elements from matrix B

e, f = B[0][0], B[0][1]
g, h = B[1][0], B[1][1]

# Compute the 7 intermediate products

P1 = a * (f - h)
P2 = (a + b) * h
P3 = (c + d) * e
P4 = d * (g - e)
P5 = (a + d) * (e + h)
P6 = (b - d) * (g + h)
P7 = (a - c) * (e + f)

# Compute the resulting matrix C

C11 = P5 + P4 - P2 + P6
C12 = P1 + P2
C21 = P3 + P4
C22 = P1 + P5 - P3 - P7
 # Return the resulting matrix as a 2x2 list
return [[C11, C12], [C21, C22]]

# Function to take runtime input for the 2x2 matrices

def get_input():
print("Enter the elements of matrix A (2x2):")
A = [[int(input(f"Enter A[{i+1}][{j+1}]: ")) for j in range(2)] for i in range(2)]

print("Enter the elements of matrix B (2x2):")

B = [[int(input(f"Enter B[{i+1}][{j+1}]: ")) for j in range(2)] for i in range(2)]

return A, B

# Main function
if __name__ == "__main__":
A, B = get_input()

# Perform Strassen's Matrix Multiplication for 2x2 matrices

C = strassen_2x2(A, B)

# Output the result

print("Resulting Matrix C (A x B):")
for row in C:
print(row)
OUTPUT:

Enter the elements of matrix A (2x2):

Enter A[1][1]: 1
Enter A[1][2]: 2
Enter A[2][1]: 3
Enter A[2][2]: 4

Enter the elements of matrix B (2x2):

Enter B[1][1]: 5
Enter B[1][2]: 6
Enter B[2][1]: 7
Enter B[2][2]: 8

Resulting Matrix C (A x B):

[19, 22]
[43, 50]
 3-DECREASE AND CONQUER
TOPOLOGICAL SORTING

PROGRAM:

from collections import deque

# Function to perform Topological Sort using Decrease-and-Conquer approach

def topological_sort(vertices, graph):
# Initialize in-degree (number of incoming edges) for each vertex
in_degree = {v: 0 for v in vertices}
for v in vertices:
for neighbor in graph[v]:
in_degree[neighbor] += 1

# Use a deque to process vertices with in-degree 0

zero_in_degree_queue = deque([v for v in vertices if in_degree[v] == 0])

top_order = []

while zero_in_degree_queue:
# Remove a vertex from the queue
vertex = zero_in_degree_queue.popleft()
top_order.append(vertex)

# Decrease the in-degree of neighbors

for neighbor in graph[vertex]:
 in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
zero_in_degree_queue.append(neighbor)

# If the topological order contains all vertices, it's valid

if len(top_order) == len(vertices):
return top_order
else:
raise ValueError("The graph contains a cycle, so topological sort is not possible.")

# Input function to get graph details

def get_input():
n = int(input("Enter the number of vertices: "))

# Initialize graph (empty adjacency list for each vertex)

graph = {i: [] for i in range(n)}

m = int(input(f"Enter the number of directed edges: "))

print("Enter the edges (u v) representing u -> v:")

for _ in range(m):
u, v = map(int, input().split())
graph[u].append(v)

vertices = list(graph.keys()) # List of all vertices

return vertices, graph

# Main function
if __name__ == "__main__":
vertices, graph = get_input()
try:
# Perform Topological Sort
top_order = topological_sort(vertices, graph)

# Output the topological order

print("Topological Order:", top_order)

except ValueError as e:
print(e)
OUTPUT:

Enter the number of vertices: 6

Enter the number of directed edges: 6
Enter the edges (u v) representing u -> v:
52
50
40
41
23
31
Topological Order: [5, 4, 2, 3, 1, 0]
 4-TRANSFORM AND CONQUER
HEAP SORT

PROGRAM:

import time
import matplotlib.pyplot as plt

# Function to heapify a subtree rooted at index i (build max heap)

def heapify(arr, n, i):
largest = i # Initialize largest as root
left = 2 * i + 1 # Left child
right = 2 * i + 2 # Right child

# If left child is larger than root

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

# If right child is larger than largest so far

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

# If largest is not root, swap and heapify the affected subtree

if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)

# Function to perform heap sort

def heap_sort(arr):
 n = len(arr)

# Build a max heap (rearrange the array)

for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)

# One by one extract elements from the heap

for i in range(n-1, 0, -1):
# Swap the root (maximum element) with the last element
arr[i], arr[0] = arr[0], arr[i]

# Heapify the root of the tree

heapify(arr, i, 0)

# Function to take runtime input and sort the list

def get_input():
n = int(input("Enter the number of elements in the array: "))
arr = [int(input(f"Enter element {i+1}: ")) for i in range(n)]
return arr

# Function to plot the time complexity graph

def plot_time_complexity():
sizes = [10, 100, 1000, 5000, 10000]
times = []

for size in sizes:

# Generate a random array of given size
arr = [i for i in range(size, 0, -1)] # Worst-case (sorted in reverse order)

start_time = time.time()
heap_sort(arr)
 end_time = time.time()

# Measure the time it took to sort

times.append(end_time - start_time)

# Plotting the graph

plt.plot(sizes, times, marker='o')
plt.xlabel("Array Size")
plt.ylabel("Time (seconds)")
plt.title("Heap Sort Time Complexity")
plt.grid(True)
plt.show()

# Main function
if __name__ == "__main__":
# Option 1: Heap sort with user input
arr = get_input()
print(f"Original Array: {arr}")
heap_sort(arr)
print(f"Sorted Array: {arr}")

# Option 2: Plot time complexity graph

plot_time_complexity()
OUTPUT:

Enter the number of elements in the array: 5

Enter element 1: 7
Enter element 2: 2
Enter element 3: 9
Enter element 4: 1
Enter element 5: 5
Original Array: [7, 2, 9, 1, 5]
Sorted Array: [1, 2, 5, 7, 9]
 5(A)-DYNAMIC PROGRAMMING
(COIN CHANGING PROBLEM)

PROGRAM:

# Function to find the minimum number of coins needed to make the given amount
def coin_change(coins, amount):
# Create a dp array to store the minimum coins required for each amount up to the target
amount
dp = [float('inf')] * (amount + 1)
dp[0] = 0 # Base case: 0 coins are needed to make 0 amount

# Iterate over each coin denomination

for coin in coins:
# Update the dp array for each amount from coin value to the target amount
for i in range(coin, amount + 1):
dp[i] = min(dp[i], dp[i - coin] + 1)

# If dp[amount] is still infinity, return -1, meaning it's not possible to form that amount
return dp[amount] if dp[amount] != float('inf') else -1

# Function to take runtime input for coins and amount

def get_input():
n = int(input("Enter the number of coin denominations: "))
coins = list(map(int, input(f"Enter the {n} coin denominations (space separated): ").split()))
amount = int(input("Enter the total amount: "))
return coins, amount

# Main function
if __name__ == "__main__":
# Get user input for coins and amount
coins, amount = get_input()

# Call the coin_change function to find the result

result = coin_change(coins, amount)

# Print the result

if result == -1:
print("It is not possible to make the amount with the given coins.")
else:
print(f"The minimum number of coins needed to make the amount {amount} is: {result}")
OUTPUT:

Enter the number of coin denominations: 3

Enter the 3 coin denominations (space separated): 1 2 5
Enter the total amount: 11
The minimum number of coins needed to make the amount 11 is: 3
 5(B)-DYNAMIC PROGRAMING
WARSHALL’S AND FLOYD’S ALGORITHM

PROGRAM:

# Floyd-Warshall Algorithm for All-Pairs Shortest Paths

def floyd_warshall(graph, V):
# Initialize distance matrix
dist = [[float('inf')] * V for _ in range(V)]

# Set distance to 0 for all diagonal elements (distance from a vertex to itself)
for i in range(V):
dist[i][i] = 0

# Populate the initial distances based on the input graph

for u in range(V):
for v, weight in graph[u]:
dist[u][v] = weight

# Perform Floyd-Warshall algorithm

for k in range(V):
for i in range(V):
for j in range(V):
# Update the distance matrix with the shortest path between i and j
if dist[i][j] > dist[i][k] + dist[k][j]:
dist[i][j] = dist[i][k] + dist[k][j]

return dist
# Function to take input for graph
def get_input_floyd():
V = int(input("Enter the number of vertices in the graph: "))
graph = [[] for _ in range(V)]

E = int(input(f"Enter the number of edges: "))

print("Enter each edge as 'u v weight' where u, v are vertices and weight is the edge weight:")
for _ in range(E):
u, v, w = map(int, input().split())
graph[u].append((v, w)) # Directed edge u -> v with weight w

return graph, V

# Main function for Floyd-Warshall

if __name__ == "__main__":
graph, V = get_input_floyd()
dist = floyd_warshall(graph, V)

# Print the shortest path matrix

print("\nShortest Path Matrix:")
for row in dist:
print(row)
OUTPUT:

Enter the number of vertices in the graph: 4

Enter the number of edges: 5
Enter each edge as 'u v weight' where u, v are vertices and weight is the edge weight:
015
0 2 10
123
231
302
Shortest Path Matrix:
[0, 5, 8, 7]
[5, 0, 3, 4]
[6, 6, 0, 1]
[2, 7, 3, 0]
 5(C)-DYNAMIC PROGRAMING
KNAPSACK PROBLEM

PROBLEM:

# Function to solve the knapsack problem using dynamic programming

def knapsack(weights, values, W, n):
# Create a DP table with (n+1) rows and (W+1) columns
dp = [[0] * (W + 1) for _ in range(n + 1)]

# Fill the DP table

for i in range(1, n + 1):
for w in range(1, W + 1):
if weights[i - 1] <= w: # If the item can fit in the knapsack
dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])
else:
dp[i][w] = dp[i - 1][w]

return dp[n][W]

# Function to take runtime input

def get_input():
n = int(input("Enter the number of items: "))
weights = list(map(int, input(f"Enter the weights of {n} items (space separated): ").split()))
values = list(map(int, input(f"Enter the values of {n} items (space separated): ").split()))
W = int(input("Enter the weight capacity of the knapsack: "))
return weights, values, W, n

# Main function
if __name__ == "__main__":
weights, values, W, n = get_input()

max_value = knapsack(weights, values, W, n)

print(f"\nMaximum value that can be obtained: {max_value}")

OUTPUT:

Enter the number of items: 4

Enter the weights of 4 items (space separated): 2 3 4 5
Enter the values of 4 items (space separated): 3 4 5 6
Enter the weight capacity of the knapsack: 5
Maximum value that can be obtained: 7