Name:________________________________________

1. (2 pts) Under what circumstances does dynamic programming give a performance advantage over the straightforward implementation of a recursive algorithm?
   
   
   
   
   
   
   
   
   
   
2. (1 pt) True or False: For the longest common subsequence problem, it takes asymptotically more time to find an actual longest common subsequence than to determine just the length of such a sequence.
   
   
   
   
3. (2 pts) Consider the implementation of the Disjoint Sets ADT that uses a linked list with a pointer from each node to the first element of the list ("rep pointer"). What are the asymptotic worst-case times for the FindSet and Union operations, assuming there have been n MakeSet operations so far?