1 Given a graph G V E whose edge weights are integers in the range 0 W where W is a relatively small integer number compare to V and E we could run Dijkstra s algorithm to nd the shortest distances from the start vertex to all other vertices Design a new algorithm that will run in linear time O V E and therefore outperform Dijkstra s algorithm Explain the time complexity No proof is needed for the correctness of your algorithm Extend every edge by its weight For example if an edge ei weighs wi then insert vertices on this edge until each sub edge has a unit length 1 weight The whole graph will be an unweighted graph We can perform BFS from the source to nd the shortest paths 2 Solve the following recurrences by giving tight notation bounds in terms of n for su ciently large n Assume that T represents the running time of an algorithm i e T n is positive and non decreasing and for small constants c independent of n T c is also constant We observe that nlogb a nlog5 9 and f n n log n O nlog5 9 cid 15 for any 0 cid 15 log5 9 1 Thus invoking the Master Theorem We have nlogb a nlog3 2024 3 5 Thus from the Master Theorem 2024 n3 465 O n3 5 and f n n 2024 n3 5 cid 15 for any 0 cid 15 a b c Homework 3 CSCI570 Fall 2024 Due Oct 6 2024 cid 16 n cid 17 5 T n 9T n log n T n nlog5 9 n1 365 T n 2024T cid 16 n cid 17 3 n 2024 T n n 2024 T n 2T n log2 n cid 16 m cid 17 2 S m 2S m 1 We use a change of variables by setting n 2m De ne S m T 2m and we obtain the recurrence Since S is a positive function due to the monotonic property of the map x cid 55 2x and the positive property of T all conditions for applying the generalized Master Theorem are satis ed Using the generalized version of the Master Theorem we get Reverting to the original variable n we get S m m log m T n T 2m S m m log m log2 n log log2 n for su ciently large n We observe that f n n2 log n and nlogb a nlog3 9 n2 Applying the generalized Master Theorem we get d e cid 16 n cid 17 3 T n 9T n2 log n T n n2 log2 n cid 16 n cid 17 2 T n 10T 2n T n 2n We have nlogb a nlog2 10 and f n 2n nlog2 10 cid 15 for any cid 15 0 From the Master Theorem 3 The recurrence T n 7T cid 0 n algorithm ALG has a running time of T cid 48 n aT cid 48 cid 0 n cid 1 n2 describes the running time of an algorithm ALG A competing cid 1 n2 log n What is the largest value of a such 2 4 that ALG is asymptotically no slower than ALG You need to a Analyze T n using the Master Theorem 4pts b Analyze T cid 48 n using the Master Theorem Analyze and give the largest possible value of a 6pts We shall use the Master Theorem to evaluate the running time of the algorithms a For T n setting 0 cid 15 log2 7 2 0 81 we have n2 O cid 0 nlog2 7 cid 15 cid 1 Hence if log4 a 2 then setting 0 log4 a 2 implies n2 log n O cid 0 nlog4 a cid 1 Hence b For T cid 48 n To have T cid 48 n asymptotically faster than T n we need T cid 48 n O T n which implies Thus if log4 a 2 we get log4 a log2 7 a 49 a 16 49 Therefore the largest possible value of a such that ALG is asymptotically faster than ALG is a 49 T n cid 0 nlog2 7 cid 1 T cid 48 n cid 0 nlog4 a cid 1 nlog4 a O cid 0 nlog2 7 cid 1 2 4 We know that binary search on a sorted array of size n takes log n time Design a similar divide and conquer algorithm for searching in a sorted singly linked list of size n Discuss its worst case runtime complexity A sorted singly linked list doesn t provide constant time access to its middle element so getting the middle element takes O n time Because of this we can t achieve O log n time complexity as in binary search on arrays where we can access the middle element in constant time However we can still design a divide and conquer algorithm with a time complexity of O n by traversing the linked list to nd the middle element The recurrence T n T n 2 O n which can be easily solved by the Master Theorem T n n 5 Given an array of N distinct integers nd a subarray L R such that 1 All numbers in the subarray are between the two endpoints i e the subarray contains all integers i where L i R 2 The subarray contains the maximum number of integers that satisfy this condition Formally for any index i in the subarray the condition min subarray nums i max subarray holds true where min subarray and max subarray refer to the minimum and maximum values of the subarray respectively Example 1 For the array 8 1 3 4 7 the answer is 1 7 Example 2 For the array 2 6 5 4 9 8 the answer is 2 9 You need to a Describe a D C algorithm that nds the subarray Use natural language or pseudo code 4pts b Explain why your algorithm nds the subarray 2pts c Analyze the time complexity of your algorithm using the Master Theorem 4pts You don t need to consider situations like such subarray doesn t exist We solve this problem using a divide and conquer approach similar to the maximum subarray problem The idea is to divide the array into two halves solve each half recursively and then consider the optimal interval that might span the midpoint Divide and Conquer Approach If the array has only one element return it as the trivial solution Otherwise divide the array into two halves Recursively solve the left and right halves Find the optimal subarray that spans the midpoint by interating from every index i of the left subarray and scanning to the right tracking the minimum and maximum seen so far and nding all the possible js in the right subarray And nd the maximum value of j i which might not exist Return the subarray that contains the most numbers Recursive Function and Complexity Let T n be the time complexity for an array of size n Dividing takes O 1 scanning and merging the …