CMPE 130-02: Advanced Algorithm Design, Fall 2018, Tarng Homework1: Chapters 2, 3, 4 Due: 9/18/2018 before the class Total 20 points 1. [2 pts] (Exercise 3.1-1) Let f(n) and g(n) be asymptotically nonnegative functions. Using the basic defi nition of -notation, prove that max(f(n), g(n))-6(f(n) + g(n)) 2. 12 pts] Show that 2n3-(n3) 3. [2 pts] (Exercise 3.1-4) a)s2") , n+1 b)s- 0r2) Justify your answer. 4. [2 pts] Suppose you have algorithms with the running times listed below. (Assume these are the exact number of operations performed as a function of the input size n.) Suppose you have a computer that can perform 1012 operations per second, and you need to compute a result in at most an hour of computation. For each of the algorithms, what is the largest input size n for which you would be able to get the result within an hour a) n2 b) n3 c) 10n2 d) n log n e) 2n 5. [2 pts] (Exercise 4.4-3) Use a recursion tree to determine a good upper bound on the recurrence T(n) - 4T(n/2 + 2) + n. 6. [10 pts] Programming assignment: Insertion sort/Merge sort - Write a program to implement Insertion sort and Merge sort to sort an array