Scribd
Upload
6 views14 pages

Essential Algorithms and Code Examples

The document provides a comprehensive overview of various algorithms and data structures, including matrix multiplication, string operations, binary search, sorting algorithms (merge sort, quick sort, radix sort), dynamic programming techniques (rod cutting, knapsack), and graph traversal methods (BFS, DFS). Each section includes code snippets demonstrating the implementation of these algorithms in Python. The document serves as a practical guide for understanding and applying fundamental computer science concepts.

Uploaded by

krishivpatel27
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
6 views14 pages

Essential Algorithms and Code Examples

The document provides a comprehensive overview of various algorithms and data structures, including matrix multiplication, string operations, binary search, sorting algorithms (merge sort, quick sort, radix sort), dynamic programming techniques (rod cutting, knapsack), and graph traversal methods (BFS, DFS). Each section includes code snippets demonstrating the implementation of these algorithms in Python. The document serves as a practical guide for understanding and applying fundamental computer science concepts.

Uploaded by

krishivpatel27
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

INDEX

1. Matrix Multiplication. ...................................................................................................................... 2


2. String Operations. ............................................................................................................................. 3
3. Binary Search. ................................................................................................................................... 4
4. Merge Sort. ........................................................................................................................................ 6
5. Rod Cutting – Divide & Conquer. ................................................................................................... 7
6. Rod Cutting – Dynamic Programming. .......................................................................................... 8
7. Knapsack – Dynamic Programming. .............................................................................................. 9
9. Longest Common Subsequence (LCS). ......................................................................................... 11
10. Quick Sort. ..................................................................................................................................... 12
11. Radix Sort. ..................................................................................................................................... 13
12. BFS / DFS....................................................................................................................................... 14

1
1. Matrix Multiplication.
• Code: -
• A = []
• B = []
• r1 = int(input("Enter rows for Matrix A: "))
• c1 = int(input("Enter cols for Matrix A: "))
• r2 = int(input("Enter rows for Matrix B: "))
• c2 = int(input("Enter cols for Matrix B: "))
•
• if c1 != r2:
• print("Matrix multiplication not possible!")
• else:
• print("Enter Matrix A:")
• for i in range(r1):
• [Link](list(map(int, input().split())))
• print("Enter Matrix B:")
• for i in range(r2):
• [Link](list(map(int, input().split())))
•
• result = [[0]*c2 for _ in range(r1)]
• for i in range(r1):
• for j in range(c2):
• for k in range(c1):
• result[i][j] += A[i][k] * B[k][j]
•
• print("Resultant Matrix:")
• for r in result:
• print(r)

• Output: -

2
2. String Operations.
• Code: -
• s = input("Enter a string: ")
• print("Uppercase:", [Link]())
• print("Lowercase:", [Link]())
• print("Length:", len(s))
• old = input("Enter substring to replace: ")
• new = input("Enter new substring: ")
• print("After replace:", [Link](old, new))
• start = int(input("Enter start index: "))
• end = int(input("Enter end index: "))
• print("Substring:", s[start:end])

• Output: -

3
3. Binary Search.
• Code: -
• def is_sorted(a):
• return all(a[i] <= a[i+1] for i in range(len(a)-1))
•
• def binary_search(arr, x):
• low, high = 0, len(arr) - 1
• while low <= high:
• mid = (low + high) // 2
• if arr[mid] == x:
• return mid
• elif arr[mid] < x:
• low = mid + 1
• else:
• high = mid - 1
• return -1
•
• def main():
• s = input("Enter elements (separated by spaces): ").strip()
• if not s:
• print("No elements entered.")
• return
• try:
• arr = list(map(int, [Link]()))
• except ValueError:
• print("Please enter only integers separated by spaces.")
• return
•
• x_input = input("Enter element to search: ").strip()
• if not x_input:
• print("No search element entered.")
• return
• try:
• x = int(x_input)
• except ValueError:
• print("Search element must be an integer.")
• return
•
• if not is_sorted(arr):
• print("Input is not sorted. Sorting the array.")
• [Link]()
• else:
• print("Input is sorted.")
•
• print("Array used for searching:", arr)
• idx = binary_search(arr, x)

4
• if idx != -1:
• print("Element found at index:", idx)
• else:
• print("Element not found!")
•
• if __name__ == "__main__":
• main()

• Output: -

5
4. Merge Sort.
• Code: -
• 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
•
• arr = list(map(int, input("Enter elements: ").split()))
• merge_sort(arr)
• print("Sorted Array:", arr)

• Output: -

6
5. Rod Cutting – Divide & Conquer.
• Code: -
• def rod_cut(prices, n):
• if n == 0:
• return 0
• max_val = -float('inf')
• for i in range(1, n+1):
• max_val = max(max_val, prices[i-1] + rod_cut(prices, n-i))
• return max_val
•
• prices = list(map(int, input("Enter price list: ").split()))
• n = int(input("Enter rod length: "))
• print("Maximum Obtainable Value:", rod_cut(prices, n))

• Output: -

7
6. Rod Cutting – Dynamic Programming.
• Code: -
• def rod_cut_dp(prices, n):
• dp = [0]*(n+1)
• for i in range(1, n+1):
• for j in range(i):
• dp[i] = max(dp[i], prices[j] + dp[i-j-1])
• return dp[n]
•
• prices = list(map(int, input("Enter price list: ").split()))
• n = int(input("Enter rod length: "))
• print("Maximum Value:", rod_cut_dp(prices, n))

• Output: -

8
7. Knapsack – Dynamic Programming.
• Code: -
• def knapsack(W, wt, val, n):
• dp = [[0]*(W+1) for _ in range(n+1)]
• for i in range(1, n+1):
• for w in range(1, W+1):
• if wt[i-1] <= w:
• dp[i][w] = max(val[i-1] + dp[i-1][w-wt[i-1]], dp[i-1][w])
• else:
• dp[i][w] = dp[i-1][w]
• return dp[n][W]
•
• n = int(input("Enter number of items: "))
• val = list(map(int, input("Enter values: ").split()))
• wt = list(map(int, input("Enter weights: ").split()))
• W = int(input("Enter knapsack capacity: "))
• print("Maximum Profit:", knapsack(W, wt, val, n))

• Output: -

9
8. Knapsack – Greedy (Fractional).

• Code: -
• def fractional_knapsack(value, weight, capacity):
• ratio = [(v/w, w, v) for v, w in zip(value, weight)]
• [Link](reverse=True)
• total = 0
• for r, w, v in ratio:
• if capacity >= w:
• total += v
• capacity -= w
• else:
• total += r * capacity
• break
• return total
•
• n = int(input("Enter number of items: "))
• value = list(map(int, input("Enter values: ").split()))
• weight = list(map(int, input("Enter weights: ").split()))
• capacity = int(input("Enter knapsack capacity: "))
• print("Maximum Profit:", fractional_knapsack(value, weight, capacity))

• Output: -

10
9. Longest Common Subsequence (LCS).
• Code: -
• def lcs(X, Y):
• m, n = len(X), len(Y)
• dp = [[0]*(n+1) for _ in range(m+1)]
• for i in range(m):
• for j in range(n):
• if X[i] == Y[j]:
• dp[i+1][j+1] = dp[i][j] + 1
• else:
• dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
• return dp[m][n]
•
• X = input("Enter first string: ")
• Y = input("Enter second string: ")
• print("Length of LCS:", lcs(X, Y))

• Output: -

11
10. 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)
•
• arr = list(map(int, input("Enter elements: ").split()))
• print("Sorted Array:", quick_sort(arr))

• Output: -

12
11. Radix Sort.
• Code: -
• def counting_sort(arr, exp):
• n = len(arr)
• output = [0]*n
• count = [0]*10
•
• for i in range(n):
• index = arr[i] // exp
• count[index % 10] += 1
•
• for i in range(1, 10):
• count[i] += count[i-1]
•
• i=n-1
• while i >= 0:
• index = arr[i] // exp
• output[count[index % 10] - 1] = arr[i]
• count[index % 10] -= 1
• i -= 1
•
• for i in range(len(arr)):
• arr[i] = output[i]
•
• def radix_sort(arr):
• max_num = max(arr)
• exp = 1
• while max_num // exp > 0:
• counting_sort(arr, exp)
• exp *= 10
•
• arr = list(map(int, input("Enter numbers: ").split()))
• radix_sort(arr)
• print("Sorted Array:", arr)

• Output: -

13
12. BFS / DFS.
• Code: -
• from collections import deque
•
• graph = {}
• n = int(input("Enter number of nodes: "))
•
• for _ in range(n):
• node = input("Enter node: ").strip()
• neighbors = input(f"Enter neighbors of {node} : ").split()
• graph[node] = neighbors
•
• def bfs(start):
• visited = []
• queue = deque([start])
• while queue:
• node = [Link]()
• if node not in visited:
• [Link](node)
• [Link]([Link](node, []))
• return visited
•
• def dfs(start, visited=None):
• if visited is None:
• visited = []
• if start not in visited:
• [Link](start)
• for neighbor in [Link](start, []):
• dfs(neighbor, visited)
• return visited
•
• start = input("Enter start node: ").strip()
• print("BFS Traversal:", bfs(start))
• print("DFS Traversal:", dfs(start))

• Output: -

14

You might also like