Algorithms & Data Structures Question

Northeastern University CS5800 Algorithms, Spring 2024 Instructor: Hyonho Lee Assignment 5 (Total Marks: 50 pts) Due Date: March 18, 2024, 6pm Name: Student Number: Collaborators: I, , read and understood Northeastern University’s Academic Integrity Policy (https://osccr.sites.northeastern.edu/academic-integrity-policy/). 1. (40 pts) An AVL tree is a binary search tree such that, for each node x, the height of the left and right subtrees of x differ by at most 1. (This question is from CLRS Problem 13-3 (AVL trees).) The below Python program is a part of AVL tree implementation. avl insert() function inserts a key to the AVL tree and avl delete() function deletes a key from the AVL tree. Note that avl insert() calls avl fixup() function at the end, but avl fixup() function is not implemented yet. avl delete() function is not implemented either. Your task is to complete these two functions, so that avl insert() and avl delete() correctly inserts and deletes a given key, respectively, while maintaining the AVL tree property after the operation. You may add more helper functions. You also need to test your implementation. Below codes contain sample functions for testing. You may add more test cases. class Node: def __init__(self, key: int, p = None, l = None, r = None, h = 1): self.left = l self.right = r self.parent = p self.value = key self.height = h 1 class Tree: def __init__(self, key): self.root = Node(key) def left_rotate(T: Tree, x: Node): y = x.right x.right = y.left if y.left: y.left.parent = x y.parent = x.parent if not x.parent: T.root = y elif x == x.parent.left: x.parent.left = y else: x.parent.right = y y.left = x x.parent = y def right_rotate(T: Tree, y: Node): x = y.left y.left = x.right if x.right: x.right.parent = y x.parent = y.parent if not y.parent: T.root = x elif y == y.parent.left: y.parent.left = x else: y.parent.right = x x.right = y y.parent = x def avl_insert(T: Tree, key: int): cur, cur_p = T.root, None while cur: cur_p = cur if key == cur.value: print(“The given key already exists:”, key) return elif key < cur.value: cur = cur.left else: 2 cur = cur.right new_node = Node(key, cur_p) if not cur_p: T.root = new_node elif key < cur_p.value: cur_p.left = new_node else: cur_p.right = new_node avl_fixup(T, new_node) def avl_fixup(T: Tree, z: Node): ## Write Your Code Here ## ## You may add more helper functions ## def avl_delete(T: Tree, key: int): ## Write Your Code Here ## ## You may add more helper functions ## ################################### ### Below are sample functions for testing. ### You may add more test cases. ################################### def printBST(tree: Tree): print_helper(tree.root, 1) def print_helper(root: Node, depth: int): tab = ” “*(depth*5) if not root: print(tab, “None”) return print_helper(root.right, depth + 1) print(tab + str(root.value) + “(” + str(root.height) + “)”) print_helper(root.left, depth + 1) def arrayToBST(nums: List[int]): tree = Tree(nums[0]) for n in nums[1:]: avl_insert(tree, n) printBST(tree) print(“———————————————–“) return tree 3 tree = arrayToBST([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]) avl_delete(tree, 3) printBST(tree) print(“———————————————–“) avl_delete(tree, 1) printBST(tree) print(“———————————————–“) avl_delete(tree, 10) printBST(tree) 2. (10 pts) Write a function, minimumRemoval, which takes a list of activities, and returns the minimum number of activities that should be removed in order to schedule the remaining activities. Each activity is represented as a pair of start time and finish time. For example, if an input is [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)], then minimumRemoval should return 7. If you remove (3, 5), (0, 6), (3, 9), (5, 9), (6, 10), (8, 12) and (2, 14), then we can schedule the remaining activities (i.e. [(1, 4), (5, 7), (8, 11), (12, 16)]). Write minimumRemoval function using greedy strategy. def minimumRemoval(activities): ## Write Your Code Here ## ## test cases minimumRemoval([(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]) # this should return 7. minimumRemoval([(1,2),(2,3),(3,4),(1,3)]) # this should return 1. minimumRemoval([(1,2),(1,2),(1,2)]) # this should return 2. minimumRemoval([(1,2),(2,3)]) # this should return 0. minimumRemoval([(0,1),(0,1),(0,1)]) # this should return 2. minimumRemoval([(0,1),(1,2)]) # this should return 0. 4 Practice Exercises (The following questions will not be graded. Do not submit solutions. But similar questions may appear in the exams.) Exercise 11.2-2 of CLRS Exercise 11.3-4 of CLRS Exercise 11.4-1 of CLRS Exercise 11.4-2 of CLRS Problem 13-1 of CLRS Exercise 15.1-3 (16.1-3 of the 3rd Ed.) Exercise 15.1-4 (16.1-4 of the 3rd Ed.) Exercise 15.2-3 (16.2-3 of the 3rd Ed.) Exercise 15.2-4 (16.2-4 of the 3rd Ed.) Exercise 15.2-5 (16.2-5 of the 3rd Ed.) Exercise 15.2-7 (16.2-7 of the 3rd Ed.) Exercise 15.3-3 (16.3-3 of the 3rd Ed.) Problem 15-1 (16-1 of the 3rd Ed.) (Coin changing ) 5