Everything must be done in LaTex and please provide as much detail as possible.
SAN FRANCISCO STATE UNIVERSITY Computer Science Department CSC510 Analysis of Algorithms– Algorithm Challenge 3: Dynamic Programming Instructor: Jose Ortiz Full Name: Student ID: Assignment Instructions. Must read! Note: Failure to follow the following instructions in detail will impact your grade negatively. 1. This algorithm challenge is worth 9%, and will be graded using a grading point scale where the maximum possible grade is 9 points 2. Handwriting work or screenshots of your work are not allowed. In addition, all the pseudocode done in this algorithm challenge must be done using LaTeX. Students who fail to meet this policy won’t get credit for their work. Note that for pseudocode, I only want to see the compiled PDF psudocode, instead of the code to create the pseudocode. 3. Each section of this algorithm challenge is worth 2.25 points 4. Take into account that in this type of assignments, I am more interested in all the different approaches you take to solve the problem rather than on the final solution. 1 CSC510 Analysis of Algorithms Problem Statement You are an electrician contractor, and you just finished a very specialized job that used wires with a very specific gauge (amp capacity). Projects that need that type of wire are very rare. Therefore, you have decided to sell all the extra wire to get some profit from it. What is the maxi- mum profit you can get if you sell N(ft) of wire (sold per foot)? For example: given a list of prices (in dollars) P = [9, 8, 5, 3] per ft, where the (indexes + 1) of those prices represent the number of ft, find the maximum profit for selling 3 ft of wire. From the above data, we know that 1ft = $9, 2ft = $8, 3ft = $5, and 4ft = $3 Then, 3ft of wire can be sold in any of the following ways: • 3ft = $5 • 1ft + 2ft = $9 + $8 = $17 • 1ft + 1ft + 1ft = $9 + $9 + $9 = $27 Therefore you will get the maximum profit from 3ft of wire if you sell them in pieces of 1ft. Page 2 of 6 CSC510 Analysis of Algorithms Your work starts here 1. Given list of prices P = [p1, p2, p3, ..., pn] and a random number of ft where 0 < ft ≤ n, create the algorithm to solve the problem using the following two approaches (including an educated guess of their time complexities): (a) brute force (b) dynamic programming page 3 of 6 csc510 analysis of algorithms 2. write the pseudocode that represents your algorithm from problem (1.b). note that in this problem, i am asking for the compiled latex pseudocode (pdf format) instead of the latex code that creates this pseudocode page 4 of 6 csc510 analysis of algorithms 3. based on your pseudocode from part 2, state the complexity function and based on that func- tion compute the time complexity of the dynamic programming algorithm that you created. note that if you implemented a recursive algorithm, you must apply the substitution method to compute the time complexity of your algorithm, and then check it with the master the- orem. if you, however, implemented an iterative algorithm for this problem, then you must use a step counting approach to compute the time complexity. credit for this problem will be given only to the students that show all the work step by step including how to solve the summations or recurrences. incomplete or poor work won’t get credit page 5 of 6 csc510 analysis of algorithms 4. modify your algorithm from problem 1.b (dynamic programming) so now you must compute the maximum profit you can get if you sell all the wire. will this modification, in the dynamic programming algorithm, change the time complexity you got from part 3? explain in detail to get credit. page 6 of 6 ft="" ≤="" n,="" create="" the="" algorithm="" to="" solve="" the="" problem="" using="" the="" following="" two="" approaches="" (including="" an="" educated="" guess="" of="" their="" time="" complexities):="" (a)="" brute="" force="" (b)="" dynamic="" programming="" page="" 3="" of="" 6="" csc510="" analysis="" of="" algorithms="" 2.="" write="" the="" pseudocode="" that="" represents="" your="" algorithm="" from="" problem="" (1.b).="" note="" that="" in="" this="" problem,="" i="" am="" asking="" for="" the="" compiled="" latex="" pseudocode="" (pdf="" format)="" instead="" of="" the="" latex="" code="" that="" creates="" this="" pseudocode="" page="" 4="" of="" 6="" csc510="" analysis="" of="" algorithms="" 3.="" based="" on="" your="" pseudocode="" from="" part="" 2,="" state="" the="" complexity="" function="" and="" based="" on="" that="" func-="" tion="" compute="" the="" time="" complexity="" of="" the="" dynamic="" programming="" algorithm="" that="" you="" created.="" note="" that="" if="" you="" implemented="" a="" recursive="" algorithm,="" you="" must="" apply="" the="" substitution="" method="" to="" compute="" the="" time="" complexity="" of="" your="" algorithm,="" and="" then="" check="" it="" with="" the="" master="" the-="" orem.="" if="" you,="" however,="" implemented="" an="" iterative="" algorithm="" for="" this="" problem,="" then="" you="" must="" use="" a="" step="" counting="" approach="" to="" compute="" the="" time="" complexity.="" credit="" for="" this="" problem="" will="" be="" given="" only="" to="" the="" students="" that="" show="" all="" the="" work="" step="" by="" step="" including="" how="" to="" solve="" the="" summations="" or="" recurrences.="" incomplete="" or="" poor="" work="" won’t="" get="" credit="" page="" 5="" of="" 6="" csc510="" analysis="" of="" algorithms="" 4.="" modify="" your="" algorithm="" from="" problem="" 1.b="" (dynamic="" programming)="" so="" now="" you="" must="" compute="" the="" maximum="" profit="" you="" can="" get="" if="" you="" sell="" all="" the="" wire.="" will="" this="" modification,="" in="" the="" dynamic="" programming="" algorithm,="" change="" the="" time="" complexity="" you="" got="" from="" part="" 3?="" explain="" in="" detail="" to="" get="" credit.="" page="" 6="" of="">