TESTI CS 425 (Theory of Algorithms) All questions must be answered. (15 pts) 1. Multiple Choice Questions i) Given a set of 1000 random data. Which algorithm will have highest runtime for this case, or will have the worst performance? a) Selection sort b) Insertion Sort c) Merge Sort d) Quick Sort ii) Given 64 unsorted data, and you are using Merge Sort to sort them. How many logical operations will be needed to sort them. a) About 60 b) About 400 c) About 2000 d) About 4000 iii) Given 100 integer data as, 0, 1, 2,3,4,5,6,... 100 If you use Quick Sort (using last element as the pivot), what would be the runtime? a) About 100 b) About 5000 c) About 700 d) None of the above iv) Which algorithm will take shortest runtime to sort the following data: 5, 10, 20, 40, 80, 100, 120, 300, 350, 450, 600 a) Selection b) Insertion c) Merge d) Quick v) Which of the following arrangement is a max heap? 0 (10 pts) 2. Given the following function: int F(int N) 1) return 2; if (Ns= 0 11 N else return N F(N-2); Show steps to find out F(5) Also give the runtime (in terms of number of recursive calls) 3. Illustrate Insertion Sort algorithm to sort the following data: (15 pts) 24 10 16 20 2 Give proper explanation and compute the runtime. Runtime Explanatiorn AII)