Furthermore, please note that the graders will grade 2 out of the 4 questions randomly. Therefore, if the grader decides to check questions 1 and 4,and you haven’t answered question 4, you’ll lose points for question 4. Hence, please answer all the questions.
1. The Fibonacci series can be computed as follows,
F(n) = F(n − 1) + F(n − 2) (1)
In class, we showed how this can be done in O(log n) computation time. Now suppose that the definition is changed in the following way,
F′(n) = F′(n − 1) + F′(n − 2) + F′(n − 3) + F′(n − 4) (2)
Can F′(n) be computed in O(log n)? If yes, please show how it can be done. If no, show a counterexample where this fails. Please provide your rationale for both. Assume that F′(0) = 0,F′(1) = 1,F′(2) = 1,F′(3) = 1. [25 Points].
2. In class we have discussed the Quick Sort algorithm. Answer the followingquestions regarding quick sort.
• When does the worst case for Quick Sort occur?
• What would be the worst case recurrence for Quick Sort? Solve the recurrence and get its time complexity in worst case.
• What would be the best case recurrence for Quick Sort? Solve the recurrence and get its time complexity in best case.
1
• Suppose you have an algorithm which can give the median of a set on numbers in O(n) time. How can this be used to improve the worst case time complexity of Quick sort?
• In the execution of Quick sort suppose every time the n/5th element is picked as the pivot element among n elements, what would be the recurrence for quick sort? What would be its time complexity?
3. If k is a non-negative constant, then prove that the recurrence: [25 points]
T(n) = k , for n = 1 and
has the following solution (for n a power of 2):
T(n) = 3knlog23− 2kn
4. Design an algorithm to compute the 2nd smallest number in an unordered(unsorted) sequence of numbers {a1,a2,...,an} in n + ⌈log2(n)⌉− 2 comparisons in the worst case. If you think such an algorithm can be designed, then show how it can be done. If your answer is no, then explain why it cannot be done. [25 points]
2
