Session 8

Implementation of Binomial Coefficient Algorithm

This session compares two ways of computing binomial coefficients. The divide-and-conquer solution follows the mathematical recurrence directly, while the dynamic programming solution stores repeated subproblem results and is much faster for larger inputs.

Objectives

Implement binomial coefficient using divide and conquer.
Implement binomial coefficient using dynamic programming.
Compare both approaches for small and large values of n and k.

Concept

The binomial coefficient C(n, k) counts the number of ways to choose k items from n items.

It also follows Pascal's recurrence:

		C(n, k) = C(n-1, k-1) + C(n-1, k)
C(n, 0) = C(n, n) = 1

Divide and Conquer Approach

The recursive approach directly follows Pascal's recurrence. It is simple, but it recomputes many subproblems.

Metric	Value
Time complexity	Exponential without memoization
Space complexity	`O(n)` recursion depth

Dynamic Programming Approach

The DP approach stores intermediate values in a table and avoids repeated computation.

Metric	Value
Time complexity	`O(nk)`
Space complexity	`O(nk)` or `O(k)` when optimized

Question 1

Problem Statement

Implement a binomial coefficient problem using divide and conquer technique.

Explanation

The binomial coefficient, denoted as $(\binom{n}{k})$ or $C (n, k)$ , represents the number of ways to choose $k$ elements from a set of $n$ elements without regard to order.To implement this using the Divide and Conquer technique, we break the larger problem into smaller subproblems using Pascal's Identity.

To implement this using the Divide and Conquer technique, we break the larger problem into smaller subproblems using Pascal's Identity.

Mathematical Formulation

Pascal's Identity states that:

(\binom{n}{k}) = (\binom{n - 1}{k - 1}) + (\binom{n - 1}{k})

Base Cases:

If $k = 0$ , there is exactly $1$ way to choose $0$ items: $(\binom{n}{0}) = 1$
If $k = n$ , there is exactly $1$ way to choose all $n$ items: $(\binom{n}{n}) = 1$
If $k > n$ , it's impossible to choose more items than available: $(\binom{n}{k}) = 0$

By using this recurrence relation, we divide the problem of computing $(\binom{n}{k})$ into two smaller subproblems: computing $(\binom{n - 1}{k - 1})$ and $(\binom{n - 1}{k})$ , and then conquer them by adding their results.

Implementation

Python

binomial-d-c-algo.py

		# Binomial Coefficient using Divide & Conquer
class BinomialDnC:
    def __init__(self):
        self.call_count = 0  # Tracks recursive calls for analysis
 
    def compute(self, n, k):
        """
        Divides problem using Pascal's Identity:
        C(n,k) = C(n-1, k-1) + C(n-1, k)
        """
        self.call_count += 1
 
        # Base Cases (Conquer step for trivial problems)
        if k == 0 or k == n:
            return 1
        if k > n or k < 0:
            return 0
 
        # Divide: Split into two subproblems
        left = self.compute(n - 1, k - 1)
        right = self.compute(n - 1, k)
 
        # Combine: Add results of subproblems
        return left + right
 
 
def main():
    solver = BinomialDnC()
    n, k = 5, 2
 
    print(f"Computing C({n}, {k}) using Divide & Conquer...\n")
    result = solver.compute(n, k)
 
    print(f"✅ Result: C({n}, {k}) = {result}")
    print(f"📊 Total Recursive Calls: {solver.call_count}")
    print(
        "📈 Note: Pure D&C has overlapping subproblems. For n=5,k=2, it takes 19 calls."
    )
    print("   Optimal approach: Add memoization → O(nk) time (Dynamic Programming).")
 
 
if __name__ == "__main__":
    main()

C Language

binomial-d-c-algo.c

		// Binomial Coefficient using Divide & Conquer
 
#include <stdio.h>
 
// Global counter to track recursive calls for lab analysis
static int call_count = 0;
 
/**
 * Computes C(n,k) using Pascal's Identity:
 * C(n,k) = C(n-1, k-1) + C(n-1, k)
 */
long long binomialCoeff(int n, int k) {
    call_count++;
 
    // Base Cases: Trivial subproblems
    if (k == 0 || k == n) return 1;
    if (k > n || k < 0) return 0;
 
    // Divide & Conquer Step
    // Divide: Create two subproblems
    // Conquer: Recursively solve them
    // Combine: Sum the results
    return binomialCoeff(n - 1, k - 1) + binomialCoeff(n - 1, k);
}
 
int main() {
    int n = 5, k = 2;
 
    printf("Computing C(%d, %d) using Divide & Conquer...\n\n", n, k);
 
    long long result = binomialCoeff(n, k);
 
    printf("✅ Result: C(%d, %d) = %lld\n", n, k, result);
    printf(" Total Recursive Calls: %d\n", call_count);
    printf("📈 Complexity Note: Overlapping subproblems cause O(2^n) calls.\n");
    printf("   Use memoization (DP) to reduce to O(nk) time.\n");
 
    return 0;
}

Rust

binomial-d-c-algo.rs

		// Binomial Coefficient using Divide & Conquer
 
struct BinomialDnC {
    call_count: u32,
}
 
impl BinomialDnC {
    fn new() -> Self {
        BinomialDnC { call_count: 0 }
    }
 
    fn compute(&mut self, n: i32, k: i32) -> i64 {
        self.call_count += 1;
 
        // Base Cases: Directly solvable subproblems
        if k == 0 || k == n {
            return 1;
        }
        if k > n || k < 0 {
            return 0;
        }
 
        // Divide: Split into C(n-1, k-1) and C(n-1, k)
        // Conquer: Recursive resolution
        // Combine: Addition of subproblem results
        self.compute(n - 1, k - 1) + self.compute(n - 1, k)
    }
}
 
fn main() {
    let mut solver = BinomialDnC::new();
    let (n, k) = (5, 2);
 
    println!("Computing C({}, {}) using Divide & Conquer...\n", n, k);
 
    let result = solver.compute(n, k);
 
    println!("✅ Result: C({}, {}) = {}", n, k, result);
    println!("📊 Total Recursive Calls: {}", solver.call_count);
    println!("📈 Complexity Note: Overlapping subproblems cause O(2^n) calls.");
    println!("   Use memoization (DP) to reduce to O(nk) time.");
}

Question 2

Problem Statement

Implement a binomial coefficient problem using dynamic programming technique.

Explanation

To optimize the computation of the binomial coefficient $(\binom{n}{k})$ , we transition from the Divide and Conquer approach to Dynamic Programming (DP).As noted previously, the recursive formula $(\binom{n}{k}) = (\binom{n - 1}{k - 1}) + (\binom{n - 1}{k})$ generates heavily overlapping subproblems. Dynamic programming solves each subproblem exactly once and stores the result in a table, completely eliminating redundant calculations.

The DP Strategy

We can implement this using a Bottom-Up (Tabulation) approach. We construct a 2D table dp of size $(n + 1) \times (k + 1)$ , where the entry dp[i][j] will store the value of $(\binom{i}{j})$ .

Mathematical Dependencies:

Base Cases: For any row $i$ , dp[i][0] = 1 (choosing 0 items) and dp[i][i] = 1 (choosing all items).
Transitions: For all other entries, dp[i][j] = dp[i-1][j-1] + dp[i-1][j].

This structure directly mirrors how Pascal's Triangle is constructed row by row.

Implementation

Python

binomial-d-p-algo.py

		# Binomial Coefficient using Dynamic Programming (Bottom-Up Tabulation)
 
 
def binomial_dp(n, k, print_table=False):
    """
    Computes C(n,k) using DP tabulation.
    Fills a 2D table iteratively to avoid recomputation.
    """
    # Handle invalid inputs
    if k < 0 or k > n:
        return 0
    if k == 0 or k == n:
        return 1
 
    # DP table initialization: (n+1) rows, (k+1) columns
    dp = [[0] * (k + 1) for _ in range(n + 1)]
 
    # Fill table using Pascal's recurrence
    for i in range(n + 1):
        # Base case: C(i, 0) = 1
        dp[i][0] = 1
        for j in range(1, min(i, k) + 1):
            # DP Transition: C(i,j) = C(i-1,j-1) + C(i-1,j)
            dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
 
    # Optional: Print DP table for lab verification
    if print_table:
        print(f"\n{'=' * 40}")
        print(f"DP TABLE CONSTRUCTION (n={n}, k={k})")
        print(f"{'=' * 40}")
        print(f"{'i\j':<4}", end="")
        for j in range(k + 1):
            print(f"j={j:<3}", end="")
        print()
        print("-" * 40)
        for i in range(n + 1):
            print(f"i={i:<2}", end="")
            for j in range(k + 1):
                print(f"{dp[i][j]:<6}", end="")
            print()
        print(f"{'=' * 40}\n")
 
    return dp[n][k]
 
 
def main():
    n, k = 5, 2
    print(f"Computing C({n}, {k}) using Dynamic Programming...\n")
    result = binomial_dp(n, k, print_table=True)
    print(f"Result: C({n}, {k}) = {result}")
    print("DP Advantage: Each subproblem computed exactly once.")
    print("   Time Complexity: O(n×k) | Space Complexity: O(n×k)")
 
 
if __name__ == "__main__":
    main()

C Language

binomial-d-p-algo.c

		// Binomial Coefficient using Dynamic Programming (Bottom-Up Tabulation)
 
#include <stdio.h>
#include <stdlib.h>
 
long long binomialDP(int n, int k) {
    // Handle edge cases
    if (k < 0 || k > n) return 0;
    if (k == 0 || k == n) return 1;
 
    // Allocate DP table: (n+1) x (k+1)
    long long dp[n + 1][k + 1];
 
    // Fill table iteratively
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            // Base cases: C(i,0) = 1, C(i,i) = 1
            if (j == 0 || j == i) {
                dp[i][j] = 1;
            }
            // Invalid state: j > i
            else if (j > i) {
                dp[i][j] = 0;
            }
            // DP Transition: C(i,j) = C(i-1,j-1) + C(i-1,j)
            else {
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
            }
        }
    }
 
    // Result stored at dp[n][k]
    return dp[n][k];
}
 
int main() {
    int n = 5, k = 2;
    printf("Computing C(%d, %d) using Dynamic Programming...\n\n", n, k);
 
    long long result = binomialDP(n, k);
 
    printf("✅ Result: C(%d, %d) = %lld\n", n, k, result);
    printf("📊 DP Properties Verified:\n");
    printf("   - Optimal Substructure: C(n,k) built from C(n-1,k-1) & C(n-1,k)\n");
    printf("   - Overlapping Subproblems: Each state computed exactly once\n");
    printf("   - Time: O(n×k) | Space: O(n×k)\n");
 
    return 0;
}

Rust

binomial-d-p-algo.rs

		// Binomial Coefficient using Dynamic Programming (Bottom-Up Tabulation)
 
fn binomial_dp(n: usize, k: usize) -> i64 {
    if k > n {
        return 0;
    }
 
    // DP table: (n+1) rows, (k+1) columns
    let mut dp = vec![vec![0i64; k + 1]; n + 1];
 
    // Fill table using iterative DP transition
    for i in 0..=n {
        for j in 0..=k.min(i) {
            if j == 0 || j == i {
                dp[i][j] = 1; // Base cases
            } else {
                // DP Transition: C(i,j) = C(i-1,j-1) + C(i-1,j)
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
            }
        }
    }
 
    dp[n][k]
}
 
fn main() {
    let (n, k) = (5, 2);
    println!("Computing C({}, {}) using Dynamic Programming...\n", n, k);
 
    let result = binomial_dp(n, k);
 
    println!("✅ Result: C({}, {}) = {}", n, k, result);
    println!(" DP Advantage: Eliminates exponential recomputation.");
    println!("   Each of the (n+1)*(k+1) states computed exactly once.");
    println!("   Time: O(n×k) | Space: O(n×k)");
}

Question 3

Problem Statement

Study the performance of both implementations using five problem instances in terms of efficiency for large and small values of n and k.

Answer

To evaluate the empirical efficiency of the Divide and Conquer (Recursive) and Dynamic Programming (Tabulation) implementations, we analyze their performance metrics across five distinct problem instances. These instances are systematically chosen to reflect combinations of small and large values for $n$ and $k$ .

Experimental Setup & Test Cases

We evaluate the algorithms using the following five instances:

Instance 1 (Small $n$ , Small $k$ ): $(\binom{5}{2})$ — Baseline verification.
Instance 2 (Medium $n$ , Small $k$ ): $(\binom{25}{3})$ — Evaluates performance when $k$ remains small but $n$ grows.
Instance 3 (Medium $n$ , Balanced $k$ ): $(\binom{26}{13})$ — Represents the worst-case scenario for a given $n$ because the binomial coefficient peaks at $k = ⌊ n / 2 ⌋$ .
Instance 4 (Large $n$ , Boundary $k$ ): $(\binom{100}{1})$ — Evaluates behavior near the edge boundaries.
Instance 5 (Large $n$ , Large $k$ ): $(\binom{100}{50})$ — The absolute worst-case threshold for evaluating large scaling structures.

Performance Breakdown by Scenario

Scenario A: Small $n$ and Small $k$ (Instance 1)

Divide & Conquer: Performs acceptably well. With a tiny search space, the recursion tree is shallow ( $n = 5$ ), and the redundant overlapping calculations are negligible to modern CPUs.
Dynamic Programming: Allocates a small tracking grid and fills it linearly. Both implementations execute in microseconds.

Scenario B: Medium $n$ and Balanced $k$ (Instance 3)

Divide & Conquer: Performance degrades exponentially. For $(\binom{26}{13})$ , the recursion tree branches out into over 20 million function calls to compute a final answer of just 10.4 million. The CPU wastes immense time re-evaluating the same sub-problems over and over.
Dynamic Programming: Highly Efficient. The DP loop fills a small, predictable table. It computes the solution in exactly 260 additions, bypassing millions of redundant operations completely.

Scenario C: Large $n$ and Boundary $k$ (Instance 4)

Divide & Conquer: Performs efficiently only because of the early exit condition ( $k = 1$ ). The execution paths short-circuit quickly back up the call stack, limiting the total recursive operations to 199.
Dynamic Programming: Keeps pace uniformly at 101 table updates.

Scenario D: Large $n$ and Large $k$ (Instance 5)

Divide & Conquer: Total System Failure. The total operation count reaches $\approx 2 \times 10^{29}$ . If a modern computer could process one trillion operations per second, it would still take over 6 billion years to complete this single computation. The program will crash due to a stack overflow or freeze indefinitely.
Dynamic Programming: Flawless. Even with an extremely massive resulting number, the tabulation method completes the task in exactly 3,825 matrix step updates, rendering an instantaneous output.

Conclusion

Divide and Conquer Evaluation: This approach is structurally unsuited for large entries. Its time complexity is fundamentally tied to the size of the final output ( $2 \times (\binom{n}{k}) - 1$ ). As the solution value grows exponentially, the execution time mirrors that explosive growth. It is only practical for academic visualization or instances where $n \leq 20$ .
Dynamic Programming Evaluation: This approach remains completely immune to structural variations in the output value size. Its time complexity scales strictly based on the matrix area bounds ( $𝒪 (n \times k)$ ). DP converts an unmanageable exponential time problem into a predictable, highly efficient polynomial time calculation.

Session 7

Minimum Cost Spanning Tree

Session 9

Floyd and Warshall's Algorithm for All Pair Shortest Path Algorithms

Session 8

Objectives

Concept

Divide and Conquer Approach

Dynamic Programming Approach

Question 1

Problem Statement

Explanation

Mathematical Formulation

Base Cases:

Implementation

Python

C Language

Rust

Question 2

Problem Statement

Explanation

The DP Strategy

Mathematical Dependencies:

Implementation

Python

C Language

Rust

Question 3

Problem Statement

Answer

Experimental Setup & Test Cases

Performance Breakdown by Scenario

Scenario A: Small n and Small k (Instance 1)

Scenario B: Medium n and Balanced k (Instance 3)

Scenario C: Large n and Boundary k (Instance 4)

Scenario D: Large n and Large k (Instance 5)

Conclusion

Scenario A: Small $n$ and Small $k$ (Instance 1)

Scenario B: Medium $n$ and Balanced $k$ (Instance 3)

Scenario C: Large $n$ and Boundary $k$ (Instance 4)

Scenario D: Large $n$ and Large $k$ (Instance 5)