CSCI 570 - Fall 2021 - HW 6 - SolutionGraded ProblemsFor the grade problems, you must provide the solution in the form ofpseudo-code and also give an analysis on the running time complexity.Problem 1[10 points] Suppose you have a rod of length N, and you want to cut up therod and sell the pieces in a way that maximizes the total amount of money youget. A piece of length i is worth pidollars. Devise a Dynamic Programmingalgorithm to determine the maximum amount of money you can get by cuttingthe rod strategically and selling the cut pieces.Solution: At each remaining length of the rod, we can choose to cut therod at any point, and obtain points for one of the cut pieces and recursivelycompute the maximum points we can get for the other piece. It is also possibleto recursively attempt to obtain the maximum value for both pieces after thecut, but that requires adding an extra check to see if the value obtained byselling a rod of this length is more than recursively cutting it up.The bottom-up pseudo-code to obtain the maximum amount of money is:Algorithm 1 Bottom-Up-Cut-Rod(p, n)Let r[0, ..., n] be a new arrayr[0] = 0for j = 1 to n doq = −∞for i = 1 to j doq = max(q, p[i] + r[j − i])end forend forreturn r[n]The time complexity of this algorithm is θ(n2) because of the double nestedfor loop.Rubric:• 5 points for a correct dynamic programming solution1• 3 points if the solution runs in θ(n2)• 2 points for providing analysis of runtime complexityProblem 2[10 points] Tommy and Bruiny are playing a turn-based game together. Thisgame involves N marbles placed in a row. The marbles are numbered 1 to Nfrom the left to the right. Marble i has a positive value mi. On each player’sturn, they can remove either the leftmost marble or the rightmost marble fromthe row and receive points equal to the sum of the remaining marbles’ values inthe row. The winner is the one with the higher score when there are no marblesleft to remove.Tommy always goes first in this game. Both players wish to maximize theirscore by the end of the game.Assuming that both players play optimally, devise a Dynamic Program-ming algorithm to return the difference in Tommy and Bruiny’s score once thegame has been played for any given input.Your algorithm must run in O(N2) time.Solution:We first calculate a prefix sum for the marbles array. This enables us to findthe sum of a continuous range of values in O(1) time.If we have an array like this: [5, 3, 1, 4, 2], then our prefix sum array would be[0, 5, 8, 9, 13, 15].Once we’ve done that, we can define OPT(i, j) as the maximum difference inscore achievable by the player whose turn it is to play, given that the marblesfrom index i to j (inclusive) remain.The pseudo-code for this algorithm, assuming 0-indexed arrays, is:Algorithm 2 Max-Difference-Scores(marbles)Let n be the length of the marbles arrayLet pref ix sum be the calculated prefix sum array for the array marbles[takes θ(n) time]Let OP T [[0, ..., 0], ..., [0, ..., 0]] be a new n∗n array, with values initialized to 0for i = n − 2 to 0 dofor j = i + 1 to n − 1 doscore if take i = pref ix sumj+1− prefix sumi+1− OP Ti+1,jscore if take j = pref ix sumj− prefix sumi− OP Ti,j−1OP Ti,j= max(score if take i, score if take j)end forend forreturn OP T0,n−12The time complexity of this algorithm is θ(n2) if a prefix sum array is cal-culated initially due to there being n ∗ n subproblems to calculate.Rubric:• 8 points for a correct dynamic programming solution• 2 points for providing analysis of runtime complexityProblem 3[10 points] The Trojan Band consisting of n band members hurries to lined upin a straight line to start a march. But since band members are not positionedby height the line is looking very messy. The band leader wants to pull out theminimum number of band members that will cause the line to be in a formation(the remaining band members will stay in the line in the same order as theywere before). The formation refers to an ordering of band members such thattheir heights satisfy r1< r2< ... < ri> ... > rn, where 1 ≤ i ≤ n.For example, if the heights (in inches) are given asR = (67, 65, 72, 75, 73, 70, 70, 68)the minimum number of band members to pull out to make a formation will be2, resulting in the following formation:(67, 72, 75, 73, 70, 68)Give an algorithm to find the minimum number of band members to pullout of the line.Note: you do not need to find the actual formation. You only need to findthe minimum number of band members to pull out of the line, but you need tofind this minimum number in O(n2) time.For this question, you must write your algorithm using pseudo-code.Solution: This problem performs a Longest − Increasing − Subsequenceoperation twice. Once from left to right and once again, but from right to left.Once we have the values for the longest subsequence we can make after we ”pullout” a few band members, we can iterate over the array and determine whatminimum number of pull-outs will cause our line of band members to satisfythe height order requirements.Let OP Tlef t(i) be maximum length of the line to the left of band member i(including i) which can be put in order of increasing height (by pulling out somemembers) Note: the problem is symmetric, so we can flip the array R and findthe same values from the other direction. Let’s call those values OP Tright(i).3The recurrence relations are:OP Tlef t(i) = max(OP Tlef t(i), OP Tlef t(j) + 1) such that ri> rj∀ 1 ≤ j < iOP Tright(i) = same once the array is flippedPseudo code:for i = 1 to n doOP Tlef t(i) = OP Tright(i) = 1 . only choose itselfend forfor i = 2 to n − 1 dofor j = 1 to i − 1 doif ri> rjthenOP Tlef t(i) = max(OP Tlef t(i), OP Tlef t(j) + 1)end ifend forend forfor i = 2 to n − 1 dofor j = 1 to i − 1 doif rn−i+1> rn−j+1thenOP Tright(i) = max(OP Tright(i), OP Tright(j) + 1)end ifend forend forresult = −∞for i = 1 to n doresult = min(result, n − (OP Tlef t(i) + OP Tright(i) + 1))end forreturn resultThe runtime of this algorithm is dominated by the nested for loops used tocalculate the LIS both ways. This takes θ(n2) each time. Therefore, the timecomplexity of the solution is θ(n2).Rubric:• 8 points for a correct dynamic programming solution in pseudo-code• 2 points for providing analysis of runtime complexityProblem 4[15 points] You’ve started a hobby of retail investing into stocks using a mobileapp, RogerGood. You magically gained the power to see N days