算法问题集作业代写 CSCI 3104代写

CSCI 3104

Problem Set 10

Standard 19- Divide and Conquer: Principles and Algorithm Design

Problem 1. Suppose we are given n Boolean variables x₁, . . . , x_n, and we wish to evaluate:

Problem 2. Consider the following algorithm. Assume that, as a precondition, 2 ≤ k ≤ n − 1. Is this algorithm guaranteed to sort A? If so, carefully explain why. If not, give a counter-example. [Note: It may be helpful, as scratch work, to implement this algorithm and test it on several random arrays.]

Algorithm 1 Sort

1: procedure Sort(ArrayA[1, . . . , n],Integer k)
2:   for i ← 1;i ≤ n − k + 1;i ← i + 1 do 
3:     Mergesort(A[i, . . . , i + k − 1])
4:

Standard 20- Divide and Conquer: Quicksort, Modifications, and Analysis 算法问题集作业代写

Problem 1 (a) and (b)

(a) Write down a recurrence Tbest(n) that models the runtime of Quicksort, assuming that the Partition algorithm always selects the median element. Don’t forget to include your base case.

(c) Suppose that we modify Partition(A, s, e) so that it chooses the median element of A[s..e] in calls that occur in nodes of even depth of the recursion tree of a call Quicksort(A[1, . . . , n], 1, n), and it chooses the maximum element of A[s..e] in calls that occur in nodes of odd depth of this recursion tree.

Assume that the running time of this modified Partition is still Θ(n) on any subarray of length n. You may assume that the root of a recursion tree starts at level 0 (which is an even number), its children are at level 1, etc.

Your job is to write down a recurrence relation for the running time of this version of Quicksort given an array n distinct elements and solve it asymptotically, i.e. give your answer as Θ(f(n)) for some function f. Show your work.

Standard 21- Applications of Quicksort 算法问题集作业代写

Problem. The

Quickselect(A[1, . . . , n],Integer start,Integer end,Integer k)

algorithm is an adaptation of Quicksort, which we use to find the kth smallest element in an array A of length n. The initial steps of Quickselect are identical to Quicksort in that Quickselect partitions the input array around a pivot element. So we have left and right subarrays after partitioning the original array A. Suppose the sub-arrays have sizes:

len(left) = m.
len(right) = n − m − [Note that the −1 term comes from accounting for the pivot element. So n = len(left) + len(right) + 1 = m + (n − m − 1) + 1.]

The trick now comes down to determining which piece to look at. We note that A is partitioned as follows:

A = [left|pivot|right].

Observe the following. 算法问题集作业代写

If len(left) ≥ k, then we know the kth smallest element of A must be in left. In particular, the kth smallest element of A is also the kth smallest element of left. So we recurse, using Quickselect to search for the kth smallest element in left.
If k = len(left)+ 1, then the kth smallest element in A is pivot, so we return pivot. The algorithm terminates.
If k > len(left) + 1, then the kth smallest element in A must be in right. In particular, the kth smallest element of A is the k−1−len(left) smallest element of right [This is because the len(left)+1 smallest elements of A are the pivot and elements of left). So we recurse, using Quickselect to search for the k − 1 − len(A) smallest element in right.

Do the following. 算法问题集作业代写

Consider the initial input array A = [3, 7, 2, 9, 1, 6, 8, 4]. In the first call to Quickselect, the algorithm partitions A as follows:

A = [3, 2, 1|4|7, 6, 8, 9],

where left = [3, 2, 1] and right = [7, 6, 8, 9].

(a) Suppose we wanted to find the 4th smallest element. What would the algorithm’s next step be after this partitioning? [Note: If the next step is to recurse on a sub-array, it suffices to state this and specify the parameters of the recursive call.]

(b) Suppose we wanted to find the 6th smallest element instead of the 3rd smallest element. What would the algorithm’s next step be after this partitioning? [Note: If the next step is to recurse on a sub-array, it suffices to state this and specify the parameters of the recursive call.]

(c) What pivot element should be selected at each recursive call, in order for Quickselect to achieve its best possible runtime? Give a 1-2 sentence justification.

合作平台：essay代写论文代写写手招聘英国留学生代写