Data Structures and Analysis of Algorithms Lab Manual (CSD3009) PDF

School of Computing Science and Artificial Intelligence (SCAI) Data Structures and Analysis of Algorithms Lab Manual (CSD3009) 1  TABLE OF CONTENTS S.No Topic Page No...

School of Computing Science and Artificial Intelligence (SCAI) Data Structures and Analysis of Algorithms Lab Manual (CSD3009) 1  TABLE OF CONTENTS S.No Topic Page No. 1 Bonafide Certificate 3 2 Experiment Evaluation Summary 4 Functions to perform the following operations on a singly 3 linked list Functions to perform the following operations on a doubly 4 linked list 5 Functions to perform the following operations on a circular linked List. 6 Sorting algorithm – insertion, bubble, selection, quick 7 Write a program to perform the following operations: 8 Implements the DFS and BFS. 9 Minimum Spanning Tree – Prim’s and Kruskal’s 10 11 12 Student Name NAVNEET SHARMA : ………………………………………… Register Number 23BCY10030 : ………………………………………… 2 B23+D21+D22 Slot : …………………………………………  SCHOOL OF COMPUTING SCIENCE AND ENGINEERING BONAFIDE CERTIFICATE Bonafide record of work done by NAVNEET SHARMA of CSE(CYBER) _ in VIT BHOPAL UNIVERSITY during winter semester in academic year 2024-2025 Faculty-in-charge Program Chair Submitted to the practical Examination held at VIT Bhopal University, Kothrikalan on ____________ REGISTER NUMBER. Internal Examiner External Examiner 3  EXPERIMENT EVALUATION SUMMARY Name: NAVNEET SHARMA Reg No: 23BCY10030 Marks Faculty S.No Date Experiment (50) Signature 1 2 3 4 5 6 7 8 9 10 4 EX. NO. [[Title of the Lab Experiment]] Aim: Pseudocodes: 5 Sample Input and Output 6 Coding 7 Output / Screen shots: Assessment of an Individual experiment Pseudocode (20) Sample Input & Output (5) Implementation (15) Output (5) Viva (5) Total (50) Result: 8 NAME – ABHSIHEK KUMAR REG NO – 23BCY10049 QUESTION – 1 Program 1: Singly Linked List Operations Aim: To implement a program that performs the following operations on a singly linked list: Creation Insertion Deletion Traversal Algorithm: Step 1: Define a Node class to represent each element in the linked list. Step 2: Define a SinglyLinkedList class with functions for each operation: Creation: Initialize an empty linked list. Insertion: Add a new node to the linked list. Deletion: Remove a specific node from the linked list. Traversal: Display all elements in the linked list. Step 3: Implement the main() function to demonstrate these operations. Pseudocode: plaintext Copy code Class Node: Function __init__(data): data ← data next ← None Class SinglyLinkedList: Function __init__(): head ← None Function insert_at_end(data): Create new_node with data If head is None: head ← new_node Else: temp ← head While temp.next is not None: temp ← temp.next temp.next ← new_node Function delete(data): If head is None: Print "List is empty" If head.data equals data: head ← head.next Else: temp ← head While temp.next is not None and temp.next.data ≠ data: temp ← temp.next If temp.next is not None: temp.next ← temp.next.next Else: Print "Element not found" Function traverse(): temp ← head While temp is not None: Print temp.data temp ← temp.next Main Function: Create an instance of SinglyLinkedList Perform insert, delete, and traverse operations PROGRAM #include using namespace std; // Node structure struct Node { int data; Node* next; }; // Function to create a new node Node* createNode(int data) { Node* newNode = new Node(); newNode->data = data; newNode->next = nullptr; return newNode; } // Insert a node at the end of the linked list void insertAtEnd(Node*& head, int data) { Node* newNode = createNode(data); if (head == nullptr) {  head = newNode; } else { Node* temp = head; while (temp->next != nullptr) { temp = temp->next; } temp->next = newNode; } } // Delete a node with a given value void deleteNode(Node*& head, int value) { if (head == nullptr) { cout data == value) { Node* temp = head; head = head->next; delete temp; return; } Node* temp = head; while (temp->next != nullptr && temp->next->data != value) { temp = temp->next; }  if (temp->next == nullptr) { cout next->next; delete nodeToDelete; } } // Traverse and print the linked list void traverse(Node* head) { Node* temp = head; while (temp != nullptr) { cout data next; } cout 30 -> NULL Value 40 not found in the list. Linked list after attempting to delete 40: 10 -> 30 -> NULL Q2. Aim: To implement a program that performs the following operations on a doubly linked list: Creation Insertion Deletion Traversal Algorithm: Step 1: Define a Node class to represent each element in the doubly linked list. Step 2: Define a DoublyLinkedList class with functions for each operation: Creation: Initialize an empty doubly linked list. Insertion: Add a new node at the end or a specific position. Deletion: Remove a specific node by its value. Traversal: Display all elements in forward and reverse order. Step 3: Implement the main() function to demonstrate these operations. PSEDUO CODE Class Node: Function __init__(data): data ← data next ← None prev ← None Class DoublyLinkedList: Function __init__(): head ← None Function insert_at_end(data): Create new_node with data If head is None: head ← new_node Else: temp ← head While temp.next is not None: temp ← temp.next temp.next ← new_node new_node.prev ← temp Function delete(data): If head is None: Print "List is empty" If head.data equals data: head ← head.next If head is not None: head.prev ← None Return temp ← head While temp.next is not None and temp.data ≠ data: temp ← temp.next If temp.data equals data: If temp.next is not None: temp.next.prev ← temp.prev  If temp.prev is not None: temp.prev.next ← temp.next Else: Print "Element not found" Function traverse_forward(): temp ← head While temp is not None: Print temp.data temp ← temp.next Function traverse_reverse(): temp ← head While temp.next is not None: temp ← temp.next While temp is not None: Print temp.data temp ← temp.prev Main Function: Create an instance of DoublyLinkedList Perform insert, delete, and traverse operations PROGRAM #include using namespace std; // Node structure struct Node { int data; Node* next; Node* prev; }; // Function to create a new node Node* createNode(int data) { Node* newNode = new Node(); newNode->data = data; newNode->next = nullptr; newNode->prev = nullptr; return newNode; } // Insert a node at the end of the doubly linked list void insertAtEnd(Node*& head, int data) { Node* newNode = createNode(data); if (head == nullptr) { head = newNode; } else { Node* temp = head; while (temp->next != nullptr) { temp = temp->next;  } temp->next = newNode; newNode->prev = temp; } } // Delete a node with a given value void deleteNode(Node*& head, int value) { if (head == nullptr) { cout data == value) { Node* temp = head; head = head->next; if (head != nullptr) { head->prev = nullptr; } delete temp; return; } Node* temp = head; while (temp != nullptr && temp->data != value) { temp = temp->next; } if (temp == nullptr) {  cout prev = temp->prev; } if (temp->prev != nullptr) { temp->prev->next = temp->next; } delete temp; } } // Traverse and print the list in forward direction void traverseForward(Node* head) { Node* temp = head; while (temp != nullptr) { cout data next; } cout next; } while (temp != nullptr) { cout data prev; } cout 2 -> 3 -> 4 -> 5 -> Back to Head After Inserting 0 at the Beginning: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> Back to Head After Inserting 6 at the End: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> Back to Head After Deleting 3: 0 -> 1 -> 2 -> 4 -> 5 -> 6 -> Back to Head Node with value 10 not found. Q4. Aim To implement and understand the working of the following sorting algorithms: 1. Insertion Sort 2. Bubble Sort 3. Selection Sort 4. Quick Sort Pseudocode 1. Insertion Sort Iterate through the list from index 1 to n-1. For each element, compare it with the elements before it. Shift larger elements one position to the right and insert the current element in its correct position. 2. Bubble Sort Repeat n-1 iterations: o Compare adjacent elements. o Swap them if the left element is greater than the right. Continue until no swaps are needed. 3. Selection Sort Iterate through the list: o Find the minimum element in the unsorted portion. o Swap it with the first element of the unsorted portion. 4. Quick Sort Select a pivot element. Partition the list so that all elements smaller than the pivot are on its left, and larger ones are on its right. Recursively apply the above steps to the left and right sublists. Program # Insertion Sort 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 return arr # Bubble Sort def bubble_sort(arr): n = len(arr) for i in range(n - 1): for j in range(n - i - 1): if arr[j] > arr[j + 1]: arr[j], arr[j + 1] = arr[j + 1], arr[j] return arr # Selection Sort def selection_sort(arr): n = len(arr) for i in range(n): min_idx = i for j in range(i + 1, n): if arr[j] < arr[min_idx]: min_idx = j arr[i], arr[min_idx] = arr[min_idx], arr[i] return arr # Quick Sort def quick_sort(arr): if len(arr) pivot] return quick_sort(left) + middle + quick_sort(right) # Example Usage if __name__ == "__main__": data = [64, 34, 25, 12, 22, 11, 90] print("Original Array:", data) print("\nInsertion Sort:", insertion_sort(data.copy())) print("Bubble Sort:", bubble_sort(data.copy())) print("Selection Sort:", selection_sort(data.copy())) print("Quick Sort:", quick_sort(data.copy())) OUTPUT Original Array: [64, 34, 25, 12, 22, 11, 90] Insertion Sort: [11, 12, 22, 25, 34, 64, 90] Bubble Sort: [11, 12, 22, 25, 34, 64, 90] Selection Sort: [11, 12, 22, 25, 34, 64, 90] Quick Sort: [11, 12, 22, 25, 34, 64, 90] Q6. Aim To implement a program that performs the following operations on a Binary Search Tree (BST): 1. Insert an element into a BST. 2. Delete an element from a BST. 3. Search for a key element in a BST. seudocode 1. Insert an Element 1. Start at the root. 2. If the tree is empty, the new node becomes the root. 3. If the new element is smaller than the current node, move to the left subtree. 4. If the new element is larger, move to the right subtree. 5. Repeat until an empty spot is found and insert the new node there. 2. Delete an Element 1. Start at the root. 2. Find the node to be deleted:  a. If it has no children, simply remove it. b. If it has one child, link the parent node directly to the child. c. If it has two children, replace it with its in-order successor or predecessor. 3. Search for a Key Element 1. Start at the root. 2. If the key matches the current node, return the node. 3. If the key is smaller, move to the left subtree. 4. If the key is larger, move to the right subtree. 5. Repeat until the key is found or the subtree is empty. PROGRAM class Node: def __init__(self, key): self.key = key self.left = None self.right = None class BST: def __init__(self): self.root = None # i) Insert an element def insert(self, key): self.root = self._insert(self.root, key) def _insert(self, root, key):  if root is None: return Node(key) if key < root.key: root.left = self._insert(root.left, key) else: root.right = self._insert(root.right, key) return root # ii) Delete an element def delete(self, key): self.root = self._delete(self.root, key) def _delete(self, root, key): if root is None: return root # Find the node to delete if key < root.key: root.left = self._delete(root.left, key) elif key > root.key: root.right = self._delete(root.right, key) else: # Node with only one child or no child if root.left is None: return root.right elif root.right is None:  return root.left # Node with two children: get the in-order successor temp = self._min_value_node(root.right) root.key = temp.key root.right = self._delete(root.right, temp.key) return root def _min_value_node(self, root): current = root while current.left is not None: current = current.left return current # iii) Search for an element def search(self, key): return self._search(self.root, key) def _search(self, root, key): if root is None or root.key == key: return root if key < root.key: return self._search(root.left, key) return self._search(root.right, key) # In-order Traversal (For visualization)  def in_order_traversal(self): result = [] self._in_order_traversal(self.root, result) return result def _in_order_traversal(self, root, result): if root is not None: self._in_order_traversal(root.left, result) result.append(root.key) self._in_order_traversal(root.right, result) # Example Usage if __name__ == "__main__": bst = BST() # Insert elements bst.insert(50) bst.insert(30) bst.insert(20) bst.insert(40) bst.insert(70) bst.insert(60) bst.insert(80) print("In-order Traversal After Insertions:", bst.in_order_traversal())  # Search for an element key = 40 result = bst.search(key) print(f"\nSearch for {key}: {'Found' if result else 'Not Found'}") # Delete an element bst.delete(20) print("\nIn-order Traversal After Deleting 20:", bst.in_order_traversal()) bst.delete(30) print("In-order Traversal After Deleting 30:", bst.in_order_traversal()) bst.delete(50) print("In-order Traversal After Deleting 50:", bst.in_order_traversal()) class Node: def __init__(self, key): self.key = key self.left = None self.right = None class BST: def __init__(self): self.root = None # i) Insert an element def insert(self, key): self.root = self._insert(self.root, key) def _insert(self, root, key): if root is None: return Node(key) if key < root.key: root.left = self._insert(root.left, key) else: root.right = self._insert(root.right, key) return root # ii) Delete an element def delete(self, key): self.root = self._delete(self.root, key) def _delete(self, root, key): if root is None: return root # Find the node to delete if key < root.key: root.left = self._delete(root.left, key) elif key > root.key: root.right = self._delete(root.right, key)  else: # Node with only one child or no child if root.left is None: return root.right elif root.right is None: return root.left # Node with two children: get the in-order successor temp = self._min_value_node(root.right) root.key = temp.key root.right = self._delete(root.right, temp.key) return root def _min_value_node(self, root): current = root while current.left is not None: current = current.left return current # iii) Search for an element def search(self, key): return self._search(self.root, key) def _search(self, root, key): if root is None or root.key == key: return root  if key < root.key: return self._search(root.left, key) return self._search(root.right, key) # In-order Traversal (For visualization) def in_order_traversal(self): result = [] self._in_order_traversal(self.root, result) return result def _in_order_traversal(self, root, result): if root is not None: self._in_order_traversal(root.left, result) result.append(root.key) self._in_order_traversal(root.right, result) # Example Usage if __name__ == "__main__": bst = BST() # Insert elements bst.insert(50) bst.insert(30) bst.insert(20) bst.insert(40)  bst.insert(70) bst.insert(60) bst.insert(80) print("In-order Traversal After Insertions:", bst.in_order_traversal()) # Search for an element key = 40 result = bst.search(key) print(f"\nSearch for {key}: {'Found' if result else 'Not Found'}") # Delete an element bst.delete(20) print("\nIn-order Traversal After Deleting 20:", bst.in_order_traversal()) bst.delete(30) print("In-order Traversal After Deleting 30:", bst.in_order_traversal()) bst.delete(50) print("In-order Traversal After Deleting 50:", bst.in_order_traversal()) 6. Implementation of DFS and BFS Aim To implement Depth First Search (DFS) and Breadth First Search (BFS) algorithms for graph traversal. Pseudocode Depth First Search (DFS) 1. Start from a source node. 2. Mark the node as visited. 3. Recursively visit all unvisited neighbors. Breadth First Search (BFS) 1. Start from a source node. 2. Use a queue to explore all neighbors of a node before moving to the next node. 3. Mark each visited node to avoid revisiting. 6. Implementation of DFS and BFS Aim To implement Depth First Search (DFS) and Breadth First Search (BFS) algorithms for graph traversal. Pseudocode Depth First Search (DFS) 1. Start from a source node. 2. Mark the node as visited. 3. Recursively visit all unvisited neighbors. Breadth First Search (BFS) 1. Start from a source node. 2. Use a queue to explore all neighbors of a node before moving to the next node. 3. Mark each visited node to avoid revisiting. Program from collections import defaultdict, deque class Graph: def __init__(self): self.graph = defaultdict(list) # Add an edge to the graph def add_edge(self, u, v): self.graph[u].append(v) # DFS Implementation def dfs(self, start): visited = set() result = [] def dfs_recursive(node): if node not in visited: visited.add(node) result.append(node) for neighbor in self.graph[node]:  dfs_recursive(neighbor) dfs_recursive(start) return result # BFS Implementation def bfs(self, start): visited = set() queue = deque([start]) result = [] while queue: node = queue.popleft() if node not in visited: visited.add(node) result.append(node) queue.extend(self.graph[node]) return result # Example Usage if __name__ == "__main__": g = Graph() g.add_edge(0, 1) g.add_edge(0, 2) g.add_edge(1, 2)  g.add_edge(2, 0) g.add_edge(2, 3) g.add_edge(3, 3) print("DFS starting from node 2:", g.dfs(2)) print("BFS starting from node 2:", g.bfs(2)) OUTPUT DFS starting from node 2: [2, 0, 1, 3] BFS starting from node 2: [2, 0, 3, 1] 7. Minimum Spanning Tree: Prim's and Kruskal's Algorithms Aim To find the Minimum Spanning Tree (MST) of a weighted graph using Prim's Algorithm and Kruskal's Algorithm. Pseudocode Prim's Algorithm 1. Start with any node. 2. Add the smallest edge connecting a visited node to an unvisited node. 3. Repeat until all nodes are visited. Kruskal's Algorithm 1. Sort all edges by weight. 2. Add edges to the MST in order of weight, ensuring no cycles are formed. 3. Stop when the MST contains all vertices. PROGRAM import heapq # Prim's Algorithm def prim(graph, start): visited = set() mst = [] min_heap = [(0, start, -1)] # (weight, node, parent) while min_heap: weight, node, parent = heapq.heappop(min_heap) if node not in visited: visited.add(node) if parent != -1: mst.append((parent, node, weight)) for neighbor, wt in graph[node]: if neighbor not in visited: heapq.heappush(min_heap, (wt, neighbor, node))  return mst # Kruskal's Algorithm class UnionFind: def __init__(self, n): self.parent = list(range(n)) self.rank = * n def find(self, u): if self.parent[u] != u: self.parent[u] = self.find(self.parent[u]) return self.parent[u] def union(self, u, v): root_u = self.find(u) root_v = self.find(v) if root_u != root_v: if self.rank[root_u] > self.rank[root_v]: self.parent[root_v] = root_u elif self.rank[root_u] < self.rank[root_v]: self.parent[root_u] = root_v else: self.parent[root_v] = root_u self.rank[root_u] += 1 def kruskal(edges, n): edges.sort(key=lambda x: x) # Sort by weight uf = UnionFind(n) mst = [] for u, v, weight in edges: if uf.find(u) != uf.find(v): mst.append((u, v, weight)) uf.union(u, v) return mst # Example Usage if __name__ == "__main__": graph = { 0: [(1, 10), (2, 6), (3, 5)], 1: [(0, 10), (3, 15)], 2: [(0, 6), (3, 4)], 3: [(0, 5), (1, 15), (2, 4)] } edges = [ (0, 1, 10), (0, 2, 6),  (0, 3, 5), (1, 3, 15), (2, 3, 4) ] print("Prim's MST:", prim(graph, 0)) print("Kruskal's MST:", kruskal(edges, 4)) OUTPUT Prim's MST: [(0, 3, 5), (3, 2, 4), (0, 1, 10)] Kruskal's MST: [(2, 3, 4), (0, 3, 5), (0, 1, 10)] Explanation DFS and BFS: Traverse graphs in depth-first and breadth-first manners, respectively. Prim's Algorithm: Builds the MST by adding the smallest edge connecting visited and unvisited nodes. Kruskal's Algorithm: Finds the MST by adding the smallest available edge while ensuring no cycles form. THANK YOU