edited by
4,483 views
11 votes
11 votes

Consider the following function.

Function F(n, m:integer):integer;
begin
    if (n<=0) or (m<=0) then F:=1
    else
      F:F(n-1, m) + F(n, m-1);
end;

Use the recurrence relation  $\begin{pmatrix} n \\ k \end{pmatrix} = \begin{pmatrix} n-1 \\ k \end{pmatrix} + \begin{pmatrix} n \\ k-1 \end{pmatrix}$  to answer the following questions. Assume that $n, m$ are positive integers. Write only the answers without any explanation.

  1. What is the value of $F(n, 2)$?

  2. What is the value of $F(n, m)$?

  3. How many recursive calls are made to the function $F$, including the original call, when evaluating $F(n, m)$.

edited by

5 Answers

Best answer
8 votes
8 votes

$F(n,m)= F(n-1,m)+F(n,m-1)$

Let vertices represent $F(n,m)$ value.

According to rule, we get value of $F(n,m)$ by adding value of vertex left above of it and vertex right above of it.

When counting these, we observe a pattern. Hence to find say $F(4,2)$ we do $F(4,1)+F(3,2)=5+10=15.$

If $C(n,m)$ denotes number of recursive calls for $F(n,m)$ we have,

$C(n,m) = C(n-1,m) + C(n-1,m-1) +2$  

edited by
4 votes
4 votes
a) $\frac{n(n-1)}{2}$

b) $\frac{n(n-m+1)}{m!}$
4 votes
4 votes

I think this question needs some correction :

1. Recurrence relation is not matching with the function in the algorithm

2.Some base conditions are missing as n>=m.

Due to these mistakes, this question is a little bit ambiguous.

Correct algorithm:

int binomialCoeff(int n, int k)
{
    // Base Cases
    if (k > n)
        return 0;
    if (k == 0 || k == n)
        return 1;
 
    // Recurence
    return binomialCoeff(n-1, k - 1) + binomialCoeff(n - 1, k);
}

Let Z(n,m) denotes number of function call required then,

Z(n,m) = Z(n-1,m) + Z(n-1,m-1) +2    

If you want visualize it it will form a binary tree of maximum height= O(n)

 

So.rougly number of function calls will be O(2^n).

This algorithm can be modified by using dynamic programming which reduces it’s time complexity.

3 votes
3 votes

here is what i understood from the question.

hope you all understand :)

Related questions

21 votes
21 votes
1 answer
1
Kathleen asked Sep 29, 2014
4,792 views
Let $T(n)$ be the function defined by $T(1) =1, \: T(n) = 2T (\lfloor \frac{n}{2} \rfloor ) + \sqrt{n}$ for $n \geq 2$.Which of the following statements is true?$T(n) = O...
21 votes
21 votes
3 answers
3
Kathleen asked Sep 29, 2014
4,970 views
The correct matching for the following pairs is$$\begin{array}{ll|ll}\hline \text{A.} & \text{All pairs shortest path} & \text{1.} & \text{Greedy} \\\hline \text{B.} & \...