A dynamic programming algorithm for solving the Activity Selection problem from

Question

A dynamic programming algorithm for solving the Activity Selection problem from chapter 16 fills an n by n table c so that c[1,n] contains the maximal number of schedulable activities. Only the entries for which i <= j are filled. Assuming the table is oriented with row 1 at the top, for the algorithm to compute a value for entry c[i,j], it must access the i-1 entries to the left of and the j-1 entries below c[i,j].

a. In terms of i, j, and n, how many times is entry c[i,j] accessed? (Hint: Try determining the answer for a 4-by-4 table and then generalize.)

b. In terms of n what is the ?-notation for the total number of accesses over all entries?

Explanation / Answer

a.

For a nxn table:

c[i,j] is accessed for calculating for elements

(n-i-1) + (n-i-2) + ..... + 1
=>(n-i)*(n-j) - (1+2+3+....(n-i-1))
=>(n-i)*(n-j) - ((n-i-1)(n-i)/2)
=>(n-i)*((n-j) - (n-i-1)/2)
=>(n-i)*(n -2j +i + 1)/2

b.

Summation of i: 1-n and j: 1-n of (n-i)*(n -2j +i + 1)/2

=> Summation of i:1-n (Summation of j: 1-n of (n-i)*(n -2j +i + 1)/2 )

=> Summation of i:1-n (Summation of j: 1-n of (n-i)*(i*n)/2 )

=> (n-1)(n+1)(n*n)/12

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.