CSCI 570 Homework 3Due Sunday Mar. 08 (by 23:30)For all divide-and-conquer algorithms follow these steps:1. Describe the steps of your algorithm in plain English.2. Write a recurrence equation for the runtime complexity.3. Solve the equation by the master theorem.For all dynamic programming algorithms follow these steps:1. Define (in plain English) subproblems to be solved.2. Write the recurrence relation for subproblems.3. Write pseudo-code to compute the optimal value4. Compute its runtimecomplexity in terms of the input size.11. Suppose we define a new kind of directed graph in which positive weights areassigned to the vertices but not to the edges. If the length of a path is definedby the total weight of all nodes on the path, describe an algorithm that findsthe shortest path between two given points A and B within this graph.Solution:We have to reduce a vertex weighted graph G into an edge weighted graph G1.Create a new graph G1 as follows. Split each vertex v in G into two verticesvin and vout, with an edge weight between them equals to the vertex weightin G1. And the original edges from G have weights as 0 in G1. Edges comingto v in G will come to vin in G1. Edges leaving v in G will leave vout in G1.Run Dijkstra’s algorithm. In the shortest path tree T1 for G1, an edge betweenvin and vout means that vertex v is in the shortest path tree T for G. Collapseall such edges (vin, vout) in T1 by merging vin and vout. This will create theshortest path tree T.Rubric: (10 points)• (10 points) The algorithm is stated clearly. And the algorithm is correct.2. For each of the following recurrences, give an expression for the runtime T (n)if the recurrence can be solved with the Master Theorem. Otherwise, indicatethat the Master Theorem does not apply.• T(n) = 3T(n/2) + n2• T(n) = 4T(n/2) + n2• T(n) = T(n/2) + 2n• T(n) = 2nT (n/2) + nn• T(n) = 16T(n/4) + n• T(n) = 2T(n/2) + nlogn• T(n) = 2T(n/4) + n0.51• T(n) = 0.5T(n/2) + 1/n• T(n) = 16T(n/4) + n!• T(n) = 10T(n/3) + n2Solution:• T(n) = 3T(n/2) + n2— case 3: T (n) = Θ(n2)2• T(n) = 4T(n/2) + n2— case 2: T (n) = Θ(n2logn)• T(n) = T(n/2) + 2n— case 3: T (n) = Θ(2n)• T(n) = 2nT (n/2) + nn— Does not apply, a is not constant• T(n) = 16T(n/4) + n — case 1: T (n) = Θ(n2)• T(n) = 2T(n/2) + nlogn — case 2: T (n) = Θ(nlog2n)• T(n) = 2T(n/4) + n0.51— case 3: T (n) = Θ(n0.51)• T(n) = 0.5T(n/2) + 1/n — Does not apply (a < 1)• T(n) = 16T(n/4) + n!. — case 3: T (n) = Θ(n!)• T(n) = 10T(n/3) + n2. — case 1: T (n) = Θ(nlog310)Rubric: (10 points)• (10 points) 1 point for each item. One for getting the case right and onefor the runtime/justification of case3. Suppose that we are given a sorted array of distinct integers A[1, ..., n] and wewant to decide whether there is an index i for which A[i] = i. Describe anefficient divide-and-conquer algorithm that solves this problem and explain thetime complexity.Solution:If the array has just one integer, then we check whether A[1] = 1 with onecomparison. Otherwise divide the list into two parts, the first half and thesecond half, as equally as possible. Consider the largest element A[m] of theleft half. We compare A[m] with m. If A[m] = m, the answer is yes and weare done. If A[m] > m, then we can throw away the right half and continuerecursively in the left half. Indeed, then for every integer k ≥ 0 using the factthat the integers are distinct and sorted, A[m + k] ≥ A[m] + k > m + k. IfA[m] < m, then we can throw away the left half and continue recursively in theright half. Indeed, then for every integer k ≥ 0 using the fact that the integersare distinct and sorted A[m − k] ≤ A[m] − k < m − k. Thus for the number ofcomparisons we get the following recursion, T (n) = T (n/2)+O(1), T (1) = O(1).According to Master Theorem, the time complexity is Θ(log n).3Rubric: (15 points)• (10 points) The algorithm is stated clearly.– 10 points if the time complexity of the algorithm is equal or less thanΘ(log n). And it is using divide-and-conquer algorithm.– 5 points if the time complexity of the algorithm is is larger thanΘ(log n). And it is using divide-and-conquer algorithm.– 0 points if the algorithm is not correct or the algorithm is not usingdivide-and-conquer.• (3 points) The recurrence equation for run time complexity is correct.• (2 points) Solving the equation by master theorem and the time complexityis Θ(log n).4. We know that binary search on a sorted array of size n takes O(log n) time.Design a similar divide-and-conquer algorithm for searching in a sorted singlylinked list of size n. Describe the steps of your algorithm in plain English.Write a recurrence equation for the runtime complexity. Solve the equation bythe master theorem.Solution:If the array has just one integer, then we easily find this value. Otherwise firstlywe find the middle element of the list, this can be done in O(n). And we splitthe list into left list and right list. Compare this middle element with the searchelement. If they are equal and we are done. If the middle element is larger thanthe search element, we throw away the right half list and continue recursivelyon the left sublist. Otherwise we continue recursively on the left sublist. Wehave T (n) = T (n/2) + O(n), T (n) = Θ(n) according to Master Theorem.Rubric: (15 points)• (10 points) The algorithm is stated clearly.– 10 points if the algorithm is using divide-and-conquer algorithm andit is correct.– 0 points if the algorithm is not correct or the algorithm is not usingdivide-and-conquer.• (3 points) The recurrence equation for run time complexity is correct.• (2 points) Solving the equation by master theorem and the time complexityis Θ(n).45. Given n balloons, indexed from 0 to n − 1. Each balloon is painted with a num-ber on it represented by array nums. You are asked to burst all the balloons. Ifthe you burst balloon i you will get nums[i − 1] × nums[i] × nums[i + 1] coins.Here left and right are adjacent indices of i. After the burst, the left and rightthen becomes adjacent. You may assume nums[−1] = nums[n] = 1 and theyare not real therefore you cannot burst them. Design a dynamic programmingalgorithm to find the maximum coins you can collect by bursting the balloonswisely. Analyze the running time of your algorithm.Example. If you have the nums = [3, 1, 5, 8]. The optimal solution wouldbe 167, where you burst balloons in the order of 1, 5, 3 and 8. The