1. If we view the selection sort as an application of "divide and conquer" strategy, what...

1. If we view the selection sort as an application of "divide and conquer"

strategy, what is the two-part partitioning of the index range [0, n)? Is it a balanced partition?

2. For the "divide and conquer" strategy for developing algorithm, do we pursue

balanced partitioning or unbalanced partitioning? Why?

3. For the quicksort, the selection of pivot determines the quality of partitioning.

Do we have any easy or cheap way for selecting a good pivot that always leads

to a very balanced partition?

Solutions

Expert Solution

1.If we see selection sort as application of divide and conquer strategey then in this the two divisions are sucth that first section includes larger element and other section includes n-1 elements.

This partitioning is not balanced partitioning as in balaced partioitoning there is an equal division or we can say that division takes place such that the algorithm runs asymtotically fast but in this division takes place like n-1,n-2 and so on.

2.We prefer balanced partitioning over unbalanced partitioning for divide and conquer starategy as if the partitioning is balanced, the algorithm runs asymptotically as fast as merge sort. If the partitioning is unbalanced, however, it can run asymptotically as slow as insertion sort.

3.If we want balanced partitioning in quick sort then pivot element should be the middle element i.e in every partiotion pivot element lies in middle.This will lead to partition such as n-1/2.

I hope my answer met all your requirements.

THANKYOU!

venereology answered 3 months ago

Next > < Previous

Related Solutions

Divide and conquer problem. Suppose we are given two sorted arrays A[1 . . . n]...

Divide and conquer problem. Suppose we are given two sorted arrays A[1 . . . n] and B[1 . . . n] and an integer k. Describe an algorithm to find the kth smallest element in the union of A and B in O(log n) time. For example, if k = 1, your algorithm should return the smallest element of A ∪ B; if k = n, your algorithm should return the median of A ∪ B.) You can assume...

Step (D) of the divide-and-conquer strategy (i.e. combine the solutions to smaller instances of the problem...

Step (D) of the divide-and-conquer strategy (i.e. combine the solutions to smaller instances of the problem to obtain the solution of the original instance) is not a necessary step for this design strategy. Mergesort is an example of such cases. Select one: True False

Create a Java Application that implements a Selection sort algorithm to sort an array of 20...

Create a Java Application that implements a Selection sort algorithm to sort an array of 20 unsorted numbers. You should initiate this array yourself and first output the array in its original order, then output the array after it has been sorted by the selection sort algorithm. Create a second Java Application that implements an Insertion sort algorithm to sort the same array. Again, output the array in its original order, then output the array after it has been sorted...

Create a Java Application that implements a Selection sort algorithm to sort an array of 20...

• You should use the divide-and-conquer strategy and write multiple functions. • You should always use...

• You should use the divide-and-conquer strategy and write multiple functions. • You should always use arrays for the data sequences. • You should always use const int to define the sizes of your arrays. a. Write a C++ program. The program first asks the user to enter 4 numbers to form Sequence 1. Then the program asks the user to enter 8 numbers to form Sequence 2. Finally, the program shall tell which sequence has a larger average. For...

In class we saw that the fast divide and conquer integer multiplication method takesO(nlog3) time. Thisis...

In class we saw that the fast divide and conquer integer multiplication method takesO(nlog3) time. Thisis because the the shifts and additions can be done in time O(n). Suppose we use a very inefficient method for doingthe shifts and additions, so these take timeO(n2). With this slower method for doing the shifts and additions, figureout how much time will the divide and conquer integer multiplication method take . You can assume that nothing elsechanges in the divide and conquer integer...

Exercise 1: (Divide and Conquer: Binary tree traversal) Write pseudocode for one of the classic traversal...

Exercise 1: (Divide and Conquer: Binary tree traversal) Write pseudocode for one of the classic traversal algorithms (preorder, inorder, and postorder) for binary trees. Assuming that your algorithm is recursive, find the number of recursive calls made.

Design and analyze a divide-and-conquer algorithm for finding the maximum element in a list: L[0: n – 1].

The following submission rules apply:· For those questions requiring programs, the solutions must be implemented using JavaScript or Java.o Appropriate self-documenting comments in the source code are mandatory, consistent with good programming practices.o Solutions must be provided in plain text so that formatting is not lost.· All answers must be provided in this document.· Sources must be given accurate and complete citations sufficient for the instructor to find and confirm them.Design and analyze a divide-and-conquer algorithm for finding the maximum...

Polynomial Multiplication by Divide-&-Conquer A degree n-1 polynomial ? (?) =Σ(n-1)(i=0) ???i = ?0 + ?1?...

Polynomial Multiplication by Divide-&-Conquer A degree n-1 polynomial ? (?) =Σ(n-1)(i=0) ???i = ?0 + ?1? + ?2?2 ... + ??−1?n-1 can be represented by an array ?[0. . ? − 1] of its n coefficients. Suppose P(x) and Q(x) are two polynomials of degree n-1, each given by its coefficient array representation. Their product P(x)Q(x) is a polynomial of degree 2(n-1), and hence can be represented by its coefficient array of length 2n-1. The polynomial multiplication problem is to...

1.Market segmentation is A. Method B. The strategy of dividing markets in order to conquer them...

1.Market segmentation is A. Method B. The strategy of dividing markets in order to conquer them C. The allocation of product D. The allocation of policy E. The allocation of service 2. Sub-market is known as A. Origin of market B. Merging of market C. Market segment of market segmentation D. Process E. Plan 3. Which is a benefit of market segmentation? A. In allocation of market budget B. In effective marketing programme C. In meeting the competition effectively D....

Subjects