Session 11

This session (PDF)MCSL-216 Section 1 (ZIP)MCSL-216 (ZIP)Semester 1 (ZIP)

More downloads

MCSL-216 Section 1 (ZIP)MCSL-216 (ZIP)Semester 1 (ZIP)

This session covers the optimal binary search tree problem. A normal binary search tree only depends on key order, but an optimal BST also considers how frequently each key is searched so that the expected search cost is minimized.

Objectives

Do not copy. Read for understanding and the viva

Understand optimal binary search tree construction.
Determine the minimum expected search cost.
Show the final tree structure for the given key probabilities/frequencies.

Concept

Do not copy. Read for understanding and the viva

An optimal binary search tree minimizes the expected search cost when keys have different search probabilities. Frequently searched keys should appear closer to the root when that reduces total weighted path cost.

Dynamic Programming Idea

Do not copy. Read for understanding and the viva

For each key range, try each key as root and choose the root that gives minimum expected cost.

cost[i][j] = min(cost[i][r-1] + cost[r+1][j] + sum(freq[i..j]))

where r ranges from i to j.

Question 1

Problem Statement

Write in lab record

Determine the cost and structure of an optimal binary search tree for a set of n = 7 keys with the given properties. Show the step-by-step process.

i	0	1	2	3	4	5	6	7
$p_{i}$		0.04	0.06	0.08	0.02	0.10	0.12	0.14
$q_{i}$	0.06	0.06	0.06	0.06	0.05	0.05	0.05	0.05

Explanation

Do not copy. Read for understanding and the viva

Optimal Tree Structure

Write in lab record

For n = 7 keys with the given probabilities, the minimum expected search cost is 3.12 (exactly 78/25) with $k_{5}$ at the root.

Optimal binary search tree for the 7 keys: k5 at the root, cost 3.12Open full size ↗

Step-by-Step

Write in lab record

The OBST problem is solved using the standard CLRS dynamic programming approach. We maintain three tables:

e[i][j]: Expected search cost for keys $k_{i}$ to $k_{j}$
w[i][j]: Sum of probabilities in the subtree (keys + dummy keys)
root[i][j]: Index of the root key that minimizes e[i][j]

Recurrence Relations

Do not copy. Read for understanding and the viva

Base Case: $‘ e [i] [i - 1] = q_{i - 1} a n d w [i] [i - 1] = q_{i - 1} ‘$ for i = 1 to n+1
Weight Update: $‘ w [i] [j] = w [i] [j - 1] + p_{j} + q_{j} ‘$
Cost Update: $‘ e [i] [j] = m i n_{r = i . . j} e [i] [r - 1] + e [r + 1] [j] + w [i] [j] ‘$

Table Initialization

Do not copy. Read for understanding and the viva

e[1][0] = 0.06, e[2][1] = 0.06, e[3][2] = 0.06, e[4][3] = 0.06
e[5][4] = 0.05, e[6][5] = 0.05, e[7][6] = 0.05, e[8][7] = 0.05
w[i][i-1] = e[i][i-1]

Filling Tables (Length l = 1 to 7)

We iterate over subtree lengths l, then start index i, compute j = i + l - 1, calculate w[i][j], and try every possible root r between i and j.

Example for l=1, i=1, j=1:

w[1][1] = w[1][0] + p_1 + q_1 = 0.06 + 0.04 + 0.06 = 0.16
e[1][1] = e[1][0] + e[2][1] + w[1][1] = 0.06 + 0.06 + 0.16 = 0.28
root[1][1] = 1

Repeating this for all l yields the final tables:

`e[i][j]`	1	2	3	4	5	6	7
1	0.28	0.62	1.02	1.34	1.83	2.44	3.12
2		0.30	0.68	0.93	1.41	1.96	2.61
3			0.32	0.57	1.04	1.48	2.13
4				0.24	0.57	1.01	1.55
5					0.30	0.72	1.20
6						0.32	0.78
7							0.34

`root[i][j]`	1	2	3	4	5	6	7
1	1	2	2	2	3	3	5
2		2	3	3	3	5	5
3			3	3	4	5	5
4				4	5	5	6
5					5	6	6
6						6	7
7							7

Check on the diagonal: e[4][4] = e[4][3] + e[5][4] + w[4][4] = 0.06 + 0.05 + (0.06 + 0.02 + 0.05) = 0.24. Note $q_{4} = 0.05$ , not 0.06; that is where a hand calculation usually slips.

Tree Reconstruction

Starting from root[1][7] = 5, we recursively find subtrees:

root[1][4] = 2 → $k_{2}$ is the left child of $k_{5}$ ; root[6][7] = 7 → $k_{7}$ is the right child.
root[1][1] = 1 and root[3][4] = 3 → $k_{1}$ and $k_{3}$ under $k_{2}$ ; root[4][4] = 4 → $k_{4}$ is the right child of $k_{3}$ .
root[6][6] = 6 → $k_{6}$ is the left child of $k_{7}$ ; the right child of $k_{7}$ is the dummy $d_{7}$ .
Every empty range [i, i-1] becomes the dummy leaf $d_{i - 1}$ : $d_{0}, d_{1}$ under $k_{1}$ ; $d_{2}$ under $k_{3}$ ; $d_{3}, d_{4}$ under $k_{4}$ ; $d_{5}, d_{6}$ under $k_{6}$ .

Implementation

Write in lab record

Lab record: write one language only. Pick yours once and every page opens on it; the other tabs are the same solution for comparison.Your language

binary-search.pypython

def optimal_bst(p, q):
    n = len(p) - 1  # p is 1-indexed, so length is n+1
    # e[i][j] stores expected cost, w[i][j] stores probability sum
    e = [[0.0] * (n + 2) for _ in range(n + 2)]
    w = [[0.0] * (n + 2) for _ in range(n + 2)]
    root = [[0] * (n + 1) for _ in range(n + 1)]

    # Base cases: single dummy keys
    for i in range(1, n + 2):
        e[i][i - 1] = q[i - 1]
        w[i][i - 1] = q[i - 1]

    # DP over chain length l
    for l in range(1, n + 1):
        for i in range(1, n - l + 2):
            j = i + l - 1
            e[i][j] = float("inf")
            w[i][j] = w[i][j - 1] + p[j] + q[j]

            # Try every key as root
            for r in range(i, j + 1):
                t = e[i][r - 1] + e[r + 1][j] + w[i][j]
                if t < e[i][j]:
                    e[i][j] = t
                    root[i][j] = r
    return e, root


def print_tree(root, i, j, depth=0, is_left=True):
    """Recursively print the tree structure"""
    prefix = "L" if is_left else "R"
    indent = "    " * depth
    if i > j:
        print(f"{indent}{prefix} -> d{i - 1} (q={q[i - 1]:.2f})")
        return

    r = root[i][j]
    print(f"{indent}{prefix} -> k{r} (p={p[r]:.2f})")
    print_tree(root, i, r - 1, depth + 1, True)
    print_tree(root, r + 1, j, depth + 1, False)


if __name__ == "__main__":
    p = [0, 0.04, 0.06, 0.08, 0.02, 0.10, 0.12, 0.14]
    q = [0.06, 0.06, 0.06, 0.06, 0.05, 0.05, 0.05, 0.05]
    e, root = optimal_bst(p, q)
    print(f"Optimal Expected Cost: {e[1][len(p) - 1]:.4f}\n")
    print("Tree Structure:")
    print_tree(root, 1, len(p) - 1)

binary-search.cc

#include <stdio.h>
#include <stdlib.h>
#include <float.h>

#define N 7

void construct_optimal_bst(double p[], double q[], double e[][N+2], int root[][N+1]) {
    double w[N+2][N+2];

    // Initialize base cases
    for (int i = 1; i <= N + 1; i++) {
        e[i][i-1] = q[i-1];
        w[i][i-1] = q[i-1];
    }

    // DP over subtree length l
    for (int l = 1; l <= N; l++) {
        for (int i = 1; i <= N - l + 1; i++) {
            int j = i + l - 1;
            e[i][j] = DBL_MAX;
            w[i][j] = w[i][j-1] + p[j] + q[j];

            for (int r = i; r <= j; r++) {
                double t = e[i][r-1] + e[r+1][j] + w[i][j];
                if (t < e[i][j]) {
                    e[i][j] = t;
                    root[i][j] = r;
                }
            }
        }
    }
}

void print_tree(int root[][N+1], int i, int j, int depth, char side) {
    if (i > j) {
        printf("%*c%c -> d%d\n", depth * 4, ' ', side, i-1);
        return;
    }
    int r = root[i][j];
    printf("%*c%c -> k%d\n", depth * 4, ' ', side, r);
    print_tree(root, i, r-1, depth+1, 'L');
    print_tree(root, r+1, j, depth+1, 'R');
}

int main() {
    double p[] = {0, 0.04, 0.06, 0.08, 0.02, 0.10, 0.12, 0.14};
    double q[] = {0.06, 0.06, 0.06, 0.06, 0.05, 0.05, 0.05, 0.05};
    double e[N+2][N+2];
    int root[N+1][N+1];

    construct_optimal_bst(p, q, e, root);

    printf("Optimal Expected Cost: %.4f\n", e[1][N]);
    printf("\nTree Structure:\n");
    print_tree(root, 1, N, 0, 'R');

    return 0;
}

binary-search.rsrust

fn optimal_bst(p: &[f64], q: &[f64]) -> (Vec<Vec<f64>>, Vec<Vec<usize>>) {
    let n = p.len() - 1;
    let mut e = vec![vec![0.0; n + 2]; n + 2];
    let mut w = vec![vec![0.0; n + 2]; n + 2];
    let mut root = vec![vec![0; n + 1]; n + 1];

    // Base cases
    for i in 1..=n + 1 {
        e[i][i - 1] = q[i - 1];
        w[i][i - 1] = q[i - 1];
    }

    // DP
    for l in 1..=n {
        for i in 1..=(n - l + 1) {
            let j = i + l - 1;
            e[i][j] = f64::MAX;
            w[i][j] = w[i][j - 1] + p[j] + q[j];

            for r in i..=j {
                let t = e[i][r - 1] + e[r + 1][j] + w[i][j];
                if t < e[i][j] {
                    e[i][j] = t;
                    root[i][j] = r;
                }
            }
        }
    }
    (e, root)
}

fn print_tree(root: &[Vec<usize>], i: usize, j: usize, depth: usize, side: char) {
    if i > j {
        println!("{:indent$}{} -> d{}", "", side, i - 1, indent = depth * 4);
        return;
    }
    let r = root[i][j];
    println!("{:indent$}{} -> k{}", "", side, r, indent = depth * 4);
    print_tree(root, i, r - 1, depth + 1, 'L');
    print_tree(root, r + 1, j, depth + 1, 'R');
}

fn main() {
    let p = vec![0.0, 0.04, 0.06, 0.08, 0.02, 0.10, 0.12, 0.14];
    let q = vec![0.06, 0.06, 0.06, 0.06, 0.05, 0.05, 0.05, 0.05];

    let (e, root) = optimal_bst(&p, &q);
    println!("Optimal Expected Cost: {:.4}\n", e[1][p.len() - 1]);
    println!("Tree Structure:");
    print_tree(&root, 1, p.len() - 1, 0, 'R');
}

Sample Output

Write in lab record

Optimal Expected Cost: 3.1200

Tree Structure:
L -> k5 (p=0.10)
    L -> k2 (p=0.06)
        L -> k1 (p=0.04)
            L -> d0 (q=0.06)
            R -> d1 (q=0.06)
        R -> k3 (p=0.08)
            L -> d2 (q=0.06)
            R -> k4 (p=0.02)
                L -> d3 (q=0.06)
                R -> d4 (q=0.05)
    R -> k7 (p=0.14)
        L -> k6 (p=0.12)
            L -> d5 (q=0.05)
            R -> d6 (q=0.05)
        R -> d7 (q=0.05)

Question 2

Problem Statement

Write in lab record

Determine the cost and structure of an optimal binary search tree for a set of n = 5 keys with the given properties. Show the step-by-step process.

i	0	1	2	3	4	5
$p_{i}$		0.15	0.10	0.05	0.10	0.20
$q_{i}$	0.05	0.10	0.05	0.05	0.05	0.10

Answer

Write in lab record

Dynamic Programming Formulation

We use three $O (n^{2})$ tables:

e[i][j]: Expected search cost for keys $k_{i} \dots k_{j}$
w[i][j]: Probability weight of subtree $i \dots j$
root[i][j]: Index of the optimal root for subtree $i \dots j$

Recurrence Relations:

Base Case: $‘ e [i] [i - 1] = q_{i - 1}$ , $w [i] [i - 1] = q_{i - 1} ‘$
Weight Update: $‘ w [i] [j] = w [i] [j - 1] + p_{j} + q_{j} ‘$
Cost Update: $‘ e [i] [j] = \min_{r = i}^{j} e [i] [r - 1] + e [r + 1] [j] + w [i] [j] ‘$

Step-by-Step DP Calculation

Write in lab record

Step 1: Base Cases (`l = 0`)

`i`	`e[i][i-1]`	`w[i][i-1]`
1	0.05	0.05
2	0.10	0.10
3	0.05	0.05
4	0.05	0.05
5	0.05	0.05
6	0.10	0.10

Step 2: Chain Length `l = 1`

`i`	`j`	`w[i][j]`	`e[i][j]`	`root[i][j]`	Calculation (`min` expression)
1	1	0.30	0.45	1	`0.05 + 0.10 + 0.30`
2	2	0.25	0.40	2	`0.10 + 0.05 + 0.25`
3	3	0.15	0.25	3	`0.05 + 0.05 + 0.15`
4	4	0.20	0.30	4	`0.05 + 0.05 + 0.20`
5	5	0.35	0.50	5	`0.05 + 0.10 + 0.35`

Step 3: Chain Length `l = 2`

`i`	`j`	`w[i][j]`	`e[i][j]`	`root[i][j]`	Best `r` & Calculation
1	2	0.45	0.90	1	`r=1: 0.05 + 0.40 + 0.45`
2	3	0.35	0.70	2	`r=2: 0.10 + 0.25 + 0.35`
3	4	0.30	0.60	4	`r=4: 0.25 + 0.05 + 0.30`
4	5	0.50	0.90	5	`r=5: 0.30 + 0.10 + 0.50`

Step 4: Chain Length `l = 3`

`i`	`j`	`w[i][j]`	`e[i][j]`	`root[i][j]`	Best `r` & Calculation
1	3	0.55	1.25	2	`r=2: 0.45 + 0.25 + 0.55`
2	4	0.50	1.20	2	`r=2: 0.10 + 0.60 + 0.50`
3	5	0.60	1.30	5	`r=5: 0.60 + 0.10 + 0.60`

Step 5: Chain Length `l = 4`

`i`	`j`	`w[i][j]`	`e[i][j]`	`root[i][j]`	Best `r` & Calculation
1	4	0.70	1.75	2	`r=2: 0.45 + 0.60 + 0.70`
2	5	0.80	2.00	4	`r=4: 0.70 + 0.50 + 0.80`

Step 6: Chain Length `l = 5` (Full Tree)

`i`	`j`	`w[i][j]`	`e[i][j]`	`root[i][j]`	Best `r` & Calculation
1	5	1.00	2.75	2	`r=2: 0.45 + 1.30 + 1.00`

Final DP Tables

Write in lab record

Expected Cost Table `e[i][j]`

`i\j`	1	2	3	4	5
1	0.45	0.90	1.25	1.75	2.75
2	—	0.40	0.70	1.20	2.00
3	—	—	0.25	0.60	1.30
4	—	—	—	0.30	0.90
5	—	—	—	—	0.50

Optimal Root Table `root[i][j]`

`i\j`	1	2	3	4	5
1	1	1	2	2	2
2	—	2	2	2	4
3	—	—	3	4	5
4	—	—	—	4	5
5	—	—	—	—	5

Optimal Tree Structure

Write in lab record

Optimal binary search tree for the 7 keys: k5 at the root, cost 3.12Open full size ↗

Implementation

Write in lab record

Lab record: write one language only. Pick yours once and every page opens on it; the other tabs are the same solution for comparison.Your language

binary-search.pypython

def optimal_bst(p, q):
    """Compute optimal BST using dynamic programming."""
    n = len(p) - 1
    e = [[0.0] * (n + 2) for _ in range(n + 2)]
    w = [[0.0] * (n + 2) for _ in range(n + 2)]
    root = [[0] * (n + 1) for _ in range(n + 1)]

    # Base cases: empty subtrees
    for i in range(1, n + 2):
        e[i][i - 1] = q[i - 1]
        w[i][i - 1] = q[i - 1]

    # DP over chain length l
    for l in range(1, n + 1):
        for i in range(1, n - l + 2):
            j = i + l - 1
            e[i][j] = float("inf")
            w[i][j] = w[i][j - 1] + p[j] + q[j]

            for r in range(i, j + 1):
                t = e[i][r - 1] + e[r + 1][j] + w[i][j]
                if t < e[i][j]:
                    e[i][j] = t
                    root[i][j] = r
    return e, root


def print_tree(root, p, q, i, j, depth=0, side="R"):
    """Recursively print tree structure."""
    indent = "    " * depth
    if i > j:
        print(f"{indent}{side} -> d{i - 1} (q={q[i - 1]:.2f})")
        return
    r = root[i][j]
    print(f"{indent}{side} -> k{r} (p={p[r]:.2f})")
    print_tree(root, p, q, i, r - 1, depth + 1, "L")
    print_tree(root, p, q, r + 1, j, depth + 1, "R")


if __name__ == "__main__":
    p = [0, 0.15, 0.10, 0.05, 0.10, 0.20]
    q = [0.05, 0.10, 0.05, 0.05, 0.05, 0.10]
    e, root = optimal_bst(p, q)
    print(f"Optimal Expected Cost: {e[1][len(p) - 1]:.4f}\n")
    print("Tree Structure:")
    print_tree(root, p, q, 1, len(p) - 1)

binary-search.cc

#include <stdio.h>
#include <float.h>

#define N 5

void construct_optimal_bst(double p[], double q[], double e[][N+2], int root[][N+1]) {
    double w[N+2][N+2];
    // Base cases
    for (int i = 1; i <= N + 1; i++) {
        e[i][i-1] = q[i-1];
        w[i][i-1] = q[i-1];
    }
    // DP
    for (int l = 1; l <= N; l++) {
        for (int i = 1; i <= N - l + 1; i++) {
            int j = i + l - 1;
            e[i][j] = DBL_MAX;
            w[i][j] = w[i][j-1] + p[j] + q[j];
            for (int r = i; r <= j; r++) {
                double t = e[i][r-1] + e[r+1][j] + w[i][j];
                if (t < e[i][j]) {
                    e[i][j] = t;
                    root[i][j] = r;
                }
            }
        }
    }
}

void print_tree(int root[][N+1], double p[], double q[], int i, int j, int depth, char side) {
    if (i > j) {
        printf("%*c%c -> d%d (q=%.2f)\n", depth * 4, ' ', side, i-1, q[i-1]);
        return;
    }
    int r = root[i][j];
    printf("%*c%c -> k%d (p=%.2f)\n", depth * 4, ' ', side, r, p[r]);
    print_tree(root, p, q, i, r-1, depth+1, 'L');
    print_tree(root, p, q, r+1, j, depth+1, 'R');
}

int main() {
    double p[] = {0, 0.15, 0.10, 0.05, 0.10, 0.20};
    double q[] = {0.05, 0.10, 0.05, 0.05, 0.05, 0.10};
    double e[N+2][N+2];
    int root[N+1][N+1];

    construct_optimal_bst(p, q, e, root);
    printf("Optimal Expected Cost: %.4f\n\n", e[1][N]);
    printf("Tree Structure:\n");
    print_tree(root, p, q, 1, N, 0, 'R');
    return 0;
}

binary-search.rsrust

fn optimal_bst(p: &[f64], q: &[f64]) -> (Vec<Vec<f64>>, Vec<Vec<usize>>) {
    let n = p.len() - 1;
    let mut e = vec![vec![0.0; n + 2]; n + 2];
    let mut w = vec![vec![0.0; n + 2]; n + 2];
    let mut root = vec![vec![0; n + 1]; n + 1];

    for i in 1..=n + 1 {
        e[i][i - 1] = q[i - 1];
        w[i][i - 1] = q[i - 1];
    }

    for l in 1..=n {
        for i in 1..=(n - l + 1) {
            let j = i + l - 1;
            e[i][j] = f64::MAX;
            w[i][j] = w[i][j - 1] + p[j] + q[j];
            for r in i..=j {
                let t = e[i][r - 1] + e[r + 1][j] + w[i][j];
                if t < e[i][j] {
                    e[i][j] = t;
                    root[i][j] = r;
                }
            }
        }
    }
    (e, root)
}

fn print_tree(
    root: &[Vec<usize>],
    p: &[f64],
    q: &[f64],
    i: usize,
    j: usize,
    depth: usize,
    side: char,
) {
    if i > j {
        println!(
            "{:indent$}{} -> d{} (q={:.2f})",
            "",
            side,
            i - 1,
            q[i - 1],
            indent = depth * 4
        );
        return;
    }
    let r = root[i][j];
    println!(
        "{:indent$}{} -> k{} (p={:.2f})",
        "",
        side,
        r,
        p[r],
        indent = depth * 4
    );
    print_tree(root, p, q, i, r - 1, depth + 1, 'L');
    print_tree(root, p, q, r + 1, j, depth + 1, 'R');
}

fn main() {
    let p = vec![0.0, 0.15, 0.10, 0.05, 0.10, 0.20];
    let q = vec![0.05, 0.10, 0.05, 0.05, 0.05, 0.10];
    let (e, root) = optimal_bst(&p, &q);
    println!("Optimal Expected Cost: {:.4}\n", e[1][p.len() - 1]);
    println!("Tree Structure:");
    print_tree(&root, &p, &q, 1, p.len() - 1, 0, 'R');
}

Sample Output

Write in lab record

Optimal Expected Cost: 2.7500

Tree Structure:
R -> k2 (p=0.10)
    L -> k1 (p=0.15)
        L -> d0 (q=0.05)
        R -> d1 (q=0.10)
    R -> k5 (p=0.20)
        L -> k4 (p=0.10)
            L -> k3 (p=0.05)
                L -> d2 (q=0.05)
                R -> d3 (q=0.05)
            R -> d4 (q=0.05)
        R -> d5 (q=0.10)

Question 3

Problem Statement

Write in lab record

Implement the optimal binary search tree algorithm on your system and study the performance of the algorithm on different problem instances

Approach

Do not copy. Read for understanding and the viva

Hand-worked DP tables are fine for small n, but studying performance across instances needs:

Automated execution: the same DP logic runs on both problem instances, with no transcription errors.

Quantitative metrics: execution time, a count of primitive operations (inner-loop iterations), and memory footprint.

Empirical validation: showing how the $O (n^{3})$ time complexity scales even between small instances (n = 5 and n = 7).

Performance Metrics

Do not copy. Read for understanding and the viva

Metric	Description	Why it matters
Execution time	Wall-clock time from a high-resolution timer	Real-world runtime behaviour
DP operations	Count of inner-loop comparisons (`t < e[i][j]`)	Algorithmic work, independent of hardware
Space	Floating-point cells allocated, 3 × (n+2)²	Memory footprint for large inputs
Optimal cost	Final `e[1][n]`	Correctness check

Execution Results

Write in lab record

Instance	$n$	Optimal Cost	DP Operations (exact)	Python Time	C Time	Rust Time	Memory Cells ( $3 \times {(n + 2)}^{2}$ )
Problem 2	5	2.7500	35	4.2 µs	0.8 µs	0.7 µs	147
Problem 1	7	3.1200	84	9.1 µs	1.4 µs	1.3 µs	243

Times vary from machine to machine; the operation counts and costs do not. The inner loop runs

\sum_{l = 1}^{n} l (n - l + 1) = \frac{n (n + 1) (n + 2)}{6} times

n = 5 : 1 \times 5 + 2 \times 4 + 3 \times 3 + 4 \times 2 + 5 \times 1 = 35

n = 7 : 1 \times 7 + 2 \times 6 + 3 \times 5 + 4 \times 4 + 5 \times 3 + 6 \times 2 + 7 \times 1 = 84

Analysis and Conclusion

Write in lab record

Even at small $n$ , the operation count jumps from 35 to 84 when $n$ goes from 5 to 7, a ratio of $84 / 35 = 2.4$ . The count is $n (n + 1) (n + 2) / 6$ , which grows as $n^{3}$ : the lower-order terms keep the ratio below ${(7 / 5)}^{3} \approx 2.74$ for small inputs, and it approaches the cube ratio as $n$ grows. This confirms the cubic $O (n^{3})$ complexity of the algorithm.

Space Complexity

All implementations allocate three $(n + 2) \times (n + 2)$ tables.

n = 5: 147 doubles, about 1.15 KB
n = 7: 243 doubles, about 1.90 KB
Space is trivial for n up to 500 but grows quadratically. For n above 1000, consider:
- Rolling arrays, which reduce w and e to O(n) space
- Knuth’s root-restriction optimisation, which brings time down to $O (n^{2})$

Implementation

Write in lab record

Lab record: write one language only. Pick yours once and every page opens on it; the other tabs are the same solution for comparison.Your language

binary-search.pypython

import time
import sys

def optimal_bst(p, q, name="Instance"):
    """
    Dynamic Programming solution for Optimal Binary Search Tree.
    Tracks execution time and inner-loop operation count.
    """
    n = len(p) - 1  # p is 1-indexed
    ops = 0  # Counts primitive comparisons

    # Allocate DP tables: e[cost], w[weight], root[index]
    e = [[0.0] * (n + 2) for _ in range(n + 2)]
    w = [[0.0] * (n + 2) for _ in range(n + 2)]
    root = [[0] * (n + 1) for _ in range(n + 1)]

    # Base case: subtrees containing only dummy keys
    for i in range(1, n + 2):
        e[i][i - 1] = q[i - 1]
        w[i][i - 1] = q[i - 1]

    # High-resolution timing start
    start = time.perf_counter()

    # DP over chain length l = 1 to n
    for l in range(1, n + 1):
        for i in range(1, n - l + 2):
            j = i + l - 1
            e[i][j] = float('inf')
            # Weight recurrence: O(1) per cell
            w[i][j] = w[i][j - 1] + p[j] + q[j]

            # Try every key r in [i, j] as root: O(n) per cell
            for r in range(i, j + 1):
                t = e[i][r - 1] + e[r + 1][j] + w[i][j]
                ops += 1  # Track primitive operation
                if t < e[i][j]:
                    e[i][j] = t
                    root[i][j] = r

    # Timing end
    elapsed = (time.perf_counter() - start) * 1_000_000  # Convert to microseconds

    print(f"[{name}] Optimal Cost: {e[1][n]:.4f} | Time: {elapsed:.2f} µs | Ops: {ops}")
    return e[1][n], ops, elapsed

if __name__ == "__main__":
    print("🔬 OBST Performance Study (Python)\n")
    # Instance 1 (n=7)
    p1 = [0, 0.04, 0.06, 0.08, 0.02, 0.10, 0.12, 0.14]
    q1 = [0.06, 0.06, 0.06, 0.06, 0.05, 0.05, 0.05, 0.05]
    optimal_bst(p1, q1, "Problem 1 (n=7)")

    # Instance 2 (n=5)
    p2 = [0, 0.15, 0.10, 0.05, 0.10, 0.20]
    q2 = [0.05, 0.10, 0.05, 0.05, 0.05, 0.10]
    optimal_bst(p2, q2, "Problem 2 (n=5)")

binary-search.cc

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <float.h>

#define MAX_N 50  // Safe upper bound for small instances

typedef struct {
    double cost;
    long ops;
    double time_us;
} Result;

Result optimal_bst(double p[], double q[], int n, const char* name) {
    // Allocate 2D tables on heap to avoid stack overflow for larger n
    double (*e)[MAX_N+2] = calloc(n + 2, sizeof(double[MAX_N+2]));
    double (*w)[MAX_N+2] = calloc(n + 2, sizeof(double[MAX_N+2]));
    int    (*root)[MAX_N+1] = calloc(n + 1, sizeof(int[MAX_N+1]));

    long ops = 0;

    // Base case initialization
    for (int i = 1; i <= n + 1; i++) {
        e[i][i-1] = q[i-1];
        w[i][i-1] = q[i-1];
    }

    struct timespec start, end;
    clock_gettime(CLOCK_MONOTONIC, &start);

    // DP recurrence: O(n^3) time, O(n^2) space
    for (int l = 1; l <= n; l++) {
        for (int i = 1; i <= n - l + 1; i++) {
            int j = i + l - 1;
            e[i][j] = DBL_MAX;
            w[i][j] = w[i][j-1] + p[j] + q[j];

            for (int r = i; r <= j; r++) {
                double t = e[i][r-1] + e[r+1][j] + w[i][j];
                ops++;  // Count comparison operation
                if (t < e[i][j]) {
                    e[i][j] = t;
                    root[i][j] = r;
                }
            }
        }
    }

    clock_gettime(CLOCK_MONOTONIC, &end);
    double elapsed_us = (end.tv_sec - start.tv_sec) * 1e6 + (end.tv_nsec - start.tv_nsec) / 1e3;

    printf("[%s] Optimal Cost: %.4f | Time: %.2f µs | Ops: %ld\n",
           name, e[1][n], elapsed_us, ops);

    Result res = {e[1][n], ops, elapsed_us};
    free(e); free(w); free(root);
    return res;
}

int main() {
    printf("🔬 OBST Performance Study (C)\n\n");

    // Problem 1 (n=7)
    double p1[] = {0, 0.04, 0.06, 0.08, 0.02, 0.10, 0.12, 0.14};
    double q1[] = {0.06, 0.06, 0.06, 0.06, 0.05, 0.05, 0.05, 0.05};
    optimal_bst(p1, q1, 7, "Problem 1 (n=7)");

    // Problem 2 (n=5)
    double p2[] = {0, 0.15, 0.10, 0.05, 0.10, 0.20};
    double q2[] = {0.05, 0.10, 0.05, 0.05, 0.05, 0.10};
    optimal_bst(p2, q2, 5, "Problem 2 (n=5)");

    return 0;
}

binary-search.rsrust

use std::time::Instant;

/// Structure to hold performance metrics for a single run
struct BenchResult {
    optimal_cost: f64,
    operations: usize,
    time_us: f64,
}

fn optimal_bst(p: &[f64], q: &[f64], name: &str) -> BenchResult {
    let n = p.len() - 1;
    let mut ops = 0;

    // Allocate DP tables with 1-based indexing padding
    let mut e = vec![vec![0.0; n + 2]; n + 2];
    let mut w = vec![vec![0.0; n + 2]; n + 2];
    let mut root = vec![vec![0usize; n + 1]; n + 1];

    // Base case: empty subtrees
    for i in 1..=n + 1 {
        e[i][i - 1] = q[i - 1];
        w[i][i - 1] = q[i - 1];
    }

    let start = Instant::now();

    // DP over chain length l
    for l in 1..=n {
        for i in 1..=(n - l + 1) {
            let j = i + l - 1;
            e[i][j] = f64::MAX;
            w[i][j] = w[i][j - 1] + p[j] + q[j];

            // Root selection loop
            for r in i..=j {
                let t = e[i][r - 1] + e[r + 1][j] + w[i][j];
                ops += 1;
                if t < e[i][j] {
                    e[i][j] = t;
                    root[i][j] = r;
                }
            }
        }
    }

    let elapsed_us = start.elapsed().as_secs_f64() * 1_000_000.0;

    println!(
        "[{}] Optimal Cost: {:.4} | Time: {:.2} µs | Ops: {}",
        name, e[1][n], elapsed_us, ops
    );

    BenchResult {
        optimal_cost: e[1][n],
        operations: ops,
        time_us: elapsed_us,
    }
}

fn main() {
    println!("🔬 OBST Performance Study (Rust)\n");

    // Problem 1 (n=7)
    let p1 = vec![0.0, 0.04, 0.06, 0.08, 0.02, 0.10, 0.12, 0.14];
    let q1 = vec![0.06, 0.06, 0.06, 0.06, 0.05, 0.05, 0.05, 0.05];
    optimal_bst(&p1, &q1, "Problem 1 (n=7)");

    // Problem 2 (n=5)
    let p2 = vec![0.0, 0.15, 0.10, 0.05, 0.10, 0.20];
    let q2 = vec![0.05, 0.10, 0.05, 0.05, 0.05, 0.10];
    optimal_bst(&p2, &q2, "Problem 2 (n=5)");
}

Sample Output

Write in lab record

🔬 OBST Performance Study (Python)

[Problem 1 (n=7)] Optimal Cost: 3.1200 | Time: 13.54 µs | Ops: 84
[Problem 2 (n=5)] Optimal Cost: 2.7500 | Time: 5.08 µs | Ops: 35

Objectives

Concept

Dynamic Programming Idea

Question 1

Problem Statement

Explanation

Optimal Tree Structure

Step-by-Step

Recurrence Relations

Table Initialization

Filling Tables (Length l = 1 to 7)

Tree Reconstruction

Implementation

Sample Output

Question 2

Problem Statement

Answer

Dynamic Programming Formulation

Recurrence Relations:

Step-by-Step DP Calculation

Step 1: Base Cases (l = 0)

Step 2: Chain Length l = 1

Step 3: Chain Length l = 2

Step 4: Chain Length l = 3

Step 5: Chain Length l = 4

Step 6: Chain Length l = 5 (Full Tree)

Final DP Tables

Expected Cost Table e[i][j]

Optimal Root Table root[i][j]

Optimal Tree Structure

Implementation

Sample Output

Question 3

Problem Statement

Approach

Performance Metrics

Execution Results

Analysis and Conclusion

Space Complexity

Implementation

Sample Output

Step 1: Base Cases (`l = 0`)

Step 2: Chain Length `l = 1`

Step 3: Chain Length `l = 2`

Step 4: Chain Length `l = 3`

Step 5: Chain Length `l = 4`

Step 6: Chain Length `l = 5` (Full Tree)

Expected Cost Table `e[i][j]`

Optimal Root Table `root[i][j]`