Question

urgent

L. Consider the following pseudocode for finding binomial coefficients: Binom(n, r) Input: integers n and r Output: n choose r if r-0 or r-n thern return 1 end else return Binom(n-1, r-1) Binom(n-1, r); end running time of this algorithm. Prove your bound for the upper bound. (5 points) Rewrite the above algorithm so that it is efficient. (You have 2 choices!) Analyze the worst case time of your new algorithm. (5 points) Find the edit distance between "SPOKE and "PARK". Backtrack to find one possible optimal alignment. Show all of your work. (10 points)

Answer 1

Answer 1.

Time Complexity of give program : O(2ⁿ)

Since , this is a recurrence relation

T(n,r) = T(n-1,r) + T (n-1,r-1) + O(1)

Now , at each step n doubles . Thus giving total time Complexity of O (2ⁿ)

Answer 2 . For finding binomial coefficients efficiently , we use dynamuc programming , as there are many repeating subproblems . For this we have 2 choices :

Choice 1: Simple Dynamic Programming

Time Complexity : O(n*r)

Space Complexity : O(n*r)

C++ Code :

#include<bits/stdc++.h>

// c++ code for finding binomial

using namespace std;

int minimum(int x, int y) // function to find min

{

return (x< y) ? x : y;  

}

//minimum function

int binomial(int n, int r)

{

int A[n+1] [r+1];  

for ( int x = 0; x <= n; x++)

{

for ( int y = 0; y <= minimum(x, r); y++)

{

if (y == 0 || y == x)

A[x] [y] = 1;

else

A[x][y] = A[x-1] [y-1]+ A[x-1][y];}

}

return A[n][r];

}

// main function

int main()

{

int n,r;

cin>>n>>r;

cout << binomial(n, r);

}

Time Complexity : O(n*r)

Space Complexity : O(n*r)

Choice 2: Space Optimised Dynamic Programming

Time Complexity : O(n*r)

Space Complexity : O(r)

C CODE :

#include<bits/stdc++.h>
// Code Space optimised
using namespace std;

int binomial(int n, int r)
{ int A[r+1];
//initalize array to 0
memset(A, 0, sizeof(A));

A[0] = 1;  
int x=0;
int y=0;
for ( x = 1; x <= n;x++)
{
for (y = min(x, r);y>0;y--)

A[y] = A[y] + A[y-1];

}

return A[y];

}

int main()

// Main function driver code

{

int n;

int r;

cin>>n>>r;

printf ("%d ", binomial(n,r) );

return 0;

}

Time Complexity : O(n*r)

Space Complexity : O(r)