API tools faq
paste
Advertisement
GamerBhai02

DAA All Programs In Order

GamerBhai02
Jun 1st, 2025 (edited)
102
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 9.23 KB | Source Code | 0 0
raw download clone embed print report
  1. def gcd_e(f, s):
  2.     while s:
  3.         f,s = s,f%s
  4.     print(f'GCD : {f}')
  5. f, s = int(input("Enter 1st (Smaller) Num: ")), int(input("Enter 2nd Num: "))
  6. gcd_e(f,s)
  7. OP:
  8. Enter 1st (Smaller) Num: 14
  9. Enter 2nd Num: 30
  10. GCD : 2
  11.  
  12.  
  13. def gcd_d(a,b):
  14.     while a!=b:
  15.         if a>=b:
  16.             a-=b
  17.         else:
  18.             b-=a
  19.     print(f'GCD : {a}')
  20. a,b = int(input("Enter 1st (Smaller) Num: ")), int(input("Enter 2nd Num: "))
  21. gcd_d(a,b)
  22. OP:
  23. Enter 1st (Smaller) Num: 14
  24. Enter 2nd Num: 30
  25. GCD : 2
  26.  
  27.  
  28. def brute_force_match(text,pattern):
  29.     n, m = len(text), len(pattern)
  30.     for i in range(n-m+1):
  31.         j=0
  32.         while j<m and text[i+j]==pattern[j]:
  33.             j+=1
  34.         if j==m:
  35.             print(f'Matched at index {i}')
  36.             return
  37.     print("Not found")
  38. text, pattern = input("Enter Text: "), input("Enter Pattern to Match: ")
  39. brute_force_match(text,pattern)
  40. OP:
  41. Enter Text: ABBBABAB
  42. Enter Pattern to Match: ABA
  43. Matched at index 4
  44.  
  45.  
  46. def merge_sort(arr):
  47.     if len(arr)>1:
  48.         mid=len(arr)//2
  49.         left,right = arr[:mid], arr[mid:]
  50.         merge_sort(left)
  51.         merge_sort(right)
  52.         i=j=k=0        
  53.         while i<len(left) and j<len(right):
  54.             if left[i]<right[j]:
  55.                 arr[k]=left[i]
  56.                 i+=1
  57.                 k+=1
  58.             else:
  59.                 arr[k]=right[j]
  60.                 j+=1
  61.                 k+=1
  62.         while i<len(left):
  63.             arr[k]=left[i]
  64.             i+=1
  65.             k+=1
  66.         while j<len(right):
  67.             arr[k]=right[j]
  68.             j+=1
  69.             k+=1    
  70. n = int(input("Enter no. of elements: "))
  71. arr = []
  72. for i in range(n):
  73.     arr.append(int(input(f"Enter Element {i+1}: ")))
  74. print("Original array: ",arr)
  75. merge_sort(arr)
  76. print("Sorted array:",arr)
  77. OP:
  78. Enter no. of elements: 4
  79. Enter Element 1: 12
  80. Enter Element 2: 52
  81. Enter Element 3: 11
  82. Enter Element 4: 123
  83. Original array:  [12, 52, 11, 123]
  84. Sorted array: [11, 12, 52, 123]
  85.  
  86.  
  87. def quick_sort(arr):
  88.     if len(arr)<=1:
  89.         return arr
  90.     pivot = arr[0]
  91.     smaller = [x for x in arr[1:] if x<=pivot]
  92.     bigger = [x for x in arr[1:] if x>pivot]
  93.     return quick_sort(smaller)+[pivot]+quick_sort(bigger)
  94. arr = list(map(int,input("Enter numbers separated with space: ").split()))
  95. print(quick_sort(arr))
  96. OP:
  97. Enter numbers separated with space: 78 12 56 23 95 10 5 4
  98. [4, 5, 10, 12, 23, 56, 78, 95]
  99.  
  100.  
  101. import heapq
  102. def prim(graph, start):
  103.     visited, heap, mst = set(), [(0, start)], []
  104.     while heap:
  105.         cost, node = heapq.heappop(heap)
  106.         if node in visited:
  107.             continue
  108.         visited.add(node)
  109.         mst.append((cost, node))
  110.         for neighbor, weight in graph[node]:
  111.             if neighbor not in visited:
  112.                 heapq.heappush(heap, (weight, neighbor))
  113.     return mst
  114. n = int(input("Enter no. of nodes: "))
  115. nodes = input("Enter Node Names (Capital): ").split()
  116. graph = {node: [] for node in nodes}
  117. print("Now Enter Adjacency List For Each Node One by One:")
  118. for _ in range(n):
  119.     data = input().split()
  120.     graph[data[0]].extend((data[i],int(data[i+1])) for i in range(1,len(data),2))
  121. start = input("Enter the start node: ").strip()
  122. mst = prim(graph, start)
  123. for cost, node in mst:
  124.     print(f"Node: {node}, Cost: {cost}")
  125. OP:
  126. Enter no. of nodes: 3
  127. Enter Node Names (Capital): X Y Z
  128. Now Enter Adjacency List For Each Node One by One:
  129. X Y 3 Z 2
  130. Y X 3 Z 1
  131. Z X 2 Y 1
  132. Enter the start node: X
  133. Node: X, Cost: 0
  134. Node: Z, Cost: 2
  135. Node: Y, Cost: 1
  136.  
  137.  
  138. class DisjointSet:
  139.     def __init__(self, n):
  140.         self.parent = list(range(n))
  141.         self.rank = [0]*n
  142.     def find(self, u):
  143.         if self.parent[u] != u:
  144.             self.parent[u] = self.find(self.parent[u])
  145.         return self.parent[u]
  146.     def union(self, u, v):
  147.         ru, rv = self.find(u), self.find(v)
  148.         if ru == rv:
  149.             return
  150.         if self.rank[ru] > self.rank[rv]:
  151.             self.parent[rv] = ru
  152.         elif self.rank[ru] < self.rank[rv]:
  153.             self.parent[ru] = rv
  154.         else:
  155.             self.parent[rv] = ru
  156.             self.rank[ru] += 1
  157. def kruskal(edges, n):
  158.     edges.sort(key=lambda x: x[2])
  159.     ds, mst = DisjointSet(n), []
  160.     for u, v, w in edges:
  161.         if ds.find(u) != ds.find(v):
  162.             ds.union(u, v)
  163.             mst.append((u, v, w))
  164.     return mst
  165. n = int(input("Enter number of nodes: "))
  166. m = int(input("Enter number of edges: "))
  167. edges = [tuple(map(int, input().split())) for _ in range(m)]
  168. for u, v, w in kruskal(edges, n):
  169.     print(f"Edge: {u} - {v}, Weight: {w}")
  170. OP:
  171. Enter number of nodes: 5
  172. Enter number of edges: 7
  173. 0 1 10
  174. 0 2 6
  175. 0 3 5
  176. 1 3 15
  177. 2 3 4
  178. 3 4 2
  179. 1 4 8
  180. Edge: 3 - 4, Weight: 2
  181. Edge: 2 - 3, Weight: 4
  182. Edge: 0 - 3, Weight: 5
  183. Edge: 1 - 4, Weight: 8
  184.  
  185.  
  186. def fractional_knapsack(capacity, items):
  187.     items.sort(key=lambda x: x[0]/x[1], reverse=True)
  188.     max_val = 0.0
  189.     for value, weight in items:
  190.         if capacity >= weight:
  191.             max_val += value
  192.             capacity -= weight
  193.         else:
  194.             return round(max_val + value * (capacity / weight), 6)
  195.     return round(max_val, 6)
  196. n, w = int(input("Enter no. of items: ")), int(input("Enter maximum capacity: "))
  197. print("Now enter value weight pair for each item")
  198. item_list = list(map(int, input().split()))
  199. items = [(item_list[i],item_list[i+1]) for i in range(0, len(item_list), 2)]
  200. print("Maximum Total Value:",fractional_knapsack(w, items))
  201. OP:
  202. Enter no. of items: 3
  203. Enter maximum capacity: 50
  204. Now enter value weight pair for each item
  205. 60 10 100 20 120 30
  206. Maximum Total Value: 240.0
  207.  
  208.  
  209. def floyd_warshall(n,edges):
  210.     INF = float('inf')
  211.     dist = [[INF] * n for _ in range(n)]
  212.     for i in range(n):
  213.         dist[i][i] = 0
  214.     for u,v,w in edges:
  215.         dist[u-1][v-1] = w
  216.     for k in range(n):
  217.         for i in range(n):
  218.             for j in range(n):
  219.                 dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
  220.     return dist
  221. n, e = int(input("Enter no. of vertices: ")), int(input("Enter no. of edges: "))
  222. edges = [tuple(map(int, input().split())) for _ in range(e)]
  223. print("Shortest Distance Matrix:")
  224. for row in floyd_warshall(n,edges):
  225.     print(*["INF" if x == float('inf') else x for x in row],"")
  226. OP:
  227. Enter no. of vertices: 4
  228. Enter no. of edges: 5
  229. 1 2 4
  230. 1 4 10
  231. 1 3 6
  232. 2 4 5
  233. 3 4 2
  234. Shortest Distance Matrix:
  235. 0 4 6 8
  236. INF 0 INF 5
  237. INF INF 0 2
  238. INF INF INF 0
  239.  
  240.  
  241. def warshall_algorithm(graph, n):
  242.     for k in range(n):
  243.         for i in range(n):
  244.             for j in range(n):
  245.                 graph[i][j] |= graph[i][k] and graph[k][j]
  246.     return graph
  247. n = int(input("Enter the no. of vertices: ").strip())
  248. graph = [list(map(int, input().split())) for _ in range(n)]
  249. transitive_closure = warshall_algorithm(graph, n)
  250. print("Transitive Closure Matrix:")
  251. for row in transitive_closure:
  252.     print(" ".join(map(str, row)))
  253. OP:
  254. Enter the no. of vertices: 4
  255. 0 1 0 0
  256. 0 0 1 1
  257. 0 0 0 0
  258. 1 0 1 0
  259. Transitive Closure Matrix:
  260. 1 1 1 1
  261. 1 1 1 1
  262. 0 0 0 0
  263. 1 1 1 1
  264.  
  265.  
  266. def count_topo_sorts(v,edges):
  267.     from collections import defaultdict
  268.     adj = defaultdict(list)
  269.     in_degree = [0]*V
  270.     for u,v in edges:
  271.         adj[u].append(v)
  272.         in_degree[v] += 1
  273.     visited = [False]*V
  274.     count = [0]
  275.     def backtrack(path):
  276.         if len(path) == V:
  277.             count[0] += 1
  278.             return
  279.         for i in range(V):
  280.             if not visited[i] and in_degree[i]==0:
  281.                 visited[i] = True
  282.                 for neighbor in adj[i]:
  283.                     in_degree[neighbor] -= 1
  284.                 backtrack(path+[i])
  285.                 visited[i] = False
  286.                 for neighbor in adj[i]:
  287.                     in_degree[neighbor] += 1
  288.     backtrack([])
  289.     return count[0]
  290. V,E = int(input("Enter no. of vertices: ")), int(input("Enter no. of edges: "))
  291. edges = [tuple(map(int, input().split())) for _ in range(E)]
  292. print("Count of possible topological sorts: ",count_topo_sorts(V, edges))
  293. OP:
  294. Enter no. of vertices: 6
  295. Enter no. of edges: 6
  296. 2 3
  297. 3 0
  298. 3 1
  299. 4 0
  300. 4 2
  301. 5 1
  302. Count of possible topological sorts:  9
  303.  
  304.  
  305. def subset_sum(arr,N,target_sum):
  306.     for i in range(len(arr)):
  307.         for j in range(len(arr)):
  308.             if arr[i]+arr[j]==target_sum:
  309.                 return True
  310.     return False
  311. N=int(input("Enter no. of elements in array: "))
  312. arr=list(map(int, input().split()))
  313. target_sum=int(input("Enter target sum: "))
  314. print(subset_sum(arr,N,target_sum))
  315. OP:
  316. Enter no. of elements in array: 6
  317. 3 34 4 12 5 2
  318. Enter target sum: 9
  319. True
  320.  
  321.  
  322. def is_safe(board, row, col, n):
  323.     return all(board[i][col] == 0 and
  324.                (col - (row - i) < 0 or board[i][col - (row - i)] == 0) and
  325.                (col + (row - i) >= n or board[i][col + (row - i)] == 0) for i in range(row))
  326. def solve(board, row, n):
  327.     if row == n:
  328.         print("\n".join(" ".join(map(str, r)) for r in board))
  329.         return True
  330.     for col in range(n):
  331.         if is_safe(board, row, col, n):
  332.             board[row][col] = 1
  333.             if solve(board, row + 1, n):
  334.                 return True
  335.             board[row][col] = 0
  336.     return False
  337. n = int(input("Enter number of queens: "))
  338. board = [[0] * n for _ in range(n)]
  339. if not solve(board, 0, n):
  340.     print("No solution found.")
  341. OP:
  342. Enter number of queens: 4
  343. 0 1 0 0
  344. 0 0 0 1
  345. 1 0 0 0
  346. 0 0 1 0
Tags: daa
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!