For each of the following questions, indicate whether the statement is TRUE or F

Question

For each of the following questions, indicate whether the statement is TRUE or FALSE. Briefly explain your answer in each case.

a)   For the Optimal BST algorithm, it is necessary to maintain the entire upper-triangle of the 2-dimensional table in memory throughout the computation, in order to compute the average search time of the optimal binary search tree.

b)   For the Optimal BST algorithm, it is necessary to maintain the entire upper-triangle of the 2-dimensional table in memory throughout the computation, in order to determine the actual shape of the best BST.

c)   For the All Pairs Shortest Path algorithm, it is necessary to maintain the entire 3-dimensional table in memory throughout the computation, in order to compute the length of the shortest paths from any node x to any node y.

d)   For the All Pairs Shortest Path algorithm, it is necessary to maintain the entire 3-dimensional table in memory throughout the computation, in order to determine the actual nodes along the shortest paths from any node x to any node y.

Explanation / Answer

B)

For the Optimal BST algorithm, it is necessary to maintain the entire upper-triangle of the 2-dimensional table in memory throughout the computation, in order to determine the actual shape of the best BST.

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.