CERTIFICATE OF ACHIEVEMENT
(Computer Science & Engineering)
This is to certify that
Mr. Mohit
Roll No.: 238032
Branch: B. Tech(AI & DS)
SEMESTER: 4th Sem
has successfully completed all the practical experiments in the
subject
"DAA"
with dedication and excellence.
This certificate is awarded in recognition of their hard work and
commitment to learning.
Date: _______________
Signature
GLOBAL INSTITUTE OF TECHNOLOGY AND MANAGEMENT,
GURUGRAM(HARYANA)
CERTIFICATE OF ACHIEVEMENT
(Computer Science & Engineering)
This is to certify that
Miss. Manya
Roll No.: 238030
Branch: B. Tech(AI & DS)
SEMESTER: 4th Sem
has successfully completed all the practical experiments in the
subject
"DAA"
with dedication and excellence.
This certificate is awarded in recognition of their hard work and
commitment to learning.
Date: _______________
Signature
GLOBAL INSTITUTE OF TECHNOLOGY AND MANAGEMENT,
GURUGRAM(HARYANA)
Index
Sr.
Description Date Sign.
No.
Implement sorting algorithms: Bubble Sort, Insertion Sort,
1.
Selection Sort, Quick Sort, Merge Sort
2. Find Minimum Cost Spanning Tree using Kruskal's Algorithm
3. Implement the Travelling Salesman Problem (TSP)
4. Find the Longest Path in a Directed Acyclic Graph (DAG)
Find the Shortest Path with exactly k edges in a directed &
5.
weighted graph
Find the maximum number of edge-disjoint paths between two
6.
vertices
Implement the 0/1 Knapsack problem using Dynamic
7.
Programming
1. Implementation of Sorting Algorithms
Objective:
To implement and analyze different sorting techniques:
Bubble Sort
Insertion Sort
Selection Sort
Quick Sort
Merge Sort
Code:
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j=i-1
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
def selection_sort(arr):
for i in range(len(arr)):
min_idx = i
for j in range(i + 1, len(arr)):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[0]
less = [x for x in arr[1:] if x <= pivot]
greater = [x for x in arr[1:] if x > pivot]
return quick_sort(less) + [pivot] + quick_sort(greater)
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
L = arr[:mid]
R = arr[mid:]
merge_sort(L)
merge_sort(R)
i=j=k=0
while i < len(L) and j < len(R):
if L[i] < R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
while i < len(L):
arr[k] = L[i]
i += 1
k += 1
while j < len(R):
arr[k] = R[j]
j += 1
k += 1
def main():
while True:
print("\n--- Sorting Algorithms Menu ---")
print("1. Bubble Sort")
print("2. Insertion Sort")
print("3. Selection Sort")
print("4. Quick Sort")
print("5. Merge Sort")
print("6. Exit")
choice = input("Enter your choice (1-6): ")
if choice == '6':
print("Exiting program.")
break
arr = list(map(int, input("Enter numbers separated by space: ").split()))
print("Original array:", arr)
if choice == '1':
bubble_sort(arr)
print("Sorted array (Bubble Sort):", arr)
elif choice == '2':
insertion_sort(arr)
print("Sorted array (Insertion Sort):", arr)
elif choice == '3':
selection_sort(arr)
print("Sorted array (Selection Sort):", arr)
elif choice == '4':
sorted_arr = quick_sort(arr)
print("Sorted array (Quick Sort):", sorted_arr)
elif choice == '5':
merge_sort(arr)
print("Sorted array (Merge Sort):", arr)
else:
print("Invalid choice. Please try again.")
if __name__ == "__main__":
main()
Output:
--- Sorting Algorithms Menu ---
1. Bubble Sort
2. Insertion Sort
3. Selection Sort
4. Quick Sort
5. Merge Sort
6. Exit
Enter your choice (1-6): 5
Enter numbers separated by space: 24 64 78 36 16 8 92 44
Original array: [24, 64, 78, 36, 16, 8, 92, 44]
Sorted array (Merge Sort): [8, 16, 24, 36, 44, 64, 78, 92]
2. Minimum Cost Spanning Tree (Kruskal's Algorithm)
Objective:
To find the Minimum Cost Spanning Tree (MST) of a given undirected graph using Kruskal's
algorithm.
Code:
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = []
def add_edge(self, u, v, w):
self.graph.append([u, v, w])
def find(self, parent, i):
if parent[i] != i:
parent[i] = self.find(parent, parent[i])
return parent[i]
def union(self, parent, rank, x, y):
xroot = self.find(parent, x)
yroot = self.find(parent, y)
if rank[xroot] < rank[yroot]:
parent[xroot] = yroot
elif rank[xroot] > rank[yroot]:
parent[yroot] = xroot
else:
parent[yroot] = xroot
rank[xroot] += 1
def kruskal(self):
result = []
i, e = 0, 0
self.graph.sort(key=lambda item: item[2])
parent = list(range(self.V))
rank = [0] * self.V
while e < self.V - 1:
u, v, w = self.graph[i]
i += 1
x = self.find(parent, u)
y = self.find(parent, v)
if x != y:
e += 1
result.append((u, v, w))
self.union(parent, rank, x, y)
return result
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)
print("Edges in the MST:", g.kruskal())
Output:
Edges in the MST: [(2, 3, 4), (0, 3, 5), (0, 1, 10)]
3. Travelling Salesman Problem (TSP)
Objective:
To find the shortest possible route that visits each city exactly once and returns to the origin
city using a brute-force approach.
Code:
from itertools import permutations
def tsp(graph, start):
V = len(graph)
min_path = float('inf')
for perm in permutations(range(V)):
if perm[0] != start:
continue
cost = 0
for i in range(V - 1):
cost += graph[perm[i]][perm[i + 1]]
cost += graph[perm[-1]][perm[0]]
min_path = min(min_path, cost)
return min_path
graph = [
[0, 10, 15, 20],
[10, 0, 35, 25],
[15, 35, 0, 30],
[20, 25, 30, 0]
]
start = 0
print("Minimum TSP cost:", tsp(graph, start))
Output:
Minimum TSP cost: 80
4. Longest Path in a Directed Acyclic Graph (DAG)
Objective:
To find the longest path from a given source vertex in a Directed Acyclic Graph (DAG) using
topological sorting.
Code:
from collections import defaultdict
class DAG:
def __init__(self, vertices):
self.graph = defaultdict(list)
self.V = vertices
def add_edge(self, u, v, w):
self.graph[u].append((v, w))
def topological_sort_util(self, v, visited, stack):
visited[v] = True
for i, _ in self.graph[v]:
if not visited[i]:
self.topological_sort_util(i, visited, stack)
stack.append(v)
def longest_path(self, s):
visited = [False] * self.V
stack = []
dist = [-float('inf')] * self.V
dist[s] = 0
for i in range(self.V):
if not visited[i]:
self.topological_sort_util(i, visited, stack)
while stack:
i = stack.pop()
for node, weight in self.graph[i]:
if dist[node] < dist[i] + weight:
dist[node] = dist[i] + weight
return dist
g = DAG(6)
g.add_edge(0, 1, 5)
g.add_edge(0, 2, 3)
g.add_edge(1, 3, 6)
g.add_edge(1, 2, 2)
g.add_edge(2, 4, 4)
g.add_edge(2, 5, 2)
g.add_edge(2, 3, 7)
g.add_edge(3, 5, 1)
g.add_edge(3, 4, -1)
g.add_edge(4, 5, -2)
s=1
print("Longest path from vertex", s, ":", g.longest_path(s))
Output:
Longest path from vertex 1 : [-inf, 0, 2, 9, 8, 10]
5. Shortest Path with Exactly k Edges
Objective:
To find the shortest path from a source to a destination with exactly k edges in a directed and
weighted graph using dynamic programming.
Code:
def shortest_path_k_edges(graph, u, v, k):
V = len(graph)
dp = [[[float('inf')] * (k + 1) for _ in range(V)] for _ in range(V)]
for e in range(k + 1):
for i in range(V):
for j in range(V):
if e == 0 and i == j:
dp[i][j][e] = 0
elif e == 1 and graph[i][j] != 0:
dp[i][j][e] = graph[i][j]
elif e > 1:
for a in range(V):
if graph[i][a] != 0 and i != a:
dp[i][j][e] = min(dp[i][j][e], graph[i][a] + dp[a][j][e - 1])
return dp[u][v][k]
graph = [
[0, 10, 3, 2],
[0, 0, 0, 0],
[0, 0, 0, 2],
[0, 0, 0, 0]
]
print("Shortest path from 0 to 3 with 2 edges:", shortest_path_k_edges(graph, 0, 3, 2))
Output:
Shortest path from 0 to 3 with 2 edges: 5
6. Maximum Edge-Disjoint Paths
Objective:
To find the maximum number of edge-disjoint paths between two vertices in a directed graph
using Ford-Fulkerson algorithm.
Code:
from collections import deque
def bfs(rGraph, s, t, parent):
visited = [False] * len(rGraph)
queue = deque([s])
visited[s] = True
while queue:
u = queue.popleft()
for v, capacity in enumerate(rGraph[u]):
if not visited[v] and capacity > 0:
queue.append(v)
visited[v] = True
parent[v] = u
if v == t:
return True
return False
def max_edge_disjoint_paths(graph, source, sink):
rGraph = [row[:] for row in graph]
parent = [-1] * len(graph)
max_flow = 0
while bfs(rGraph, source, sink, parent):
path_flow = float('inf')
s = sink
while s != source:
path_flow = min(path_flow, rGraph[parent[s]][s])
s = parent[s]
v = sink
while v != source:
u = parent[v]
rGraph[u][v] -= path_flow
rGraph[v][u] += path_flow
v = parent[v]
max_flow += path_flow
return max_flow
graph = [
[0, 1, 1, 0],
[0, 0, 0, 1],
[0, 0, 0, 1],
[0, 0, 0, 0]
]
print("Max edge-disjoint paths from 0 to 3:", max_edge_disjoint_paths(graph, 0, 3))
Output:
Max edge-disjoint paths from 0 to 3: 2
7. 0/1 Knapsack Problem (Dynamic Programming)
Objective:
To solve the 0/1 Knapsack problem using dynamic programming, maximizing the value of
items in a knapsack without exceeding its weight capacity.
Code:
def knapsack(W, wt, val, n):
K = [[0 for _ in range(W + 1)] for _ in range(n + 1)]
for i in range(n + 1):
for w in range(W + 1):
if i == 0 or w == 0:
K[i][w] = 0
elif wt[i-1] <= w:
K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w])
else:
K[i][w] = K[i-1][w]
return K[n][W]
val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
n = len(val)
print("Maximum value in Knapsack:", knapsack(W, wt, val, n))
Output:
Maximum value in Knapsack: 220
