Session 11

This session (PDF)MCS-216 Section 1 (ZIP)MCS-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.20.

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:

`i \ j`	1	2	3	4	5	6	7
1	0.28	0.62	1.02	1.38	1.87	2.50	3.20
2		0.30	0.68	0.96	1.45	2.02	2.68
3			0.32	0.60	1.07	1.54	2.20
4				0.26	0.60	1.06	1.61
5					0.32	0.75	1.25
6						0.34	0.81
7							0.36

Tree Reconstruction

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

root[1][4] = 2 → k2 is left child of k5
root[6][7] = 7 → k7 is right child of k5
Continue recursively until all root[i][j] and base dummy keys are placed.

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

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

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

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]`