Here are all the programs from the PDF, organized by category:

---

### **1. SEARCHING AND SORTING ALGORITHMS**

#### **a. Linear Search**

```python
import matplotlib.pyplot as plt

def linear_search(arr, x):

for i in range(len(arr)):
if arr[i] == x:
return i
return -1

arr = [2, 3, 4, 10, 40]

x = 50
result = linear_search(arr, x)

if result == -1:
print("Element is not present in array")
else:
print("Element is present at index", result)

n = [10, 20, 50, 100, 200, 500, 1000]

time = [0.0001, 0.0003, 0.0008, 0.0015, 0.0030, 0.0075, 0.0150]

plt.plot(n, time)
plt.xlabel('Number of Elements')
plt.ylabel('Time Taken')
plt.title('Time Complexity of Linear Search')
plt.show()
```

---

#### **b. Binary Search**

```python
def binary_search(arr, x):
low = 0
high = len(arr) - 1
mid = 0

while low <= high:

mid = (high + low) // 2
if arr[mid] < x:
low = mid + 1
elif arr[mid] > x:
high = mid - 1
else:
return mid
return -1

arr = [2, 3, 4, 10, 40]

x = 10
result = binary_search(arr, x)

if result != -1:
 print("Element is present at index", str(result))
else:
print("Element is not present in array")

import matplotlib.pyplot as plt

X = [0.1, 2.3, 4.5, 6.7, 8.9, 10]
Y = [0.1, 4.9, 16.25, 36.49, 64.81, 100]
plt.plot(X, Y)
plt.show()
```

---

#### **c. Pattern Matching**

```python
def search(pat, txt):
M = len(pat)
N = len(txt)
for i in range(N - M + 1):
j = 0
while j < M:
if txt[i + j] != pat[j]:
break
j += 1
if j == M:
print("Pattern found at index", i)

txt = "AABAACAADAABAAAABAA"
pat = "AABA"
search(pat, txt)
```

---

#### **d. Sorting Algorithms**

##### **i) Insertion Sort**
```python
def insertionSort(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

arr = []
n = int(input("Enter number of elements: "))
for i in range(0, n):
element = int(input("Enter element: "))
arr.append(element)

insertionSort(arr)
print("Sorted array is:")
for i in range(len(arr)):
print("%d" % arr[i])

import matplotlib.pyplot as plt

x = [2, 3, 4, 5, 6, 7, 8, 9, 10]
y = [0, 0, 0.1, 0.3, 0.5, 0.7, 1.0, 1.3, 1.5]
plt.plot(x, y)
plt.xlabel('Size of array')
plt.ylabel('Complexity')
plt.title('Time Complexity of Insertion Sort')
plt.show()
```

##### **ii) Heap Sort**

```python
def heapify(arr, n, i):
largest = i
l = 2 * i + 1
r = 2 * i + 2

if l < n and arr[i] < arr[l]:

largest = l
if r < n and arr[largest] < arr[r]:
largest = r
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)

def heapSort(arr):
n = len(arr)
for i in range(n, -1, -1):
heapify(arr, n, i)
for i in range(n-1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)

arr = [12, 11, 13, 5, 6, 7]

heapSort(arr)
n = len(arr)
print("Sorted array is")
for i in range(n):
print("%d" % arr[i])
```

---

### **2. GRAPH ALGORITHMS**

#### **a. Breadth First Search (BFS)**

```python
from collections import defaultdict

class Graph:
def __init__(self):
self.graph = defaultdict(list)

def addEdge(self, u, v):

self.graph[u].append(v)

def BFS(self, start):

visited = [False] * (max(self.graph) + 1)
queue = []
queue.append(start)
visited[start] = True
 while queue:
start = queue.pop(0)
print(start, end=" ")
for i in self.graph[start]:
if not visited[i]:
queue.append(i)
visited[i] = True

g = Graph()
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 2)
g.addEdge(2, 0)
g.addEdge(2, 3)
g.addEdge(3, 3)

print("Following is Breadth First Traversal (starting from vertex 2)")

g.BFS(2)
```

---

#### **b. Depth First Search (DFS)**

```python
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}

visited = set()

def dfs(visited, graph, node):

if node not in visited:
print(node)
visited.add(node)
for neighbour in graph[node]:
dfs(visited, graph, neighbour)

print("The DFS Traversal : Node visited order is")

dfs(visited, graph, 'A')
```

---

#### **c. Dijkstra's Algorithm**

```python
import sys

def dijkstra(graph, start, goal):

shortest_distance = {}
predecessor = {}
unseenNodes = graph
infinity = sys.maxsize
path = []
 for node in unseenNodes:
shortest_distance[node] = infinity
shortest_distance[start] = 0

while unseenNodes:
minNode = None
for node in unseenNodes:
if minNode is None:
minNode = node
elif shortest_distance[node] < shortest_distance[minNode]:
minNode = node

for childNode, weight in graph[minNode].items():

if weight + shortest_distance[minNode] < shortest_distance[childNode]:
shortest_distance[childNode] = weight + shortest_distance[minNode]
predecessor[childNode] = minNode
unseenNodes.pop(minNode)

currentNode = goal
while currentNode != start:
try:
path.insert(0, currentNode)
currentNode = predecessor[currentNode]
except KeyError:
print('Path not reachable')
break
path.insert(0, start)
if shortest_distance[goal] != infinity:
print('Shortest distance is ' + str(shortest_distance[goal]))
print('And the path is ' + str(path))

graph = {
'A': {'B': 5, 'C': 1},
'B': {'A': 5, 'C': 2, 'D': 1},
'C': {'A': 1, 'B': 2, 'D': 4, 'E': 8},
'D': {'B': 1, 'C': 4, 'E': 3, 'F': 6},
'E': {'C': 8, 'D': 3},
'F': {'D': 6}
}

dijkstra(graph, 'A', 'F')

```

---

#### **d. Prim's Algorithm**

```python
import sys

V = 5
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]
]
def minKey(key, mstSet):
min_val = sys.maxsize
for v in range(V):
if key[v] < min_val and not mstSet[v]:
min_val = key[v]
min_index = v
return min_index

def primMST():
key = [sys.maxsize] * V
parent = [None] * V
key[0] = 0
mstSet = [False] * V
parent[0] = -1

for _ in range(V):
u = minKey(key, mstSet)
mstSet[u] = True
for v in range(V):
if graph[u][v] > 0 and not mstSet[v] and key[v] > graph[u][v]:
key[v] = graph[u][v]
parent[v] = u

print("Edge \tWeight")
for i in range(1, V):
print(parent[i], "-", i, "\t", graph[i][parent[i]])

primMST()
```

---

#### **e. Floyd's Algorithm (All-Pairs Shortest Paths)**

```python
graph = [
[0, 5, 9, 7],
[4, 0, 2, 8],
[3, 2, 0, 1],
[6, 5, 2, 0]
]

n = len(graph)
dist = [[float('inf') for _ in range(n)] for _ in range(n)]

for i in range(n):
for j in range(n):
dist[i][j] = graph[i][j]

for k in range(n):
for i in range(n):
for j in range(n):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

print(dist)
```

---

#### **f. Warshall's Algorithm (Transitive Closure)**

```python
graph = {
'A': ['B', 'C'],
'B': ['C', 'D'],
'C': ['D'],
'D': ['C']
}

def transitive_closure(graph):
closure_matrix = [[0 for _ in range(len(graph))] for _ in range(len(graph))]

for i in range(len(graph)):
for j in graph[list(graph.keys())[i]]:
closure_matrix[i][list(graph.keys()).index(j)] = 1

for k in range(len(graph)):
for i in range(len(graph)):
for j in range(len(graph)):
closure_matrix[i][j] = closure_matrix[i][j] or (closure_matrix[i]
[k] and closure_matrix[k][j])

for row in closure_matrix:

print(row)

transitive_closure(graph)
```

---

### **3. ALGORITHM DESIGN TECHNIQUES**

#### **a. Divide and Conquer (Max and Min)**

```python
def find_max_min(numbers):
if len(numbers) == 1:
return (numbers[0], numbers[0])
mid = len(numbers) // 2
left_max, left_min = find_max_min(numbers[:mid])
right_max, right_min = find_max_min(numbers[mid:])
return (max(left_max, right_max), min(left_min, right_min))

numbers = [3, 5, 2, 8, 1, 4, 10]

max_num, min_num = find_max_min(numbers)
print("Maximum number is:", max_num)
print("Minimum number is:", min_num)
```

---

#### **b. Sorting Algorithms**

##### **i) Merge Sort**
```python
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 = [12, 11, 13, 5, 6, 7]

merge_sort(arr)
print("Sorted array is:", arr)
```

##### **ii) Quick Sort**

```python
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 = [5, 6, 7, 8, 1, 2, 12, 14]

sorted_arr = quick_sort(arr)
print("Sorted array:", sorted_arr)
```

---

### **4. STATE SPACE SEARCH ALGORITHMS**

#### **a. N-Queens Problem**

```python
def is_safe(board, row, col):
for i in range(col):
if board[row][i] == 1:
return False
for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
if board[i][j] == 1:
return False
for i, j in zip(range(row, len(board)), range(col, -1, -1)):
if board[i][j] == 1:
return False
return True
def solve_n_queens(board, col):
if col >= len(board):
return True
for i in range(len(board)):
if is_safe(board, i, col):
board[i][col] = 1
if solve_n_queens(board, col + 1):
return True
board[i][col] = 0
return False

n = int(input("Enter the size of board: "))

board = [[0 for _ in range(n)] for _ in range(n)]
if solve_n_queens(board, 0):
for row in board:
print(row)
else:
print("Solution does not exist")
```

---

### **5. APPROXIMATION ALGORITHMS**

#### **a. Traveling Salesperson Problem**

```python
import numpy as np
import math

dist_matrix = np.array([
[0, 10, 15, 20],
[10, 0, 35, 25],
[15, 35, 0, 30],
[20, 25, 20, 0]
])

num_cities = 4

def opt_solution(dist_matrix, num_cities):

visited = [False] * num_cities
current_city = 0
total_cost = 0
visited[current_city] = True

for _ in range(num_cities - 1):

min_cost = math.inf
next_city = 0
for j in range(num_cities):
if not visited[j] and dist_matrix[current_city][j] < min_cost:
min_cost = dist_matrix[current_city][j]
next_city = j
total_cost += min_cost
visited[next_city] = True
current_city = next_city
return total_cost

opt_sol = opt_solution(dist_matrix, num_cities)

print("Optimal Solution:", opt_sol)
def approx_algorithm(dist_matrix, num_cities):
visited = [False] * num_cities
current_city = 0
total_cost = 0
visited[current_city] = True

for _ in range(num_cities - 1):

min_cost = math.inf
next_city = 0
for j in range(num_cities):
if not visited[j] and dist_matrix[current_city][j] < min_cost:
min_cost = dist_matrix[current_city][j]
next_city = j
total_cost += min_cost
visited[next_city] = True
current_city = next_city
return total_cost

approx_sol = approx_algorithm(dist_matrix, num_cities)

print("Approximated Solution:", approx_sol)
print("Error:", opt_sol - approx_sol)
```

---

#### **b. Randomized Algorithm (kth Smallest Number)**

```python
import random

def kthSmallest(arr, k):

n = len(arr)
temp = arr[:k]
random.shuffle(temp)
for i in range(k, n):
for j in range(k):
if arr[i] < temp[j]:
temp[j] = arr[i]
break
return temp[k - 1]

arr = [12, 3, 5, 7, 19]

k = 2
print("K'th smallest element is", kthSmallest(arr, k))
```

---

These programs cover all the algorithms discussed in the PDF. Let me know if you
need any clarifications or further assistance!