question archive 1) Consider the problem of constructing an Optimal Binary Search Tree
1) Consider the problem of constructing an Optimal Binary Search Tree
Subject:Computer SciencePrice: Bought3
1) Consider the problem of constructing an Optimal Binary Search Tree.
2. What is the size of the search space (all possible candidate solutions)?
3. Is it possible to construct a divide and conquer algorithm for this problem? If so, outline an algorithm based on D&C (pseudo code is not necessary) and explain its time complexity.
4. Are there overlapping sub problems? If so, give an example.
5. Show that the optimal substructure property holds for this problem.
6. Give an algorithm (pseudo code) based on dynamic programming for OBST. What is the time and space complexity of such an algorithm?
7. Suggest a greedy strategy and give an algorithm (pseudo code) for OBST. What is the time and space complexity of your algorithm? Will the greedy algorithm always give an optimal solution? Justify your answer.
