1. Given an array A[1..n] of distinct integers, the number of pairs (i, j) with i...

Transcribed Image Text:

1. Given an array A[1..n] of distinct integers, the number of pairs (i, j) with i < j and A[i]> A[j] is called the reversals of A, denoted Rev(A). a. Determine Rev (A) for A (5, 7, 10, 4, 6, 9, 8, 3) by listing all reversed pairs and count- ing them. b. What array with integers from the set {1, 2, ,n} has the highest Rev (A)? How many does it have? c. Design a "brute force" algorithm for computing Rev(A), justify its correctness, and analyze its worst-case running time. Here, the running time can be in n(n²). d. Design a divide and conquer algorithm for computing Rev(A), justify its correctness, and analyze its worst-case running time. Here, the running time is required to be in O(n lg n). Hint: Consider adapting Mergesort. Presentation: Start your answer by a section presenting the key ideas of the algorithm. Use the array A of part (a) to illustrate the working of the algorithm. Next, present a pseudo-code of the algorithm, and then justify its correctness, and analyze the running time. 1. Given an array A[1..n] of distinct integers, the number of pairs (i, j) with i < j and A[i]> A[j] is called the reversals of A, denoted Rev(A). a. Determine Rev (A) for A (5, 7, 10, 4, 6, 9, 8, 3) by listing all reversed pairs and count- ing them. b. What array with integers from the set {1, 2, ,n} has the highest Rev (A)? How many does it have? c. Design a "brute force" algorithm for computing Rev(A), justify its correctness, and analyze its worst-case running time. Here, the running time can be in n(n²). d. Design a divide and conquer algorithm for computing Rev(A), justify its correctness, and analyze its worst-case running time. Here, the running time is required to be in O(n lg n). Hint: Consider adapting Mergesort. Presentation: Start your answer by a section presenting the key ideas of the algorithm. Use the array A of part (a) to illustrate the working of the algorithm. Next, present a pseudo-code of the algorithm, and then justify its correctness, and analyze the running time.

Answer rating: 100% (QA)

The image contains a problem statement that is about devising algorithms to compute the number of reversal pairs in an array and analyzing their performances Lets break down the tasks and provide expl... View the full answer