代写merge-sort、代做cs,java编程、median留学生代做、代写Python/Java

日期：2019-01-21 10:17

Problem 12. (Difficulty 2) Bubblesort and oblivious merge-sort each give a sequence of

compare-exchange operations which sorts any array A[0..3]. Write down both sequences.

Problem 13. (Difficulty 4) For n distinct elements x1, x2, . . . , xn with positive weights

w1, w2, . . . , wn such that Pn

i=1 wi = 1, define the weighted median to be an index k satisfying

P

i:xi<xk

wi ≤ 1/2 and P

i:xi>xk

wi ≤ 1/2. Give an O(n) algorithm for finding the

weighted median.

Problem 14. (Difficulty 3) Suppose we are given k sorted lists, each consisting of n elements.

The multimerge problem is to merge the k lists into a single sorted list of length nk. Design an

efficient algorithm for the multimerge problem. Analyze the running time of your algorithm.

The more efficient your algorithm is in terms of its worst-case running time, the more credit

you will get.

2 Homework 1

Problem 15. (Difficulty 3) Return a list of the following functions separated by the symbol

≡or , where f ≡ g means f = Θ(g) and f  g means f = O(g). You do not need

to justify your answer. For example, if the functions are log n, n, 5n, 2

n a correct answer is

log n  n ≡ 5n  2

n

. All logarithms are in base 2. One point for each correct symbol.

Problem 16. (Difficulty 3) Solve the following recurrences. Give both O(.) and (.).

T(n) = 4T(n/3) + n,

T(n) = 3T(n/4) + n,

T(n) = 3T(n/4) + n

2

.

5

Problem 17. (Difficulty 2) Execute the Quick-Sort algorithm on the following array

[5, 2, 6, 1, 3, 4, 7]

using the last element of the array as a pivot element. Show the contents of the array after

each pass of partition.

Problem 18. (Difficulty 3) Give an algorithm running in time O(n) and space O(1) which

sorts an array of n elements in the range {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. Note that you cannot use

another array of length n for the output because you are only allowed space O(1).

Problem 19. (Difficulty 3) You are given as input an array A[1..n] containing integer

numbers from 1 to n

10. Give an O(n)-time algorithm to determine if there are two numbers

which sum to 0.