The entries a ij of matrix A are computed according to the formula: a ij = 1 for

Question

The entries aij of matrix A are computed according to the formula:

                aij = 1 for i = 1, j > 1,

                aij = 0 for i > 1, j = 1,

  aij = (ai-1, j + ai, j-1)/2 for i > 1, j > 1

(a) Estimate the number of operations + that are necessary to compute aij. Apply dynamic programming approach similar to the treatment of Pascal’s triangle.

(b) What are the minimal space resources required for your computation. i.e. how many computed values do you need to keep in order to compute aij?

Explanation / Answer

a) If we have m*n matrix then according to formula 1st row and 1st column is filled with ones. So we are left with (m-1) rows and (n-1) columns.It means we have (m-1)*(n-1) elements to be filled. For each element , we need to perform one + operation. So total no. of operations required =(m-1)*(n-1)a

b)If a[i][j] is the lower right most element of the matrix ,then to compute it , I need 2 values just above or below it.But to compute them ,I need another 2 values. In this way ,I need to store all the elements just above it or on left side of it.So we need around m*(n-1) = O(mn) space complexity

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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