a) (T/F) Dynamic Programming approach only works on problems with non-overlapping sub problems. b) (T/F) The difference between dynamic programming and divide and conquer techniques is that in divide and conquer sub-problems are independent. c) In a dynamic programming solution, the space requirement is always at least as big as the number of unique sub problems. d) (T/F) Suppose that there is an algorithm that merges two sorted arrays in n then the merge sort algorithm runs in O(n) e) (T/F) To determine whether two binary search trees on the same set of keys have identical tree structures, one could perform an inorder tree walk on both and compare the output lists. f) (T/F) If graph G has more than |V | 1 edges, and there is a unique heaviest edge, then this edge cannot be part of a minimum spanning tree. False. Any unique heaviest edge that is not part of a cycle must be in the MST. A graph with one edge is a counterexample. g) (T/F) If the lightest edge in a graph is unique, then it must be part of every MST. h) (T/F) If f(n) = (n log n) and g(n) = O(n 2 log n), then f(n) = O(g(n)). (T/F) The shortest path in a weighted directed acyclic graph can be found in linear time.