Question 6380 – Engineering-Mathematics
April 8, 2024Question 10974 – Software-Engineering
April 8, 2024Question 6925 – Engineering-Mathematics
Let n = 4 and (a1, a2, a3, a4) = (do, if, int, while). Let p(1 : 4) = (3/8, 3/8, 1/8, 1/8) and Let q(0 : 4) = (2/8, 3/8, 1/8, 1/8, 1/8) where p(i) and q(i) denotes the probability with which we search ai and the identifier x being searched satisfy ai < x < ai+1 respectively. The optimal search tree is given by:
Correct Answer: B
Question 1028 Explanation:
The above problem is nothing but Optimal Binary Search Tree(OBST). The OBST we are using the recurrence relation is
Initially, we have w(i,j)=q(i), c(i,j)=0 and r(i,i)=0, 0 ≤ i ≤ 4. The observations are w(i,j)=p(j)+q(j)+w(i,j-1), we get
w(0,1) = p(1) + q(1) + w(0,0) = 8
c(0,1) = w(0,1) + min{c(0,0) + c(1,1)} = 8
r(0,1) = 1
w(1,2) = p(2) + q(2) + w(1,1) = 7
c(1,2) = w(1,2) + min{c(1,1) + c(2,2)} = 7
r(0,2) = 2
w(2,3) = p(3) + q(3) + w(2,2) = 3
c(2,3) = w(2,3) + min{c(2,2) + c(3,3)} = 3
r(2,3) = 3
w(3,4) = p(4) + q(4) + w(3,3) = 3
c(3,4) = w(3,4) + min{c(3,3) + c(4,4)} = 3
r(3,4) = 4
knowing w(i, i+1) and c(i, i+1), 0 ≤ i < 4 and to compute recurrence relation of OBST and compute w(i, i+2), c(i,i+2) and r(i,i+2), 0 ≤ i < 3. This process can repeated until w(0,4), c(0,4) and r(0,4) are obtained.
Initially, we have w(i,j)=q(i), c(i,j)=0 and r(i,i)=0, 0 ≤ i ≤ 4. The observations are w(i,j)=p(j)+q(j)+w(i,j-1), we get
w(0,1) = p(1) + q(1) + w(0,0) = 8
c(0,1) = w(0,1) + min{c(0,0) + c(1,1)} = 8
r(0,1) = 1
w(1,2) = p(2) + q(2) + w(1,1) = 7
c(1,2) = w(1,2) + min{c(1,1) + c(2,2)} = 7
r(0,2) = 2
w(2,3) = p(3) + q(3) + w(2,2) = 3
c(2,3) = w(2,3) + min{c(2,2) + c(3,3)} = 3
r(2,3) = 3
w(3,4) = p(4) + q(4) + w(3,3) = 3
c(3,4) = w(3,4) + min{c(3,3) + c(4,4)} = 3
r(3,4) = 4
knowing w(i, i+1) and c(i, i+1), 0 ≤ i < 4 and to compute recurrence relation of OBST and compute w(i, i+2), c(i,i+2) and r(i,i+2), 0 ≤ i < 3. This process can repeated until w(0,4), c(0,4) and r(0,4) are obtained.
Subscribe
Login
0 Comments