TMA 03 EEX4435 Data Structures and Algorithms PDF

ANSWERS FOR TMA 03 EEX4435 DATA STRUCTURE AND ALGORITHMS NAME : W.A.S.RANISHANI REG. NO :222554550 DUE DATE : 11/10/2024 CENTER : COLOMBO QUESTION 01 a). 1. Union of Two BSTs with Parent Pointers function findUnionOfBS...

ANSWERS FOR TMA 03 EEX4435 DATA STRUCTURE AND ALGORITHMS NAME : W.A.S.RANISHANI REG. NO :222554550 DUE DATE : 11/10/2024 CENTER : COLOMBO QUESTION 01 a). 1. Union of Two BSTs with Parent Pointers function findUnionOfBSTs(tree1, tree2): resultList = empty list # Get the sorted lists from both trees sortedList1 = traverseInOrder(tree1) sortedList2 = traverseInOrder(tree2) # Merge the two sorted lists resultList = mergeLists(sortedList1, sortedList2) return resultList function traverseInOrder(root): nodeStack = empty stack currentNode = root inorderList = empty list while not nodeStack is empty or currentNode is not null: if currentNode is not null: nodeStack.push(currentNode) currentNode = currentNode.leftChild else: currentNode = nodeStack.pop() inorderList.append(currentNode.value)  currentNode = currentNode.rightChild return inorderList function mergeLists(listA, listB): mergedList = empty list indexA = 0, indexB = 0 # Traverse both lists and merge them in sorted order while indexA < length(listA) and indexB < length(listB): if listA[indexA] < listB[indexB]: mergedList.append(listA[indexA]) indexA = indexA + 1 elif listA[indexA] > listB[indexB]: mergedList.append(listB[indexB]) indexB = indexB + 1 else: # Equal elements mergedList.append(listA[indexA]) indexA = indexA + 1 indexB = indexB + 1 # Add remaining elements from listA if any while indexA < length(listA): mergedList.append(listA[indexA]) indexA = indexA + 1 # Add remaining elements from listB if any while indexB < length(listB): mergedList.append(listB[indexB])  indexB = indexB + 1 return mergedList Intersection of Two BSTs with Parent Pointers function findIntersectionOfBSTs(tree1, tree2): intersectionList = empty list # Perform in-order traversal for both trees sortedList1 = traverseInOrder(tree1) sortedList2 = traverseInOrder(tree2) # Find common elements between the two sorted lists intersectionList = getCommonElements(sortedList1, sortedList2) return intersectionList function getCommonElements(listA, listB): commonList = empty list indexA = 0, indexB = 0 while indexA < length(listA) and indexB < length(listB): if listA[indexA] < listB[indexB]: indexA = indexA + 1 elif listA[indexA] > listB[indexB]: indexB = indexB + 1 else: # listA[indexA] == listB[indexB] commonList.append(listA[indexA])  indexA = indexA + 1 indexB = indexB + 1 return commonList 2. Union of Two BSTs without Parent Pointers class TreeNode: def __init__(self, value): self.value = value self.left = None self.right = None def findUnion(root1, root2): # Perform in-order traversal for both trees list1 = inorderTraversal(root1) list2 = inorderTraversal(root2) # Merge two sorted lists result = mergeSortedLists(list1, list2) return result def inorderTraversal(node): if node is None: return [] # Recursively traverse the left subtree, visit the current node, and then the right subtree return inorderTraversal(node.left) + [node.value] + inorderTraversal(node.right) def mergeSortedLists(list1, list2): result = [] i, j = 0, 0 # Merge the two sorted lists while i < len(list1) and j < len(list2): if list1[i] < list2[j]: result.append(list1[i]) i += 1 elif list1[i] > list2[j]: result.append(list2[j]) j += 1 else: # list1[i] == list2[j] result.append(list1[i]) i += 1 j += 1 # Append remaining elements from list1 while i < len(list1): result.append(list1[i]) i += 1 # Append remaining elements from list2 while j < len(list2): result.append(list2[j]) j += 1 return result  3. intersection of Two BSTs without Parent Pointers function findIntersectionOfBSTs(tree1, tree2): intersectionList = empty list # Perform in-order traversal for both trees sortedList1 = inorderTraversal(tree1) sortedList2 = inorderTraversal(tree2) # Find common elements between the two sorted lists intersectionList = getCommonElements(sortedList1, sortedList2) return intersectionList function getCommonElements(listA, listB): commonElements = empty list indexA = 0, indexB = 0 while indexA < length(listA) and indexB < length(listB): if listA[indexA] < listB[indexB]: indexA = indexA + 1 elif listA[indexA] > listB[indexB]: indexB = indexB + 1 else: # listA[indexA] == listB[indexB] commonElements.append(listA[indexA]) indexA = indexA + 1 indexB = indexB + 1 return commonElements function inorderTraversal(node): if node is null: return empty list # Recursively traverse left subtree, visit the node, then right subtree return inorderTraversal(node.leftChild) + [node.value] + inorderTraversal(node.rightChild) b). [i] To Check Whether the Given BST is an AVL Tree class TreeNode: def __init__(self, value): self.value = value self.left = None self.right = None def isAVL(root): # Helper function that checks balance and calculates height def checkBalance(node): if node is None: return 0 # Base case: height of an empty tree is 0 # Recursively check the left and right subtrees leftHeight = checkBalance(node.left) rightHeight = checkBalance(node.right) # If either subtree is unbalanced, propagate the -1 value upwards if leftHeight == -1 or rightHeight == -1: return -1 # Check if the current node is balanced if abs(leftHeight - rightHeight) > 1: return -1 # Tree is unbalanced # Return the height of the current subtree return max(leftHeight, rightHeight) + 1  # Check if the entire tree is balanced return checkBalance(root) != -1 [ii] To Generate an AVL Tree of Height hhh with a Minimum Number of Nodes class TreeNode: def __init__(self): self.left = None self.right = None self.height = 0 # Height of the node def generateMinAVLTree(h): # Base cases if h < 0: return None # An empty tree (no nodes) elif h == 0: return createNode() # A single node tree (leaf node) # Recursively build the left and right subtrees leftSubtree = generateMinAVLTree(h - 1) rightSubtree = generateMinAVLTree(h - 2) # Create the current root node root = createNode() # Attach the left and right subtrees root.left = leftSubtree root.right = rightSubtree  # Set the height of the current node root.height = h return root def createNode(): # Create and return a new node with default values return TreeNode() c). Union and Intersection for BSTs with Parent Pointers: class TreeNode { int value; TreeNode left, right, parent; // Constructor TreeNode(int value) { this.value = value; left = right = parent = null; } public static void main(String[] args) { // Create a sample TreeNode TreeNode node = new TreeNode(10); System.out.println("TreeNode value: " + node.value); } } Union and Intersection for BSTs without Parent Pointers: class TreeNodeWithoutParent { int value; TreeNodeWithoutParent left, right; // Constructor TreeNodeWithoutParent(int value) { this.value = value; left = right = null; } // Main method to run the code public static void main(String[] args) { // Create an instance of TreeNodeWithoutParent TreeNodeWithoutParent root = new TreeNodeWithoutParent(10); root.left = new TreeNodeWithoutParent(5); root.right = new TreeNodeWithoutParent(15); // Print the values of the nodes System.out.println("Root value: " + root.value);  System.out.println("Left child value: " + root.left.value); System.out.println("Right child value: " + root.right.value); } } Check if a BST is AVL and Generate AVL Tree with Minimum Nodes: class AVLTree { class TreeNode { int value; TreeNode left, right; int height; TreeNode(int value) { this.value = value; left = right = null; height = 1; } } // Function to check if a tree is AVL public boolean isAVL(TreeNode root) { return checkBalance(root) != -1; } private int checkBalance(TreeNode node) { if (node == null) return 0; int leftHeight = checkBalance(node.left); int rightHeight = checkBalance(node.right); if (leftHeight == -1 || rightHeight == -1) return -1; if (Math.abs(leftHeight - rightHeight) > 1) return -1; return Math.max(leftHeight, rightHeight) + 1; } // Function to generate an AVL tree of height h public TreeNode generateMinAVLTree(int h) { if (h < 0) return null; if (h == 0) return new TreeNode(0); // Create leaf node TreeNode leftSubtree = generateMinAVLTree(h - 1); TreeNode rightSubtree = generateMinAVLTree(h - 2); TreeNode root = new TreeNode(0); root.left = leftSubtree;  root.right = rightSubtree; root.height = h; return root; } // Main method to test the AVL Tree functionality public static void main(String[] args) { AVLTree avlTree = new AVLTree(); // Test generating an AVL tree of height 3 TreeNode root = avlTree.generateMinAVLTree(3); System.out.println("Generated AVL Tree of height 3."); // Check if the generated tree is AVL boolean isAvl = avlTree.isAVL(root); System.out.println("Is the generated tree an AVL tree? " + isAvl); } } QUESTION 02 a). i). function createCourseSchedule(courses, prerequisites): graph = buildGraph(courses, prerequisites) sortedCourses = performTopologicalSort(graph) schedule = empty list currentSemester = 0 while sortedCourses is not empty: currentSemester += 1 semesterCourses = empty list // Take only one course in the current semester semesterCourses.append(sortedCourses) // Enroll in the first available course sortedCourses.remove(0) // Remove the enrolled course // Update the prerequisites for dependent courses for each dependentCourse in graph[semesterCourses].dependencies: graph[dependentCourse].prerequisitesCount -= 1 if graph[dependentCourse].prerequisitesCount == 0: sortedCourses.append(dependentCourse) // Add to available courses schedule[currentSemester] = semesterCourses return schedule function buildGraph(courses, prerequisites):  graph = empty dictionary for each course in courses: graph[course] = new CourseNode(course) // Create a node for each course for each (course, prerequisite) in prerequisites: graph[prerequisite].addDependency(course) // Add the course as a dependency graph[course].prerequisitesCount += 1 // Increase the prerequisites count for the course return graph function performTopologicalSort(graph): sortedCourses = empty list queue = empty queue // Initialize the queue with courses that have no prerequisites for each course in graph: if graph[course].prerequisitesCount == 0: queue.enqueue(course) while not queue.isEmpty(): course = queue.dequeue() sortedCourses.append(course) // Update dependencies and remove the course for each dependency in graph[course].dependencies: graph[dependency].prerequisitesCount -= 1 if graph[dependency].prerequisitesCount == 0: queue.enqueue(dependency)  return sortedCourses ii). function createMinimalSemesterSchedule(courses, prerequisites): graph = buildGraph(courses, prerequisites) sortedCourses = performTopologicalSort(graph) schedule = empty list currentSemester = 0 while sortedCourses is not empty: currentSemester += 1 semesterCourses = empty list // Enroll in as many courses as possible in the current semester while sortedCourses is not empty: semesterCourses.append(sortedCourses) // Enroll in the first available course sortedCourses.remove(0) // Remove the enrolled course from the list // Update the prerequisites for courses dependent on the enrolled course for each dependentCourse in graph[semesterCourses[last]].dependencies: graph[dependentCourse].prerequisitesCount -= 1 if graph[dependentCourse].prerequisitesCount == 0: sortedCourses.append(dependentCourse) // Add to available courses schedule[currentSemester] = semesterCourses // Store the courses for the current semester return schedule function buildGraph(courses, prerequisites):  graph = empty dictionary for each course in courses: graph[course] = new CourseNode(course) // Create a node for each course for each (course, prerequisite) in prerequisites: graph[prerequisite].addDependency(course) // Add the course as a dependency graph[course].prerequisitesCount += 1 // Increment prerequisites count for the course return graph function performTopologicalSort(graph): sortedCourses = empty list queue = empty queue // Initialize the queue with courses that have no prerequisites for each course in graph: if graph[course].prerequisitesCount == 0: queue.enqueue(course) while not queue.isEmpty(): course = queue.dequeue() sortedCourses.append(course) // Update dependencies for the removed course for each dependency in graph[course].dependencies: graph[dependency].prerequisitesCount -= 1 if graph[dependency].prerequisitesCount == 0: queue.enqueue(dependency)  return sortedCourses b). import java.util.*; class CourseNode { String courseName; List dependencies; int prerequisitesCount; CourseNode(String courseName) { this.courseName = courseName; this.dependencies = new ArrayList(); this.prerequisitesCount = 0; } void addDependency(CourseNode course) { dependencies.add(course); } } public class CourseScheduler { private Map createGraph(Set courses, Set prerequisites) { Map graph = new HashMap(); for (String course : courses) { graph.put(course, new CourseNode(course)); }  for (Pair prereq : prerequisites) { CourseNode course = graph.get(prereq.first); CourseNode prerequisite = graph.get(prereq.second); prerequisite.addDependency(course); course.prerequisitesCount++; } return graph; } private List topologicalSort(Map graph) { List sortedCourses = new ArrayList(); Queue queue = new LinkedList(); for (CourseNode node : graph.values()) { if (node.prerequisitesCount == 0) { queue.offer(node.courseName); } } while (!queue.isEmpty()) { String course = queue.poll(); sortedCourses.add(course); for (CourseNode dependency : graph.get(course).dependencies) { dependency.prerequisitesCount--; if (dependency.prerequisitesCount == 0) { queue.offer(dependency.courseName); }  } } return sortedCourses; } public List createCourseSchedule(Set courses, Set prerequisites) { Map graph = createGraph(courses, prerequisites); List sortedCourses = topologicalSort(graph); List schedule = new ArrayList(); int currentSemester = 0; while (!sortedCourses.isEmpty()) { currentSemester++; List semesterCourses = new ArrayList(); semesterCourses.add(sortedCourses.get(0)); sortedCourses.remove(0); for (String course : new ArrayList(semesterCourses)) { for (CourseNode dependency : graph.get(course).dependencies) { dependency.prerequisitesCount--; if (dependency.prerequisitesCount == 0) { sortedCourses.add(dependency.courseName); } } } schedule.add(semesterCourses);  } return schedule; } public List createMinimalSemesterSchedule(Set courses, Set prerequisites) { Map graph = createGraph(courses, prerequisites); List sortedCourses = topologicalSort(graph); List schedule = new ArrayList(); int currentSemester = 0; while (!sortedCourses.isEmpty()) { currentSemester++; List semesterCourses = new ArrayList(); while (!sortedCourses.isEmpty()) { semesterCourses.add(sortedCourses.get(0)); sortedCourses.remove(0); for (String course : new ArrayList(semesterCourses)) { for (CourseNode dependency : graph.get(course).dependencies) { dependency.prerequisitesCount--; if (dependency.prerequisitesCount == 0) { sortedCourses.add(dependency.courseName); } } }  } schedule.add(semesterCourses); } return schedule; } public static void main(String[] args) { CourseScheduler scheduler = new CourseScheduler(); Set courses = new HashSet(Arrays.asList( "Algorithms", "Computer Architecture", "Compiler Designs", "Software Engineering", "Design Patterns", "Data Structures", "Operating Systems", "Artificial Intelligence", "Processor Design", "Data Science", "Java Programming", "Database Systems" )); Set prerequisites = new HashSet(Arrays.asList( new Pair("Database Systems", "Compiler Designs"), new Pair("Computer Architecture", "Design Patterns"), new Pair("Software Engineering", "Data Structures"), new Pair("Data Science", "Java Programming"), new Pair("Operating Systems", "Processor Design"), new Pair("Artificial Intelligence", "Algorithms") )); // Create a schedule with one course per semester List scheduleOneCourse = scheduler.createCourseSchedule(courses, prerequisites); System.out.println("Schedule (One Course per Semester): " + scheduleOneCourse);  // Create a schedule with minimal semesters List minimalSchedule = scheduler.createMinimalSemesterSchedule(courses, prerequisites); System.out.println("Schedule (Minimal Semesters): " + minimalSchedule); } } // Helper Pair class class Pair { public A first; public B second; public Pair(A first, B second) { this.first = first; this.second = second; } } QUSTION 03 a). Initialization: Set the distance to the starting node (A) as 0 and to all other nodes as infinity. Mark all nodes as unvisited. Algorithm Execution: Select the unvisited node with the smallest distance (initially A). Update the distances to its neighbors. Mark the node as visited. Repeat until all nodes are visited or the smallest distance is infinity. Initial Setup Node Distance from A Previous Node Visited A 0 - No B ∞ - No C ∞ - No D ∞ - No E ∞ - No F ∞ - No G ∞ - No Starting with Node A: Update neighbors of A (B and C). Distances: B: 2 (A to B) C: 7 (A to C) Node Distance from A Previous Node Visited A 0 - Yes B 7 A No C 2 A No D ∞ - No E ∞ - No F ∞ - No G ∞ - No Next Node B (smallest distance): Update neighbors of B (C and D). New distance to C: 2 + 3 = 5 (update since it’s smaller than 7) D: 2 + 2 = 4 (update) Node Distance from A Previous Node Visited A 0 - Yes B 2 A Yes C 5 B No D 4 B No E ∞ - No F ∞ - No G ∞ - No Next Node D: Update neighbor E. E: 4 + 2 = 6 Node Distance from A Previous Node Visited A 0 - Yes B 2 A Yes C 5 B Yes D 4 B Yes E 6 D No F ∞ - No G ∞ - No Next Node C: Update neighbors E (new path). E: 5 + 2 = 7 (keep 6) Node Distance from A Previous Node Visited A 0 - Yes B 2 A Yes C 5 B No D 4 B Yes E 6 D No F ∞ - No G ∞ - No Next Node E: Update neighbors F and G. F: 6 + 7 = 13 G: 6 + 2 = 8 Node Distance from A Previous Node Visited A 0 - Yes B 2 A Yes C 5 B No D 4 B Yes E 6 D Yes F 13 E No G 8 E No Next Node G: Update neighbors F. F: 8 + 7 = 15 (keep 13) Node Distance from A Previous Node Visited A 0 - Yes B 2 A Yes C 5 B No D 4 B Yes E 6 D Yes F 13 E No G 8 E Yes Next Node F: No more neighbors to update. All nodes visited. Node Distance from A Previous Node A 0 - B 2 A C 5 B D 4 B E 6 D F 13 E G 8 E b). Adjacency List:  A → B (2), C (12), E (7)  B → C (3), E (1)  C → D (1)  D → F (2)  E → F (7), G (2)  F → G (1)  G → C (2) C). Another appropriate algorithm for finding a path of the shortest length is the Bellman-Ford algorithm. It operates well in graphs with negative weights, which the Dijkstra's algorithm cannot do when edge weights should be non-negative. Bellman-Ford works by running over all of the edges many times and updating the shortest paths and detecting any negative-weight cycles on the way.