SAN FRANCISCO STATE UNIVERSITY

Computer Science Department

CSC510 Analysis of Algorithms–Algorithm Challenge 3: Dynamic Programming

Instructor: Jose Ortiz

Due on Tuesday 04/12/2021 at 11:59 pm

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 100 points. For instance, if your grade in this assignment is 85/100, then this is equivalent to 0.85*9%=7.65% of 9%

2. Don’t forget to include your student id and full name. Otherwise, a penalization of 10 points on the final grade of this algorithm challenge will be applied.

3. In this algorithm challenge, students are not allowed to write code; only pseudocode will be allowed. Writing code instead of pseudocode in this assignment will incur in a penalization of 20 points.

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(f t) 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.

Your work starts here

1. (50 points) 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

2. (10 points) Write the pseudocode that represents your algorithm used in your dynamic pro-gramming approach. Note pseudocoding is not the same as coding. In this challenge you are not required to code.

3. (20 points) Based on your pseudocode from part 2, state the complexity function and based on that function compute the time complexity of the dynamic programming algorithm that you created. Note that if you created a recursive algorithm, you must apply the substitution method to compute the time complexity of your algorithm, and then check it with the Master Theorem. If you, however, created 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 low quality work won’t get credit

4. (20 points) Modify your algorithm from part 1 (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.