Prove that the merge sort algorithm is correct.The quick

Problem 55E Determine the worst-case complexity of the quick sort algorithm in terms of the number of comparisons used.

Problem 1E Trace Algorithm 1 when it is given n = 5 as input. That is, show all steps used by Algorithm 1 to find 5!, as is done in Example 1 to find 4!.

Problem 2E Trace Algorithm 1 when it is given n = 6 as input. That is, show all steps used by Algorithm 1 to find 6!. as is done in Example 1 to find 4!.

Problem 4E Trace Algorithm 3 when it finds gcd(12. 17). That is. show all the steps used by Algorithm 3 to find gcd(12. 17).

Problem 5E Trace Algorithm 4 when it is given m = 5, n = 11, and b = 3 as input. That is, show all the steps Algorithm 4 uses to find 311 mod 5.

Problem 3E Trace Algorithm 3 when it finds gcd(8,13). That is. show all the steps used by Algorithm 3 to find gcd(8, 13).

Problem 6E Trace Algorithm 4 when it is given m =7, n = 10, and b = 2 as input. That is, show all the steps Algorithm 4 uses to find 210mod 7.

Problem 7E Give a recursive algorithm for computing nx whenever n is a positive integer and x is an integer, using just addition.

Problem 9E Give a recursive algorithm for finding the sum of the first n odd positive integers.

Problem 8E Give a recursive algorithm for finding the sum of the first n positive integers.

Problem 10E Give a recursive algorithm for finding the maximum of a finite set of integers, making use of the fact that the maximum of n integers is the larger of the last integer in the list and the maximum of the first n — 1 integers in the list.

Problem 11E Give a recursive algorithm for finding the minimum of a finite set of integers, making use of the fact that the minimum of n integers is the smaller of the last integer in the list and the minimum of the first n — 1 integers in the list.

Problem 13E Give a recursive algorithm for finding n! mod m whenever n and m are positive integers.

Problem 16E Prove that the recursive algorithm for finding the sum of the first n positive integers you found in Exercise 8 is correct.

Problem 15E Devise a recursive algorithm for computing the greatest common divisor of two nonnegative integers a and b with a

Problem 17E Describe a recursive algorithm for multiplying two non- negative integers x and y based on the fact that xy = 2(x · (y/2)) when y is even and xy = 2(x· [y/2]) +x when y is odd. together with the initial condition xy = 0 when y = 0.

Problem 14E Give a recursive algorithm for finding a mode of a list of integers. (A mode is an element in the list that occurs at least as often as every other element.)

Problem 18E Prove that Algorithm 1 for computing n! when n is a non- negative integer is correct.

Problem 19E Prove that Algorithm 3 for computing gcd(a, b) when a and b are positive integers with a

Problem 20E Prove that the algorithm you devised in Exercise 17 is correct.

Problem 21E Prove that the recursive algorithm that you found in Exercise 7 is correct.

Problem 22E Prove that the recursive algorithm that you found in Exercise 10 is correct.

Devise a recursive algorithm to find \(a^{2^{n}}\), where \(a\) is a real number and \(n\) is a positive integer. [Hint: Use the equality \(\left.a^{2^{n+1}}=\left(a^{2^{n}}\right)^{2} .\right]\) Equation Transcription: Text Transcription: a^2n a^2n-1=(a^2n)^2

Problem 23E Devise a recursive algorithm for computing n2 where n is a nonnegative integer, using the fact that (n + 1)2 = n2 + 2n + 1. Then prove that this algorithm is correct.

How does the number of multiplications used by the algorithm in Exercise 24 compare to the number of multiplications used by Algorithm 2 to evaluate \(a^{2^{n}}\)? Equation Transcription: Text Transcription: a^2n

Problem 26E Use the algorithm in Exercise 24 to devise an algorithm for evaluating an when n is a nonnegative integer. [Hint: Use the binary expansion of n.]

Problem 27E How does the number of multiplications used by the algorithm in Exercise 26 compare to the number of multiplications used by Algorithm 2 to evaluate an?

Problem 28E How many additions are used by the recursive and iterative algorithms given in Algorithms 7 and 8, respectively, to find the Fibonacci number f7?

Problem 29E Devise a recursive algorithm to find the n th term of the sequence defined by a0 = 1 ,a1 =2, and an = an-1 · an-2 , for n = 2,3,4.......

Problem 30E Devise an iterative algorithm to find the nth term of the sequence defined in Exercise 29.

Problem 31E Is the recursive or the iterative algorithm for finding the sequence in Exercise 29 more efficient?

Problem 32E Devise a recursive algorithm to find the nth term of the sequence defined by a0 =1, a1 =2, a2 = 3, and an = an-1 + an-2 + an-3 , for n = 3, 4, 5.....

Problem 33E Devise an iterative algorithm to find the 71th term of the sequence defined in Exercise 32.

Problem 34E Is the recursive or the iterative algorithm for finding the sequence in Exercise 32 more efficient?

Problem 36E Give a recursive algorithm to find the number of partitions of a positive integer based on the recursive definition given in Exercise 47 in Section 5.3.

Give iterative and recursive algorithms for finding the nth term of the sequence defined by \(a_{0}=1, a_{1}=3, a_{2}=5\), and \(a_{n}=a_{n-1} \cdot a_{n-2}^{2} \cdot a_{n-3}^{3}\). Which is more efficient? Equation Transcription: Text Transcription: a_0= 1, a_1 = 3, a_2 = 5 a_n = a_n-1 dot a_n-2^2 dot a_n-3^3

Problem 37E Give a recursive algorithm for finding the reversal of a bit string. (See the definition of the reversal of a bit string in the preamble of Exercise 34 in Section 5.3.)

Problem 38E Give a recursive algorithm for finding the string wi, the concatenation of i copies of w, when w is a bit string.

Problem 39E Prove that the recursive algorithm for finding the reversal of a bit string that you gave in Exercise 37 is correct.

Problem 40E Prove that the recursive algorithm for finding the concatenation of i copies of a bit string that you gave in Exercise 38 is correct.

Problem 41E Give a recursive algorithm for tiling a 2n × 2n checkerboard with one square missing using right triominoes.

Problem 43E Give a recursive algorithm for computing values of the Ackermann function. [Hint: See the preamble to Exercise 48 in Section 5.3.]

Problem 44E Use a merge sort to sort 4,3,2,5, 1,8,7,6 into increasing order. Show all the steps used by the algorithm.

Problem 45E Use a merge sort to sort b, d, a, f, g, h, z, p, o, k into alphabetic order. Show all the steps used by the algorithm.

Problem 46E How many comparisons are required to merge these pairs of lists using Algorithm 10? a) 1,3,5,7,9:2,4,6,8, 10 ________________ b) 1,2, 3, 4, 5; 6, 7, 8, 9, 10 ________________ c) 1,5, 6, 7, 8; 2, 3, 4,9, 10

Problem 47E Show that for all positive integers m and n there are sorted lists with m elements and n elements, respectively, such that Algorithm 10 uses m + n ? 1 comparisons to merge them into one sorted list.

Problem 48E What is the least number of comparisons needed to merge any two lists in increasing order into one list in increasing order when the number of elements in the two lists are a) 1.4? ________________ b) 2, 4? ________________ c) 3, 4? ________________ d) 4, 4?

Problem 49E Prove that the merge sort algorithm is correct. The quick sort is an efficient algorithm. To sort a1 ,a2 ,…,an this algorithm begins by taking the first element a1 and forming two sublists, the first containing those elements that are less than a1, in the order they arise, and the second containing those elements greater than a1, in the order they arise. Then a1 is put at the end of the first sublist. This procedure is repeated recursively for each sublist, until all sublists contain one item. The ordered list of n items is obtained by combining the sublists of one item in the order they occur.

Problem 50E Sort 3, 5, 7, 8, 1,9, 2, 4, 6 using the quick sort.

Problem 51E Let a1 ,a2 ,........an be a list of n distinct real numbers.How many comparisons are needed to form two sublists from this list, the first containing elements less than a1 and the second containing elements greater than a1?

Problem 52E Describe the quick sort algorithm using pseudocode.

Problem 53E What is the largest number of comparisons needed to order a list of four elements using the quick sort algorithm?

Problem 54E What is the least number of comparisons needed to order a list of four elements using the quick sort algorithm?