Homework Help is Here – Start Your Trial Now!
Engineering
Data Structures and Algorithms
Question 4 In a Science-oriented university, the following faculties have the respective search probabilities of: Faculty Probability 0.25 Arts Sciences 0.60 Business 0.15 a) Draw all possible Binary Search Trees that can contain the names of the 3 Faculties. b) Use Dynamic Programming to find the Binary Search Tree with the minimum average search time (Optimal BST). Recall that the average search time for an Optimal BST containing items i through j is given by the expression below. Do not forget the first step to sort, so your tree will be a proper BST! A[i, j] = MIN<<=j (A[i,k−1] + A[k+1,j] + Σm=i..j Pm) = Pi if j > i if j = i Solution After sorting: Faculty Probability A11 = A12= A13 = Average search time = A22 = Optimum BST: (draw the tree) >> A33 = A23 =

Question 4 In a Science-oriented university, the following faculties have the respective search probabilities of: Faculty Probability 0.25 Arts Sciences 0.60 Business 0.15 a) Draw all possible Binary Search Trees that can contain the names of the 3 Faculties. b) Use Dynamic Programming to find the Binary Search Tree with the minimum average search time (Optimal BST). Recall that the average search time for an Optimal BST containing items i through j is given by the expression below. Do not forget the first step to sort, so your tree will be a proper BST! A[i, j] = MIN<<=j (A[i,k−1] + A[k+1,j] + Σm=i..j Pm) = Pi if j > i if j = i Solution After sorting: Faculty Probability A11 = A12= A13 = Average search time = A22 = Optimum BST: (draw the tree) >> A33 = A23 =

icon
Related questions
Question

Question 4

Question 4 In a Science-oriented university, the following faculties have the respective search probabilities of: Faculty Probability 0.25 Arts Sciences 0.60 Business 0.15 a) Draw all possible Binary Search Trees that can contain the names of the 3 Faculties. b) Use Dynamic Programming to find the Binary Search Tree with the minimum average search time (Optimal BST). Recall that the average search time for an Optimal BST containing items i through j is given by the expression below. Do not forget the first step to sort, so your tree will be a proper BST! A[i, j] = MIN<<=j (A[i,k−1] + A[k+1,j] + Σm=i..j Pm) = Pi if j > i if j = i Solution After sorting: Faculty Probability A11 = A12= A13 = Average search time = A22 = Optimum BST: (draw the tree) >> A33 = A23 =
Transcribed Image Text:Question 4 In a Science-oriented university, the following faculties have the respective search probabilities of: Faculty Probability 0.25 Arts Sciences 0.60 Business 0.15 a) Draw all possible Binary Search Trees that can contain the names of the 3 Faculties. b) Use Dynamic Programming to find the Binary Search Tree with the minimum average search time (Optimal BST). Recall that the average search time for an Optimal BST containing items i through j is given by the expression below. Do not forget the first step to sort, so your tree will be a proper BST! A[i, j] = MIN<<=j (A[i,k−1] + A[k+1,j] + Σm=i..j Pm) = Pi if j > i if j = i Solution After sorting: Faculty Probability A11 = A12= A13 = Average search time = A22 = Optimum BST: (draw the tree) >> A33 = A23 =
Expert Solution
steps

Step by step

Solved in 2 steps with 2 images

SEE SOLUTIONCheck out a sample Q&A here
Blurred answer