TIFR CSE 2025 | Part B | Question: 9

Question

Consider the following pseudocode. The program should take as input $n$, and when it ends, the element $A[i]$ of the vector $A$ should contain the binomial coefficient $\binom{n}{i}$ (with the index of $A$ starting from 0). In order to do so, what should replace the ___________ in the pseudocode?

procedure BINOMIALCOEFFICIENT
  input n
  for i ←  0 to n do
      A[i] ← 0
  end for
  A[0] ← 1
  for i ← 1 to n do
      B ← A
      for j ← 1 to n do
          A[j] ← ___________ 
     end for
   end for
end procedure

• A. $B(j-1)+B(j)$
• B. $A(j-1)+B(j-1)$
• C. $\dfrac{B(j)+B(n-j)}{2}$
• D. $\dfrac{B(j-1) \times B(j)}{2}$
• E. $\dfrac{A(j-1)+B(j-1)}{2}$

Comments

 

 The Intuitive Algorithm

 

The core logic relies on the fundamental recurrence relation for binomial coefficients:

$$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$$

In terms of the pseudocode variables:

• $\binom{n}{k}$ is the value we want to store in $A[j]$.

• $\binom{n-1}{k-1}$ is the value from the previous row at the previous index: $B[j-1]$.

• $\binom{n-1}{k}$ is the value from the previous row at the current index: $B[j]$.

Therefore, to compute the $i$-th row from the $(i-1)$-th row, the update must be:

$A[j] \leftarrow B[j-1] + B[j]$

This matches Option A.

---

 

Answer 1

In the beginning, $A$ is initialized as: $A = [1, 0, 0, ..., 0]$
 

The outer loop is running from $i = 1$ to $n$, where each iteration is basically calculating the coefficients for a new value of $n = i$
At the beginning of each outer loop iteration, the current array $A$ is copied to $B$

This means that $B[j]$ holds $\binom{i-1}{j}$ — the binomial coefficient values from the previous iteration and we are using these values for next.

We know that :
$$
\binom{i}{j} = \binom{i-1}{j-1} + \binom{i-1}{j}
$$
$B[j-1]$ is just $\binom{i-1}{j-1}$ 
and $B[j]$  is $\binom{i-1}{j}$ 

So, the inner loop is running from $j = 1$ to $n$, and updating $A[j]$ as:
$$
\boxed{A[j] = B[j - 1] + B[j]}
$$
 

---

Try for $n = 4$. 

Initially:  
$A = [1, 0, 0, 0, 0]$  
 

After $i = 1$:  
$A = [1, 1, 0, 0, 0]$  
$A$ stores $\binom{1}{j}$

After $i = 2$:  
$A = [1, 2, 1, 0, 0]$  
$A$ stores $\binom{2}{j}$

After $i = 3$:  
$A = [1, 3, 3, 1, 0]$  
$A$ stores $\binom{3}{j}$

After $i = 4$:  
$A = [1, 4, 6, 4, 1]$  
$A$ stores $\binom{4}{j}$