Problem 1 (25 points) This problem will test your understanding of dynamic programming by having you run

through the algorithm for interval scheduling that we saw in class. Consider the following input

for the interval scheduling problem: ( picture of problen is in image )

Fill out the dynamic programming table with the values of OPT() for = 0, 1, . . . , 6. Label each

value of OPT() with whether or not the optimal schedule of length contains interval or not.

Write the optimal schedule and its value.

Problem 1 (25 points) This problem will test your understanding of dynamic programming by having you run through the algorithm for interval scheduling that we saw in class. Consider the following input for the interval scheduling problem: 1v1=20 p(1)=0 2 v2=18 p(2)=1 3 v3=70 p(3)=0 4 v4=50 p(4)=2 5 p(5)=1 6 p(6)=4 Fill out the dynamic programming table with the values of OPT(i) for i=0,1,,6. Label each value of OPT (i) with whether or not the optimal schedule of length i contains interval i or not. Write the optimal schedule and its value