CS333 Assignment 2Instructor: KD [email protected] Name:• This homework is due at the beginning of the class on March 10, 2009. Timely submission ofyour homework is recommended, because there will be 10% late penalty per day.• Always try to be precise and concise. Finally, always make sure your answers are readable!1: [20 points] Using the quicksort algorithm in the textbook (pages 60 − 66), showhow to sort the following list of integers.1, 2, 3, 4, 5, 6, 7(a) [10 points] Use the first element in a (sub)list as the pivot item. Show the sorting actionsstep by step.(b) [10 points] Randomly choose an element in a (sub)list as the pivot item. Show the sortingactions step by step.2: [20 points] Do Exercise 2.6. (Algorithm: 10 points and Time complexity analysis:10 points)3: [10 points] Do Exercise 2.11.4: [10 points] The behavior of a recursive algorithm is expressed by the followingrecurrence relations.T (n) = 7T (n/5) + 10n for n > 1T (1) = 1(a) [5 points] Find T(125).(b) [5 points] What is the time complexity of this algorithm? [Hint: Refer to Theorem B.5 inAppendix B.]5: [10 points] Do Exercise 2.7.6: [10 points] You need to write a program to compute the nthFibonacci term forinput n, which is a positive integer greater than 1. Answer the following questions.1HW2 CS333Instructor: KD [email protected](a) [2 points] Will you use Algorithms 1.6 or 1.7?(b) [8 points] Justify your choice in part (a).7: [10 points] Do Exercise 1.28.8: [10 points] Do Exercise
View Full Document