Computer Science Homework Help

1)Divide-and-Conquer is breaking a problem into a small number of _______ (12.5 Points)

1. Smaller Sub Problems
2. Pivot
3. Sieve
4. Solutions

2) What does it mean when we say that an algorithm X is asymptotically more efficient than Y? (12.5 Points)

1. X will be a better choice for all inputs
2. X will be a better choice for all inputs except small inputs
3. X will be a better choice for all inputs except large inputs
4. Y will be a better choice for small inputs

3) Show the growth of the function f(x) = x^2 + 2x^3 + 5x + 4 ; where x = 1, 2, 5 and 10. (25 Points)

4) Use the model (draw) in your text (CLRS page 18) to execute an INSERT sort on array A. (25 Points)

7 5 3 8 0 1 2

5) Use the model (draw) in your text (CLRS page 35) to execute a MERGE sort on array A. (25 Points)

7 5 3 8 0 1 2 6)Explain the design principle of Divide and Conquer in algorithms. Give and explain an example of one such algorithm.