Hi, I need help with the following question:
Let S be a sequence of N elements on which a total order relation is defined. Recall that an inversion in S is a pair of elements x and y such that x appears before y in S but x > y. Describe an algorithm running in O(n log n) time for determining the number of inversions in S.
How to get number of inversions in
merge()?
In merge process, let i is used for indexing left sub-array and j
for right sub-array. At any step in merge(), if a[i] is greater
than a[j], then there are (mid – i) inversions. because left and
right subarrays are sorted, so all the remaining elements in
left-subarray (a[i+1], a[i+2] … a[mid]) will be greater than
a[j]
JAVA CODE
// Java implementation of counting the
// inversion using merge sort
class Test {
/* This method sorts the input array and returns
the
number of inversions in the array */
static int mergeSort(int arr[], int array_size)
{
int temp[] = new
int[array_size];
return _mergeSort(arr, temp, 0,
array_size - 1);
}
/* An auxiliary recursive method that sorts the
input array and
returns the number of inversions in the array.
*/
static int _mergeSort(int arr[], int temp[], int left,
int right)
{
int mid, inv_count = 0;
if (right > left) {
/* Divide the
array into two parts and call _mergeSortAndCountInv()
for each of the parts */
mid = (right +
left) / 2;
/* Inversion
count will be sum of inversions in left-part, right-part
and number of inversions in merging
*/
inv_count =
_mergeSort(arr, temp, left, mid);
inv_count +=
_mergeSort(arr, temp, mid + 1, right);
/*Merge the
two parts*/
inv_count +=
merge(arr, temp, left, mid + 1, right);
}
return inv_count;
}
/* This method merges two sorted arrays and returns
inversion count in
the arrays.*/
static int merge(int arr[], int temp[], int left, int
mid, int right)
{
int i, j, k;
int inv_count = 0;
i = left; /* i is index for left
subarray*/
j = mid; /* j is index for right
subarray*/
k = left; /* k is index for
resultant merged subarray*/
while ((i <= mid - 1) &&
(j <= right)) {
if (arr[i] <=
arr[j]) {
temp[k++] = arr[i++];
}
else {
temp[k++] = arr[j++];
/*this is tricky -- see above
explanation/diagram for merge()*/
inv_count = inv_count + (mid - i);
}
}
/* Copy the remaining elements
of left subarray
(if there are any) to temp*/
while (i <= mid - 1)
temp[k++] =
arr[i++];
/* Copy the remaining elements
of right subarray
(if there are any) to temp*/
while (j <= right)
temp[k++] =
arr[j++];
/*Copy back the merged elements
to original array*/
for (i = left; i <= right;
i++)
arr[i] =
temp[i];
return inv_count;
}
// Driver method to test the above function
public static void main(String[] args)
{
int arr[] = new int[] { 1, 20, 6,
4, 5 };
System.out.println("Number of
inversions are " + mergeSort(arr, 5));
}
}
Hi, I need help with the following question: Let S be a sequence of N elements...
Can i please get help with problem 3? please, if possible, answer in a text format. JN/2) f(n/2); f(n/2); f(n/2); Problem 3. Let A[O...n-1) be an array of n distinct integers. A pair (Ali), A[]) is said to be an inversion if these numbers are out of order, i.e., i<j but A[i] > AG). Design a O(n log n) time algorithm for counting the number of inversions.
ALGORITHM PROBLEM: A) Significant Inversions: We are given a sequence of n arbitrary but distinct real numbers <a1 , a2 ,..., an>. We define a significant inversion to be a pair i < j such that ai > 2 aj . Design and analyze an O(n log n) time algorithm to count the number of significant inversions in the given sequence. [Hint: Use divide-&-conquer. Do the “combine” step carefully] B) The Maximum-Sum Monotone Sub-Array Problem: Input: An array A[1..n] of...
4. (10 points) Suppose we are given a sequence S of n elements, each of which is colored red or blue. Assuming S is represented by an array, give a linear-time in-place algorithm for ordering S so that all the blue elements are listed before all the red elements. What is the running time of your method?
maybe use induction to prove? Problem 2: Let p-p.Pn be a permutation considered in its one-line notation. An inversion in p is a pair 1 i<jS n such that j appears to the left of i in p (i.e., an out-of-order pair). Let inv(p) be the total number of inversions in p. Prove that PES where z is a variable. Problem 2: Let p-p.Pn be a permutation considered in its one-line notation. An inversion in p is a pair 1...
1) Design a greedy algorithm that solves the problem; describe your algorithm with clear pseudocode; and prove the time efficiency class of your algorithm: If x, y are two adjacent elements in a sequence, with x before y, we say that the pair x, y is in order when x <= y and the pair is out of order when x > y. For example, in the string “BEGGAR” the pair G, A are out of order, but all the...
Question3 10 pts Let A [L.n] be a max-heap with n > 1 and consider the index ị such that l 〈 i 〈 n . Assume that all the elements of A are distinct. Write the pseudocode of an algorithm which replaces A [i] by A i 100 and then re-arranges the elements of A into a max-heap. The running time of your algorithm must be O (log, n Upload Choose a File Question3 10 pts Let A [L.n]...
I already solved part A and I just need help with part B 1. Matrix Multiplication The product of two n xn matrices X and Y is a third n x n matrix 2 = XY, with entries 2 - 21; = xixYk x k=1 There are n’ entries to compute, each one at a cost of O(n). The formula implies an algorithm with O(nº) running time. For a long time this was widely believed to be the best running...
56. Let S = N × N and let ρ be a binary relation on şdefined by (x,y)ρ(z, w)艹x + y-z + w. Show that p is an equivalence relation on S and describe the resulting equivalence classes.
4. Ranking/Unranking Subsets. Let A be a set of n elements and set Sk(A) be the collection of all k-element subsets of A. Recall that |Sk(A)I - (a.) (8 points) Describe a ranking algorithm to rank a k-element subset of an n-element set. (b.) (8 points) Describe an unranking algorithm to unrank an integer 0 < s< [into a ithm to unrank an integer 0 S s <C) k-element subset of an n-element set. (c.) (10 points) As examples, let...
(20 points) Recall the following deterministic select algorithm: (a) Divide the n elements into groups of size 5. So n/5 groups. (b) Find the median of each group. (c) Find the median x of the n/5 medians by a recursive call to Select. (d) Call Partition with x as the pivot. (e) Make a recursive call to Select either on the smaller elements or larger elements (de- pending on the situation); if the pivot is the answer we are done....