Homework 2 CSCI570 Fall 2024 Due Sep 22 2024 1 Prove by induction that if we remove the root of a k th order binomial tree it results in k binomial trees of the smaller orders You can only use the definition of Bk Per the definition Bk is formed by joining two Bk 1 trees Base Case B1 If we remove the root node we get 1 empty binomial tree B0 Induction Hypothesis Assume that Bk 1 without its root node is made up of k 1 trees of smaller orders Proving k th case Per our definition Bk is formed by joining two Bk 1 trees The joining happens at the root node of one of the two trees making the root node of the resulting tree connected to the root node of a Bk 1 tree as well as being part of the other tree Therefore when we remove the root node we get One Bk 1 tree and One Bk 1 tree without the root node It follows from Induction Hypothesis that the Bk 1 tree without the root node consists of k 1 binomial trees This plus the one Bk 1 tree adds up to k binomial trees of smaller orders Rubrics 10 points Getting base case 2 points Getting Induction Hypotheses 2 points Proving k th case 6 points 2 Given a sorted array A and a value x a Design an algorithm using heaps to find the k closest elements to x in A b Determine and explain the time complexity of your algorithm a A max heap can be used to maintain the k closest numbers to x First iterate over the elements in the array and calculate their absolute differences from x Pairs of absolute differences and their corresponding values are pushed into the max heap If the size of the max heap exceeds k the element with the maximum absolute difference is removed Finally the top k elements from the max heap are extracted and stored in a result vector b The time complexity is O nlog k where n is the size of the array and k is the number of elements to be returned Inserting an element into the max heap takes O log k time and removing the top element also takes O log k time Thus iterating through the array and maintaining the heap takes O nlog k Extracting the top k elements from the heap and adding them to the result vector takes O klog k Therefore the total time complexity is O nlog k klog k which simplifies to O nlog k 1 Rubrics 10 points a 5 points i 1 point using max heap ii 2 point calculating absolute difference and constructing the heap iii 1 point controlling for size of the heap iv 1 point correctly handling heaps of size greater than k b 5 points i 1 point considering insertion and deletion time complexities ii 1 point considering number of iterations iii 1 point considering time complexity of extracting values from heap iv 2 points deriving final time complexity 3 There are n ropes of lengths L1 L2 Ln Your task is to connect them into one rope The cost to connect two ropes is equal to sum of their lengths Design a greedy algorithm such that it minimizes the cost of connecting all the ropes No proof is required Algorithm Make a min heap containing the lengths of all the ropes While there is more than one element in the min heap extract the two smallest elements from the min heap add their length and put the added length back into the min heap Rubrics 10 points 3 points Uses greedy strategy correctly Always combining the 2 shortest ropes 3 points Describes the process of repeatedly selecting the two shortest ropes and combining them Or adding the combination back to the remaining ropes 2 points Clearly identifies the termination condition when only one rope remains indicating the end of the process Or more than one as the solution says 2 points Maintains a min heap for the ropes Note If a student s answer is different but seems correct it should be eligible for full credits Please contact the TAs if case of any questions 4 Given a graph G V E with non negative edge weights and the shortest path distances d s u from a source vertex s to all other vertices in G but without the shortest path tree devise a linear time algorithm to find a shortest path from s to a given vertex t No proof is required Reverse edges in the original graph This could be done in linear time for example using matrix transform For all vertices that are connected to a given vertex t find ones such that d s t d s u d u t Next set u as t and repeat this to find new u until s equals to u Nodes saved in the sequence are the shortest path from s to a given vertex t Rubrics 10 points 2 points Reverse edges in the original graph 3 points Find a vertex u satisfying d s t d s u d u t 2 points Iterative step setting u as the new t and repeating the process 2 point Ensuring that the iterative process will terminate correctly when s equals u 1 point Correct description of how the vertices are recorded for example using a sequence during the iterative process to reconstruct the shortest path 2 5 Given a graph G V E where a set of cities V is connected by a network of roads E Each road edge has a positive weight w u v between cities u and v There is a proposal to add a new road to the network The proposal suggests a list C of candidate pairs of cities between which the new road may be built Your task is to choose the road that would result in the maximum decrease in the driving distance between given city s and city t Design an efficient algorithm for solving this problem 8 points No proof is required Give the runtime complexity of your algorithm 2 points Algorithm Run Dijkstra algorithm from s to calculate shortest distances from s to all other cities Run Dijkstra algorithm from t to calculate shortest distance from t to all other cities For every candidate pair of cities u v the shortest path distance between s and t which covers road u v is min dist s u dist t v w u v dist s v dist t u w u v Choose the shortest distances If the selected distance is longer than original dist s t any candidate road cannot decrease distance between s and t Else choose the u v pair that produces shortest new distance In the case of tie choose one arbitrarily Complexity O V E log V C Rubrics 10 points 1 point running Dijkstra algorithm from s 1 point running Dijkstra from t 2 points calculating shortest path between s and t given two candidate cities u and v 4 points …