ANALYSIS AND DESIGN OF ALGORITHM
PRACTICAL FILE
NAME: RISHI KUMAR
ENROLLMENT NO: A2305321054
BATCH: 5IT-Y (2021-25)
SUBMITTED TO: DR. DEEPTI MEHROTRA
INDEX
S.NO NAME OF THE EXPERIMENT DATE OF SIGNATURE
EXPERIMENT
EXPERIMENT-1
AIM: Write a program for computing 2 sum and 3 sum.
CODE:
FOR 2 SUM:
def two_sum(nums, target):
num_dict = {}
for i, num in enumerate(nums):
complement = target - num
if complement in num_dict:
return [num_dict[complement], i]
num_dict[num] = i
return None
# Example usage:
nums = [2, 7, 11, 15]
target = 9
result = two_sum(nums, target)
if result:
print(f"Indices of the two numbers that add up to the target:
{result}")
else:
print("No solution found.")
OUTPUT:
CODE FOR 3-SUM:
def three_sum(nums):
result = []
nums.sort()
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue
left, right = i + 1, len(nums) - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total == 0:
result.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
elif total < 0:
left += 1
else:
right -= 1
return result
# Example usage
nums = [-1, 0, 1, 2, -1, -4]
result = three_sum(nums)
if result:
print("Unique triplets that sum to zero:")
for triplet in result:
print(triplet)
else:
print("No solution found.")
OUTPUT:
EXPERIMENT-2
AIM: Write a program for Binary Search
CODE:
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
# Example usage
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
target = 5
result = binary_search(arr, target)
if result != -1:
print(f"Element {target} found at index {result}")
else:
print(f"Element {target} not found in the array")
OUTPUT:
EXPERIMENT-3
AIM: Write a program for Merge Sort.
CODE:
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
merge_sort(left_half)
merge_sort(right_half)
i=j=k=0
while i < len(left_half) and j < len(right_half):
if left_half[i] < right_half[j]:
arr[k] = left_half[i]
i += 1
else:
arr[k] = right_half[j]
j += 1
k += 1
while i < len(left_half):
arr[k] = left_half[i]
i += 1
k += 1
while j < len(right_half):
arr[k] = right_half[j]
j += 1
k += 1
# Example usage
arr = [12, 11, 13, 5, 6, 7]
print("Original array:", arr)
merge_sort(arr)
print("Sorted array:", arr)
OUTPUT:
EXPERIMENT-4
AIM: Write a program for Quick Sort.
CODE:
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
# Example usage
arr = [12, 4, 5, 6, 7, 3, 1, 15]
print("Original array:", arr)
sorted_arr = quick_sort(arr)
print("Sorted array:", sorted_arr)
OUTPUT:
EXPERIMENT-5
AIM: Write a program for BFS and DFS.
CODE FOR BFS:
from collections import defaultdict, deque
class Graph:
def __init__(self):
self.graph = defaultdict(list)
def add_edge(self, u, v):
self.graph[u].append(v)
def bfs(self, start):
visited = [False] * len(self.graph)
queue = deque()
queue.append(start)
visited[start] = True
while queue:
node = queue.popleft()
print(node, end=" ")
for neighbor in self.graph[node]:
if not visited[neighbor]:
queue.append(neighbor)
visited[neighbor] = True
g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 0)
g.add_edge(2, 3)
g.add_edge(3, 3)
print("Breadth-First Traversal (starting from vertex 2):")
g.bfs(2)
OUTPUT:
FOR DFS:
from collections import defaultdict
class Graph:
def __init__(self):
self.graph = defaultdict(list)
def add_edge(self, u, v):
self.graph[u].append(v)
def dfs_util(self, v, visited):
visited[v] = True
print(v, end=" ")
for neighbor in self.graph[v]:
if not visited[neighbor]:
self.dfs_util(neighbor, visited)
def dfs(self, start):
visited = [False] * len(self.graph)
self.dfs_util(start, visited)
g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 0)
g.add_edge(2, 3)
g.add_edge(3, 3)
print("Depth-First Traversal (starting from vertex 2):")
g.dfs(2)
OUTPUT:
EXPERIMENT-7
AIM: Write a program for Travelling salesman.
CODE:
import itertools
def total_distance(tour, distances):
dist = 0
n = len(tour)
for i in range(n):
dist += distances[tour[i]][tour[(i + 1) % n]]
return dist
def tsp_brute_force(distances):
n = len(distances)
cities = list(range(n))
shortest_tour = None
min_distance = float("inf")
for tour in itertools.permutations(cities):
dist = total_distance(tour, distances)
if dist < min_distance:
min_distance = dist
shortest_tour = tour
return shortest_tour, min_distance
distances = [
[0, 29, 20, 21],
[29, 0, 15, 18],
[20, 15, 0, 30],
[21, 18, 30, 0]
]
shortest_tour, min_distance = tsp_brute_force(distances)
print("Shortest tour:", shortest_tour)
print("Minimum distance:", min_distance)
OUTPUT:
EXPERIMENT-8
AIM: Write a program for LCS.
Code:
def lcs_algo(S1, S2, m, n):
L = [[0 for x in range(n+1)] for x in range(m+1)]
# Building the mtrix in bottom-up way
for i in range(m+1):
for j in range(n+1):
if i == 0 or j == 0:
L[i][j] = 0
elif S1[i-1] == S2[j-1]:
L[i][j] = L[i-1][j-1] + 1
else:
L[i][j] = max(L[i-1][j], L[i][j-1])
index = L[m][n]
lcs_algo = [""] * (index+1)
lcs_algo[index] = ""
i=m
j=n
while i > 0 and j > 0:
if S1[i-1] == S2[j-1]:
lcs_algo[index-1] = S1[i-1]
i -= 1
j -= 1
index -= 1
elif L[i-1][j] > L[i][j-1]:
i -= 1
else:
j -= 1
# Printing the sub sequences
print("S1 : " + S1 + "\nS2 : " + S2)
print("LCS: " + "".join(lcs_algo))
S1 = "ACADB"
S2 = "CBDA"
m = len(S1)
n = len(S2)
lcs_algo(S1, S2, m, n)
Output:
EXPERIMENT-9
AIM: Write a program for MST using prims.
Code:
import sys
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = [[0 for _ in range(vertices)] for _ in range(vertices)]
def min_key(self, key, mst_set):
min_value = sys.maxsize
min_index = -1
for v in range(self.V):
if key[v] < min_value and not mst_set[v]:
min_value = key[v]
min_index = v
return min_index
def prim_mst(self):
key = [sys.maxsize] * self.V
parent = [-1] * self.V
key[0] = 0
mst_set = [False] * self.V
parent[0] = -1
for _ in range(self.V - 1):
u = self.min_key(key, mst_set)
mst_set[u] = True
for v in range(self.V):
if self.graph[u][v] > 0 and not mst_set[v] and key[v] >
self.graph[u][v]:
key[v] = self.graph[u][v]
parent[v] = u
self.print_mst(parent)
def print_mst(self, parent):
print("Edge \tWeight")
for i in range(1, self.V):
print(f"{parent[i]} - {i}\t{self.graph[i][parent[i]]}")
# Example usage
g = Graph(5)
g.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]
]
g.prim_mst()
Output:
EXPERIMENT-10
AIM: Write a program for knapsack using greedy approach.
Code:
def fractional_knapsack(items, capacity):
items = sorted(items, key=lambda x: x[1] / x[0], reverse=True)
max_value = 0
for item in items:
weight, value = item
if capacity >= weight:
max_value += value
capacity -= weight
else:
max_value += (value / weight) * capacity
break
return max_value
# Example usage
items = [(10, 60), (20, 100), (30, 120)] # Format: (weight, value)
capacity = 50
max_value = fractional_knapsack(items, capacity)
print(f"Maximum value obtainable: {max_value}")
Output:
