Write pseudocode for a divide-and-conquer algorithm for finding the position of

Question

Write pseudocode for a divide-and-conquer algorithm for finding the position of the largest element in an array of n numbers. b. What will be your algorithm's output for arrays with several elements of the largest value? c. Set up and solve a recurrence relation for the number of key comparisons made by your algorithm. d. How does this algorithm compare with the brute-force algorithm for this problem? a. Write pseudocode for a divide-and-conquer algorithm for finding values of both the largest and smallest elements in an array of n numbers. b. Set up and solve (for n = 2^k) a recurrence relation for the number of key comparisons made by your algorithm. c. How does this algorithm compare with the brute-force algorithm for this problem? a. Write pseudocode for a divide-and-conquer algorithm for the exponentiation problem of computing an where a is a^n positive integer. b. Set up and solve a recurrence relation for the number of multiplications made by this algorithm. c. How does this algorithm compare with the brute-force algorithm for this problem? Find the order of growth for solutions of the following recurrences. a. T(n) = 4T(n/2) + n, T(l) = 1. b. T(n) 4T(n/2) + n^2, T(l) = 1. c. T(n) = 4T(n/2) + n^2, T(l) = 1. Apply mergesort to sort the list E, X, A, M, P, L, E in alphabetical order. Apply quicksort to sort the list E, X, A, M, P, L, E in alphabetical order. Draw the tree of the recursive calls made.in alphabetical order. Draw the tree of the recursive calls made.

Explanation / Answer

5.5.1.6

EXAMPLE

E

X

A

M

P

L

E

Now let us find middle to divide array in two parts

Mid = (l + r)/2

Mid = (0+6)/2 = 3

Hence M is the middle position

E

X

A

M

P

L

E

First Divide EXAMPLE

EXAM   PLE

Second Divide EXAM and PLE

EX   AM    PL   E

Now divide further until single letter comes

E X A M P L E

Now start merging after comparison in the same order as we had divided

E<X     A<M P>L   E

EX    AM       LP      E

Now compare EX AM and then LP and E

AEMX      ELP

Now merge these two

AEEMLPX

E

X

A

M

P

L

E

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.