Description

Problem 2.1. (1pt) Prove lg(𝑛!) = Θ(𝑛 log 𝑛) when 𝑛 is an odd number. You can

(1) try the similar approach like what we did in the lecture, or (2) find the answer based on the result for even numbers.

Problem 2.2. (5pts) Solve the following recurrence equations by the master theorem or any other methods that we discussed in class.

(b) 𝑇(𝑛) = 3𝑇(𝑛/9) + 𝑛⁴ lg𝑛

(d) 𝑇(𝑛) = 𝑇(𝑛 − 1) + lg𝑛 (e)𝑇(𝑛) = 2𝑇(𝑛/2 − 1)

Problem 2.3. (bonus) Compare the efficiency of the Quicksort code to either (1) the code you wrote for your data structure class; (2) the code written by Hoare in 1960 (page 185 or shown below). You should have some trials and report the performance difference, moreover, providing some reasons why we may have such performance difference.

HOARE-PARTITION(A, p, r)     x = A[p]     i = p – 1     j = r + 1     while true         repeat             j = j – 1         until A[j] ≤ x         repeat             i = i + 1

until A[i] ≥ x         if i < j

exchange A[i] with A[j]         else return j

Problem 2.4. (bonus) In slide No. 13, confirm the performance of the improved quicksort based on MEDIAN3 and small files sorted by insertion sort. You can give your best choice of M and suggest an amount of time reduction for the choice. A figure with the performance curve is helpful.