Homework 3

1. Problem 4-1: Recurrence examples
   Give asymptotic upper and lower bounds for T(n) in each of the following recurrences. Assume that T(n) is constant for n≤2. Make your bounds as tight as possible, and justify your answers.

   • 
   • 
   • 
   • 
   • 第十七組

2. Problem 4-3: More recurrence examples
   Give asymptotic upper and lower bounds for T(n) in each of the following recurrences. Assume that T(n) is constant for sufficiently small n. Make your bounds as tight as possible, and justify your answers.

   • 
   • 
   • 
   • 
   • 
   • 第十組

3. Exercise 4.5-4:
   Can the master method be applied to the recurrence ? Why or why not? Give an asymptotic upper bound for this recurrence.

   • 第六組

4. In chapter 4.1 (p.68), the author converts the stock buying problem into the maximum-subarray problem, then solves the problem with a divide-and-conque algorithm which takes Θ(nlogn) time. Design a O(n)-time algorithm that solves the stock buying problem without transformation.

   • 第二組

5. Analyze best-case, average-case, and worst-case performance of the following pseudocode which describes a sorting algorithm and determine whether it is in place and whether it is stable. Append your analyzing process or reasons.

   • 第十八組

sort(first, last) # pass by address
    swap first and last if last.value < first.value
    size = last - first + 1
    if size >= 3
        offset = size / 3
        sort(first, last - offset)
        sort(first + offset, last)
        sort(first, last - offset)