Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CS566 Homework-2

(1) [10 pts] A sorting algorithm takes 1 second to sort 1,000 items on your local machine.  How long will it take to sort 10,000 items

(a) if you believe that the algorithm takes time proportional to n², and

(b) if you believe that the algorithm takes time roughly proportional to n log n?

What are the theta values for the recurrences given below in Q2-Q8?  

Show your work in details

Hint:  use Master Theorem or Substitution method

(2) [5 pts.] T(n) = 2T(n/2) + n**3

(3) [5 pts.] T(n) = T((9/10) n)  + n

(4) [5 pts.] T(n) = 16T(n/4) + n**2

(5) [5 pts.] T(n) = 7T(n/3) + n**2

(6) [5 pts.] T(n) = 2T(n/4) + SQRT(n), where SQRT means “square root”

(7) [10 pts] T(n) = T(n-1) + n

(8) [15 pts.] T(n) = 2T(n-1) + 1, T(1)=1

 (9) [15 pts.] How many inversions (swaps) requires to sort the following lists?

A pair of elements (p_i, p_j) is called an inversion in a list permutation p if  i > j and  p _i  <  p_j.

Show your work in details, name a sorting algorithm in use

(a) (5,2,3,4,1)

(b) (1,2,3,4,5)

(c) (5,1,2,3,4)

(10) [25 pts.]

Let us consider the easiest sorting algorithms – Maxsort.

It works as follows: Find the largest key, say max, in the unsorted section of array (initially the whole array) and then interchange max with the element in the last position in the unsorted section. Now max is considered part of the sorted section consisting of larger keys at the end of the array. It is no longer in the unsorted section. Repeat this until the whole array is sorted.

a) Write an algorithm for Maxsort assuming an array E contains n elements to be sorted,

      with indexes 0, 1,…,n-1.

b) How many comparisons of keys does Maxsort do in the worst case and on average?

Submit source code, test cases, results, and the answers to part (b).