1. [10 Points] State whether TRUE or FALSE

A. The merge is where most of the work is done in the Mergesort algorithm.

B. In the Quicksort algorithm, the subproblem sizes may be disproportionate.

C. The Dynamic Programming solution to a problem could be optimal even though the solutions to some subproblems are not optimal.

D. The Dynamic Programming method yields the optimal solution in polynomial time.

E. The Optimal Binary Search Tree (OBST) is always a balanced tree.

F. The average number of comparisons for a key on a successful search may not always be the smallest possible in an OBST.

G. Floyds algorithm always gives the optimal solution.

H. The Dynamic Programming method solves several overlapping subproblems.

I. A 1 in the Rmatrix of Warshalls algorithm may change to a 0 in a subsequent iteration.

J. The final matrix (transitive closure) produced by Warshalls algorithm is still a binary matrix.