Question

Write an algorithm to find OBST using dynamic programming.

Answer 1

Answer

Optimal Substructure:

The optimal cost for freq[i..j] can be recursively calculated using following formula.

optcost\left ( i, \right j) = \sum_{k=i}^{j} freq \begin{bmatrix}k\end{bmatrix} + min_{r=i}^{j}\begin{bmatrix} optcost(i, r-1) + optcost(r+1, j) \end{bmatrix}

We need to calculate optCost(0, n-1) to find the result.

The idea of above formula is simple, we one by one try all nodes as root (r varies from i to j in second term). When we make rth node as root, we recursively calculate optimal cost from i to r-1 and r+1 to j.

We add sum of frequencies from i to j (see first term in the above formula), this is added because every search will go through root and one comparison will be done for every search.

2) Overlapping Subproblems

Answer 2

Explanation:

Static scheduling algorithm for cloudlet allocation using dynam