1. General Python Programs:
Python
# Python Program to demonstrate the use of various Python Data Types and Structures
# Integer
my_int = 10
print(f"Integer: {my_int}")
# Float
my_float = 10.5
print(f"Float: {my_float}")
# String
my_string = "Hello, World!"
print(f"String: {my_string}")
# List
my_list = [1, 2, 3, 4, 5]
print(f"List: {my_list}")
# Tuple
my_tuple = (1, 2, 3, 4, 5)
print(f"Tuple: {my_tuple}")
# Dictionary
my_dict = {"name": "Alice", "age": 25}
print(f"Dictionary: {my_dict}")
# Set
my_set = {1, 2, 3, 4, 5}
print(f"Set: {my_set}")
# Boolean
my_bool = True
print(f"Boolean: {my_bool}")
Python
# Python Program to demonstrate OOP Concepts including Class, Objects, Inheritance, and Encapsulation
class Animal:
def __init__(self, name):
self._name = name # Encapsulation (protected attribute)
def speak(self):
raise NotImplementedError("Subclass must implement abstract method")
class Dog(Animal): # Inheritance
def speak(self):
return f"{self._name} says Woof!"
class Cat(Animal): # Inheritance
def speak(self):
return f"{self._name} says Meow!"
# Creating Objects
dog = Dog("Buddy")
cat = Cat("Kitty")
# Accessing Methods
print(dog.speak())
print(cat.speak())
Python
# Python Program to implement array and operations of arrays
from array import array
# Create an array of integers
my_array = array('i', [1, 2, 3, 4, 5])
print(f"Original array: {my_array.tolist()}")
# Append an element to the array
my_array.append(6)
print(f"Array after append: {my_array.tolist()}")
# Insert an element at a specific position
my_array.insert(2, 10)
print(f"Array after insert: {my_array.tolist()}")
# Remove an element from the array
my_array.remove(4)
print(f"Array after remove: {my_array.tolist()}")
# Pop an element from the array
popped_element = my_array.pop()
print(f"Array after pop: {my_array.tolist()}")
print(f"Popped element: {popped_element}")
# Access an element by index
element = my_array[1]
print(f"Element at index 1: {element}")
2. List and Pointer Structure:
Python
# Python Program to create singly linked list and various operations on it
class Node:
def __init__(self, data):
self.data = data
self.next = None
class SinglyLinkedList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
return
last_node = self.head
while last_node.next:
last_node = last_node.next
last_node.next = new_node
def prepend(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
def delete(self, key):
cur_node = self.head
if cur_node and cur_node.data == key:
self.head = cur_node.next
cur_node = None
return
prev = None
while cur_node and cur_node.data != key:
prev = cur_node
cur_node = cur_node.next
if cur_node is None:
return
prev.next = cur_node.next
cur_node = None
def display(self):
elems = []
cur_node = self.head
while cur_node:
elems.append(cur_node.data)
cur_node = cur_node.next
print("Singly Linked List:", elems)
# Example usage
sll = SinglyLinkedList()
sll.append(1)
sll.append(2)
sll.append(3)
sll.prepend(0)
sll.display()
sll.delete(2)
sll.display()
Python
# Python Program to create doubly linked list and various operations on it
class Node:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
class DoublyLinkedList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
return
last_node = self.head
while last_node.next:
last_node = last_node.next
last_node.next = new_node
new_node.prev = last_node
def prepend(self, data):
new_node = Node(data)
if self.head:
self.head.prev = new_node
new_node.next = self.head
self.head = new_node
def delete(self, key):
cur_node = self.head
while cur_node and cur_node.data != key:
cur_node = cur_node.next
if cur_node is None:
return
if cur_node.prev:
cur_node.prev.next = cur_node.next
if cur_node.next:
cur_node.next.prev = cur_node.prev
if cur_node == self.head:
self.head = cur_node.next
cur_node = None
def display(self):
elems = []
cur_node = self.head
while cur_node:
elems.append(cur_node.data)
cur_node = cur_node.next
print("Doubly Linked List:", elems)
# Example usage
dll = DoublyLinkedList()
dll.append(1)
dll.append(2)
dll.append(3)
dll.prepend(0)
dll.display()
dll.delete(2)
dll.display()
Python
# Python Program to create circular linked list and various operations on it
class Node:
def __init__(self, data):
self.data = data
self.next = None
class CircularLinkedList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
new_node.next = self.head
return
cur_node = self.head
while cur_node.next != self.head:
cur_node = cur_node.next
cur_node.next = new_node
new_node.next = self.head
def prepend(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
new_node.next = self.head
return
new_node.next = self.head
cur_node = self.head
while cur_node.next != self.head:
cur_node = cur_node.next
cur_node.next = new_node
self.head = new_node
def delete(self, key):
if self.head is None:
return
if self.head.data == key:
cur_node = self.head
while cur_node.next != self.head:
cur_node = cur_node.next
if self.head == self.head.next:
self.head = None
else:
cur_node.next = self.head.next
self.head = self.head.next
return
prev = None
cur_node = self.head
while cur_node.next != self.head:
prev = cur_node
cur_node = cur_node.next
if cur_node.data == key:
prev.next = cur_node.next
cur_node = None
return
if cur_node.data == key:
prev.next = self.head
cur_node = None
def display(self):
elems = []
if self.head is None:
print("Circular Linked List:", elems)
return
cur_node = self.head
while True:
elems.append(cur_node.data)
cur_node = cur_node.next
if cur_node == self.head:
break
print("Circular Linked List:", elems)
# Example usage
cll = CircularLinkedList()
cll.append(1)
cll.append(2)
cll.append(3)
cll.prepend(0)
cll.display()
cll.delete(2)
cll.display()
3. Stacks and Queues:
Python
# Python Program to implement stack and demonstrate push, pop, and peek operations
class Stack:
def __init__(self):
self.stack = []
def push(self, item):
self.stack.append(item)
def pop(self):
if not self.is_empty():
return self.stack.pop()
return "Stack is empty"
def peek(self):
if not self.is_empty():
return self.stack[-1]
return "Stack is empty"
def is_empty(self):
return len(self.stack) == 0
def display(self):
print("Stack:", self.stack)
# Example usage
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
stack.display()
print("Peek:", stack.peek())
print("Pop:", stack.pop())
stack.display()
print("Pop:", stack.pop())
print("Pop:", stack.pop())
print("Pop:", stack.pop())
Python
# Python Program to implement stack for Bracket-matching application
class Stack:
def __init__(self):
self.stack = []
def push(self, item):
self.stack.append(item)
def pop(self):
if not self.is_empty():
return self.stack.pop()
return None
def peek(self):
if not self.is_empty():
return self.stack[-1]
return None
def is_empty(self):
return len(self.stack) == 0
def is_balanced(expression):
stack = Stack()
brackets = {"(": ")", "{": "}", "[": "]"}
for char in expression:
if char in brackets:
stack.push(char)
elif char in brackets.values():
if stack.is_empty() or brackets[stack.pop()] != char:
return False
return stack.is_empty()
# Example usage
expression = "{[()()]}"
print(f"Is the expression '{expression}' balanced?: {is_balanced(expression)}")
expression = "{[(])}"
print(f"Is the expression '{expression}' balanced?: {is_balanced(expression)}")
Python
# Python Program to implement list-based queues and demonstrate various operations on it
class Queue:
def __init__(self):
self.queue = []
def enqueue(self, item):
self.queue.append(item)
def dequeue(self):
if not self.is_empty():
return self.queue.pop(0)
return "Queue is empty"
def peek(self):
if not self.is_empty():
return self.queue[0]
return "Queue is empty"
def is_empty(self):
return len(self.queue) == 0
def display(self):
print("Queue:", self.queue)
# Example usage
queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
queue.display()
print("Peek:", queue.peek())
print("Dequeue:", queue.dequeue())
queue.display()
print("Dequeue:", queue.dequeue())
print("Dequeue:", queue.dequeue())
print("Dequeue:", queue.dequeue())
Python
# Python Program to implement stack-based queues and demonstrate various operations on it
class StackQueue:
def __init__(self):
self.stack1 = []
self.stack2 = []
def enqueue(self, item):
self.stack1.append(item)
def dequeue(self):
if not self.stack2:
while self.stack1:
self.stack2.append(self.stack1.pop())
if self.stack2:
return self.stack2.pop()
return "Queue is empty"
def display(self):
print("Stack1:", self.stack1)
print("Stack2:", self.stack2)
# Example usage
sq = StackQueue()
sq.enqueue(1)
sq.enqueue(2)
sq.enqueue(3)
sq.display()
print("Dequeue:", sq.dequeue())
sq.display()
print("Dequeue:", sq.dequeue())
print("Dequeue:", sq.dequeue())
print("Dequeue:", sq.dequeue())
Python
# Python Program to implement node-based queues and demonstrate various operations on it
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Queue:
def __init__(self):
self.front = None
self.rear = None
def enqueue(self, item):
new_node = Node(item)
if self.rear:
self.rear.next = new_node
self.rear = new_node
if not self.front:
self.front = self.rear
def dequeue(self):
if self.front:
temp = self.front
self.front = self.front.next
if not self.front:
self.rear = None
return temp.data
return "Queue is empty"
def display(self):
elems = []
cur_node = self.front
while cur_node:
elems.append(cur_node.data)
cur_node = cur_node.next
print("Queue:", elems)
# Example usage
queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
queue.display()
print("Dequeue:", queue.dequeue())
queue.display()
print("Dequeue:", queue.dequeue())
print("Dequeue:", queue.dequeue())
print("Dequeue:", queue.dequeue())
Python
# Python Program to implement queue data structure for simulating media player playlist queues
class PlaylistQueue:
def __init__(self):
self.queue = []
def add_song(self, song):
self.queue.append(song)
print(f"Added song: {song}")
def play_next(self):
if not self.is_empty():
next_song = self.queue.pop(0)
print(f"Playing next song: {next_song}")
else:
print("No songs in the playlist")
def display_playlist(self):
print("Current playlist:", self.queue)
def is_empty(self):
return len(self.queue) == 0
# Example usage
playlist = PlaylistQueue()
playlist.add_song("Song 1")
playlist.add_song("Song 2")
playlist.add_song("Song 3")
playlist.display_playlist()
playlist.play_next()
playlist.display_playlist()
playlist.play_next()
playlist.play_next()
playlist.play_next()
4. Trees:
Python
# Python Program to implement tree data structure and demonstrate depth first traversal
class Node:
def __init__(self, value):
self.value = value
self.children = []
def add_child(self, child_node):
self.children.append(child_node)
def depth_first_traversal(self):
print(self.value)
for child in self.children:
child.depth_first_traversal()
# Example usage
root = Node("A")
child_b = Node("B")
child_c = Node("C")
child_d = Node("D")
child_e = Node("E")
child_f = Node("F")
root.add_child(child_b)
root.add_child(child_c)
child_b.add_child(child_d)
child_b.add_child(child_e)
child_c.add_child(child_f)
print("Depth-First Traversal:")
root.depth_first_traversal()
Python
# Python Program to implement tree data structure and demonstrate breadth-first traversal
from collections import deque
class Node:
def __init__(self, value):
self.value = value
self.children = []
def add_child(self, child_node):
self.children.append(child_node)
def breadth_first_traversal(self):
queue = deque([self])
while queue:
current = queue.popleft()
print(current.value)
queue.extend(current.children)
# Example usage
root = Node("A")
child_b = Node("B")
child_c = Node("C")
child_d = Node("D")
child_e = Node("E")
child_f = Node("F")
root.add_child(child_b)
root.add_child(child_c)
child_b.add_child(child_d)
child_b.add_child(child_e)
child_c.add_child(child_f)
print("Breadth-First Traversal:")
root.breadth_first_traversal()
Python
# Python Program to implement binary search tree to find the minimum node
class TreeNode:
def __init__(self, key):
self.left = None
self.right = None
self.val = key
def insert(root, key):
if root is None:
return TreeNode(key)
if key < root.val:
root.left = insert(root.left, key)
else:
root.right = insert(root.right, key)
return root
def find_minimum(node):
current = node
while current.left is not None:
current = current.left
return current
# Example usage
root = TreeNode(20)
root = insert(root, 10)
root = insert(root, 30)
root = insert(root, 5)
root = insert(root, 15)
min_node = find_minimum(root)
print(f"Minimum node value: {min_node.val}")
Python
# Python Program to implement binary search tree to find the maximum node
class TreeNode:
def __init__(self, key):
self.left = None
self.right = None
self.val = key
def insert(root, key):
if root is None:
return TreeNode(key)
if key < root.val:
root.left = insert(root.left, key)
else:
root.right = insert(root.right, key)
return root
def find_maximum(node):
current = node
while current.right is not None:
current = current.right
return current
# Example usage
root = TreeNode(20)
root = insert(root, 10)
root = insert(root, 30)
root = insert(root, 25)
root = insert(root, 35)
max_node = find_maximum(root)
print(f"Maximum node value: {max_node.val}")
Python
# Python Program to demonstrate the insert and delete method to add/delete nodes in the BST
class TreeNode:
def __init__(self, key):
self.left = None
self.right = None
self.val = key
def insert(root, key):
if root is None:
return TreeNode(key)
if key < root.val:
root.left = insert(root.left, key)
else:
root.right = insert(root.right, key)
return root
def delete_node(root, key):
if root is None:
return root
if key < root.val:
root.left = delete_node(root.left, key)
elif key > root.val:
root.right = delete_node(root.right, key)
else:
if root.left is None:
return root.right
elif root.right is None:
return root.left
temp = find_minimum(root.right)
root.val = temp.val
root.right = delete_node(root.right, temp.val)
return root
def find_minimum(node):
current = node
while current.left is not None:
current = current.left
return current
def inorder_traversal(root):
if root:
inorder_traversal(root.left)
print(root.val, end=" ")
inorder_traversal(root.right)
# Example usage
root = TreeNode(20)
root = insert(root, 10)
root = insert(root, 30)
root = insert(root, 5)
root = insert(root, 15)
print("Inorder traversal before deletion:")
inorder_traversal(root)
print()
root = delete_node(root, 10)
print("Inorder traversal after deletion:")
inorder_traversal(root)
print()
Python
# Python Program to search the node in the BST
class TreeNode:
def __init__(self, key):
self.left = None
self.right = None
self.val = key
def insert(root, key):
if root is None:
return TreeNode(key)
if key < root.val:
root.left = insert(root.left, key)
else:
root.right = insert(root.right, key)
return root
def search(root, key):
if root is None or root.val == key:
return root
if key < root.val:
return search(root.left, key)
return search(root.right, key)
# Example usage
root = TreeNode(20)
root = insert(root, 10)
root = insert(root, 30)
root = insert(root, 5)
root = insert(root, 15)
key = 15
found_node = search(root, key)
if found_node:
print(f"Node with value {key} found in the BST.")
else:
print(f"Node with value {key} not found in the BST.")
Python
# Python program to build up a tree for an expression written in postfix notation and evaluate it
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def is_operator(c):
return c in ['+', '-', '*', '/']
def construct_expression_tree(postfix):
stack = []
for char in postfix:
if not is_operator(char):
stack.append(Node(char))
else:
node = Node(char)
node.right = stack.pop()
node.left = stack.pop()
stack.append(node)
return stack[-1]
def evaluate_expression_tree(root):
if root is None:
return 0
if not is_operator(root.value):
return int(root.value)
left_val = evaluate_expression_tree(root.left)
right_val = evaluate_expression_tree(root.right)
if root.value == '+':
return left_val + right_val
elif root.value == '-':
return left_val - right_val
elif root.value == '*':
return left_val * right_val
elif root.value == '/':
return left_val / right_val
# Example usage
postfix = "23*54*+"
expression_tree_root = construct_expression_tree(postfix)
result = evaluate_expression_tree(expression_tree_root)
print(f"The result of the postfix expression '{postfix}' is: {result}")
5. Hashing and Symbol Tables:
Python
# Python Program to demonstrate computing hash for given strings
def compute_hash(string):
return hash(string)
# Example usage
strings = ["hello", "world", "python", "hashing"]
for s in strings:
print(f"Hash for '{s}': {compute_hash(s)}")
Python
# Python program to implement hash table for storing and searching values
class HashTable:
def __init__(self, size):
self.size = size
self.table = [None] * size
def hash_function(self, key):
return hash(key) % self.size
def insert(self, key, value):
index = self.hash_function(key)
if self.table[index] is None:
self.table[index] = []
self.table[index].append((key, value))
def search(self, key):
index = self.hash_function(key)
if self.table[index] is not None:
for k, v in self.table[index]:
if k == key:
return v
return None
# Example usage
hash_table = HashTable(10)
hash_table.insert("name", "Alice")
hash_table.insert("age", 25)
hash_table.insert("city", "New York")
print("Searching for 'name':", hash_table.search("name"))
print("Searching for 'age':", hash_table.search("age"))
print("Searching for 'city':", hash_table.search("city"))
print("Searching for 'country':", hash_table.search("country"))
Python
# Python Program to create Symbol Table
class SymbolTable:
def __init__(self):
self.table = {}
def insert(self, symbol, value):
self.table[symbol] = value
def lookup(self, symbol):
return self.table.get(symbol, None)
def delete(self, symbol):
if symbol in self.table:
del self.table[symbol]
def display(self):
for symbol, value in self.table.items():
print(f"{symbol}: {value}")
# Example usage
symbol_table = SymbolTable()
symbol_table.insert("x", 10)
symbol_table.insert("y", 20)
symbol_table.insert("z", 30)
print("Symbol Table:")
symbol_table.display()
print("Lookup 'x':", symbol_table.lookup("x"))
print("Lookup 'a':", symbol_table.lookup("a"))
symbol_table.delete("y")
print("Symbol Table after deleting 'y':")
symbol_table.display()
6. Graphs:
Python
# Python program to store and display Graph data structure using adjacency matrix
class Graph:
def __init__(self, vertices):
self.vertices = vertices
self.adj_matrix = [[0] * vertices for _ in range(vertices)]
def add_edge(self, src, dest):
self.adj_matrix[src][dest] = 1
self.adj_matrix[dest][src] = 1 # If the graph is undirected
def display(self):
for row in self.adj_matrix:
print(row)
# Example usage
graph = Graph(5)
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 2)
graph.add_edge(1, 3)
graph.add_edge(2, 4)
print("Adjacency Matrix:")
graph.display()
Python
# Python program to implement Graph traversal (BFS/DFS) using adjacency matrix
class Graph:
def __init__(self, vertices):
self.vertices = vertices
self.adj_matrix = [[0] * vertices for _ in range(vertices)]
def add_edge(self, src, dest):
self.adj_matrix[src][dest] = 1
self.adj_matrix[dest][src] = 1 # If the graph is undirected
def bfs(self, start_vertex):
visited = [False] * self.vertices
queue = []
result = []
queue.append(start_vertex)
visited[start_vertex] = True
while queue:
vertex = queue.pop(0)
result.append(vertex)
for i in range(self.vertices):
if self.adj_matrix[vertex][i] == 1 and not visited[i]:
queue.append(i)
visited[i] = True
return result
def dfs_util(self, vertex, visited, result):
visited[vertex] = True
result.append(vertex)
for i in range(self.vertices):
if self.adj_matrix[vertex][i] == 1 and not visited[i]:
self.dfs_util(i, visited, result)
def dfs(self, start_vertex):
visited = [False] * self.vertices
result = []
self.dfs_util(start_vertex, visited, result)
return result
# Example usage
graph = Graph(5)
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 2)
graph.add_edge(1, 3)
graph.add_edge(2, 4)
print("BFS Traversal starting from vertex 0:", graph.bfs(0))
print("DFS Traversal starting from vertex 0:", graph.dfs(0))
Python
# Python program to implement priority queue and heap operations
import heapq
class PriorityQueue:
def __init__(self):
self.heap = []
def push(self, item, priority):
heapq.heappush(self.heap, (priority, item))
def pop(self):
return heapq.heappop(self.heap)[1]
def peek(self):
return self.heap[0][1] if self.heap else None
def is_empty(self):
return len(self.heap) == 0
def display(self):
print("Priority Queue:", self.heap)
# Example usage
pq = PriorityQueue()
pq.push("Task 1", 3)
pq.push("Task 2", 1)
pq.push("Task 3", 2)
print("Priority Queue after pushes:")
pq.display()
print("Peek:", pq.peek())
print("Pop:", pq.pop())
print("Priority Queue after pop:")
pq.display()
print("Peek:", pq.peek())
print("Pop:", pq.pop())
print("Pop:", pq.pop())
print("Is empty:", pq.is_empty())
7. Searching:
Python
# Python program for linear search on an unordered list of items
def linear_search_unordered(lst, target):
for i, item in enumerate(lst):
if item == target:
return i
return -1
# Example usage
unordered_list = [34, 7, 23, 32, 5, 62]
target = 23
result = linear_search_unordered(unordered_list, target)
print(f"Target {target} found at index: {result}")
Python
# Python program for linear search on an ordered list of items
def linear_search_ordered(lst, target):
for i, item in enumerate(lst):
if item == target:
return i
elif item > target:
break
return -1
# Example usage
ordered_list = [3, 5, 7, 9, 11, 13]
target = 9
result = linear_search_ordered(ordered_list, target)
print(f"Target {target} found at index: {result}")
Python
# Python program for binary search on an ordered list of items
def binary_search(lst, target):
low = 0
high = len(lst) - 1
while low <= high:
mid = (low + high) // 2
if lst[mid] == target:
return mid
elif lst[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
# Example usage
ordered_list = [3, 5, 7, 9, 11, 13]
target = 7
result = binary_search(ordered_list, target)
print(f"Target {target} found at index: {result}")
Python
# Python program for interpolation search algorithm
def interpolation_search(lst, target):
low = 0
high = len(lst) - 1
while low <= high and target >= lst[low] and target <= lst[high]:
if low == high:
if lst[low] == target:
return low
return -1
pos = low + ((high - low) // (lst[high] - lst[low]) * (target - lst[low]))
if lst[pos] == target:
return pos
if lst[pos] < target:
low = pos + 1
else:
high = pos - 1
return -1
# Example usage
ordered_list = [3, 5, 7, 9, 11, 13]
target = 9
result = interpolation_search(ordered_list, target)
print(f"Target {target} found at index: {result}")
8. Sorting:
Python
# Python program for implementing Insertion Sort
def insertion_sort(lst):
for i in range(1, len(lst)):
key = lst[i]
j = i - 1
while j >= 0 and key < lst[j]:
lst[j + 1] = lst[j]
j -= 1
lst[j + 1] = key
return lst
# Example usage
unordered_list = [12, 11, 13, 5, 6]
sorted_list = insertion_sort(unordered_list.copy())
print(f"Insertion Sort: {sorted_list}")
Python
# Python program for implementing Bubble Sort
def bubble_sort(lst):
n = len(lst)
for i in range(n):
swapped = False
for j in range(0, n - i - 1):
if lst[j] > lst[j + 1]:
lst[j], lst[j + 1] = lst[j + 1], lst[j]
swapped = True
if not swapped:
break
return lst
# Example usage
unordered_list = [64, 34, 25, 12, 22, 11, 90]
sorted_list = bubble_sort(unordered_list.copy())
print(f"Bubble Sort: {sorted_list}")
Python
# Python program for implementing Quick Sort
def quick_sort(lst):
if len(lst) <= 1:
return lst
pivot = lst[len(lst) // 2]
left = [x for x in lst if x < pivot]
middle = [x for x in lst if x == pivot]
right = [x for x in lst if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
# Example usage
unordered_list = [10, 7, 8, 9, 1, 5]
sorted_list = quick_sort(unordered_list.copy())
print(f"Quick Sort: {sorted_list}")
Python
# Python program for implementing Selection Sort
def selection_sort(lst):
for i in range(len(lst)):
min_idx = i
for j in range(i + 1, len(lst)):
if lst[j] < lst[min_idx]:
min_idx = j
lst[i], lst[min_idx] = lst[min_idx], lst[i]
return lst
# Example usage
unordered_list = [64, 25, 12, 22, 11]
sorted_list = selection_sort(unordered_list.copy())
print(f"Selection Sort: {sorted_list}")
9. Selection Algorithms:
Python
# Python program to implement Randomized Selection
import random
def randomized_partition(arr, low, high):
pivot_index = random.randint(low, high)
arr[high], arr[pivot_index] = arr[pivot_index], arr[high]
return partition(arr, low, high)
def partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
def randomized_select(arr, low, high, k):
if low == high:
return arr[low]
pivot_index = randomized_partition(arr, low, high)
num_elements_in_left = pivot_index - low + 1
if k == num_elements_in_left:
return arr[pivot_index]
elif k < num_elements_in_left:
return randomized_select(arr, low, pivot_index - 1, k)
else:
return randomized_select(arr, pivot_index + 1, high, k - num_elements_in_left)
# Example usage
arr = [12, 3, 5, 7, 4, 19, 26]
k = 3
result = randomized_select(arr, 0, len(arr) - 1, k)
print(f"The {k}rd smallest element is {result}")
Python
# Python program to implement Deterministic Selection (Median of Medians)
def partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
def deterministic_select(arr, low, high, k):
if low == high:
return arr[low]
pivot_index = median_of_medians(arr, low, high)
pivot_index = partition(arr, low, high, pivot_index)
num_elements_in_left = pivot_index - low + 1
if k == num_elements_in_left:
return arr[pivot_index]
elif k < num_elements_in_left:
return deterministic_select(arr, low, pivot_index - 1, k)
else:
return deterministic_select(arr, pivot_index + 1, high, k - num_elements_in_left)
def median_of_medians(arr, low, high):
n = high - low + 1
if n <= 5:
return partition5(arr, low, high)
medians = []
for i in range(low, high + 1, 5):
sub_high = min(i + 4, high)
median = partition5(arr, i, sub_high)
medians.append(arr[median])
return median_of_medians(medians, 0, len(medians) - 1)
def partition5(arr, low, high):
sublist = arr[low:high + 1]
sublist.sort()
median_index = len(sublist) // 2
return arr.index(sublist[median_index])
# Example usage
arr = [12, 3, 5, 7, 4, 19, 26]
k = 3
result = deterministic_select(arr, 0, len(arr) - 1, k)
print(f"The {k}rd smallest element is {result}")
10. Application:
Python
# Python program to create an application for storing Polynomial
class Polynomial:
def __init__(self, coefficients):
self.coefficients = coefficients # Store coefficients as a list
def __repr__(self):
degree = len(self.coefficients) - 1
terms = []
for i, coeff in enumerate(self.coefficients):
if coeff != 0:
term = f"{coeff}x^{degree-i}" if degree-i > 1 else f"{coeff}x" if degree-i == 1 else f"{coeff}"
terms.append(term)
return " + ".join(terms)
# Example usage
poly1 = Polynomial([2, 0, -1, 3]) # Represents 2x^3 - x^2 + 3
print("Polynomial 1:", poly1)
poly2 = Polynomial([0, 1, 0, 4, 2]) # Represents x^4 + 4x^3 + 2x
print("Polynomial 2:", poly2)
Python
# Python program to create an application for adding two Polynomials
class Polynomial:
def __init__(self, coefficients):
self.coefficients = coefficients # Store coefficients as a list
def __repr__(self):
degree = len(self.coefficients) - 1
terms = []
for i, coeff in enumerate(self.coefficients):
if coeff != 0:
term = f"{coeff}x^{degree-i}" if degree-i > 1 else f"{coeff}x" if degree-i == 1 else f"{coeff}"
terms.append(term)
return " + ".join(terms)
def __add__(self, other):
len_self = len(self.coefficients)
len_other = len(other.coefficients)
max_len = max(len_self, len_other)
result_coefficients = [0] * max_len
for i in range(max_len):
if i < len_self:
result_coefficients[i] += self.coefficients[i]
if i < len_other:
result_coefficients[i] += other.coefficients[i]
return Polynomial(result_coefficients)
# Example usage
poly1 = Polynomial([2, 0, -1, 3]) # Represents 2x^3 - x^2 + 3
poly2 = Polynomial([0, 1, 0, 4, 2]) # Represents x^4 + 4x^3 + 2x
print("Polynomial 1:", poly1)
print("Polynomial 2:", poly2)
poly_sum = poly1 + poly2
print("Sum of Polynomial 1 and Polynomial 2:", poly_sum)