Given an array A of n distinct numbers, we say that a pair of numbers i,...

Given an array A of n distinct numbers, we say that a pair of numbers i, j ∈ {0, . . . , n − 1} form an inversion of A if i < j and A[i] > A[j]. Let inv(A) = {(i, j) | i < j and A[i] > A[j]}. Define the Inversion problem as follows: • Input: an array A consisting of distinct numbers. • Output: the number of inversions of A, i.e. |inv(A)|. Answer the following: (a) How small can the number of inversions be? Give an example of an array of length n with the smallest possible number of inversions. (b) Repeat the last exercise with ‘small’ replaced by ‘large’. (c) Show that the running time of insertion sort on array A is Θ(|inv(A)| + n). (d) Assume that the array A contains the number 1, . . . , n in a uniformly random order (among all the n! many orderings). In this case, the running time of insertion sort on A becomes a random variable T. Calculate T up to constant factors.

Define the Exponentiation problem as follows. • Input: A number a and an integer n. • Output: a n . Design an algorithm to solve the problem with as few multiplications as possible

Solutions

Expert Solution

orchestra answered 1 year ago

Next > < Previous

Related Solutions

Given an array A of n distinct real numbers, we say that a pair of numbers...

Given an array A of n distinct real numbers, we say that a pair of numbers i, j ∈ {0, . . . , n−1} form an inversion of A if i < j and A[i] > A[j]. Let inv(A) = {(i, j) | i < j and A[i] > A[j]}. Answer the following: (a) How small can the number of inversions be? Give an example of an array of length n with the smallest possible number of inversions. (b)...

Given an array A[1..n], with distinct values and k with 1 ≤ k ≤ n. We...

Given an array A[1..n], with distinct values and k with 1 ≤ k ≤ n. We want to return the k smallest element of A[1.....n], in non-decreasing order. For example: A = [5, 4, 6, 2, 10] and k = 4, the algorithm returns [2, 4, 5, 6]. There are at least the following four approaches: a. heapify A and then extract k elements one by one b. sort the array (e.g. using MergeSort or HeapSort) and then read the...

An array A of n distinct numbers are said to be unimodal if there exists an...

An array A of n distinct numbers are said to be unimodal if there exists an index k, 1 ≤ k ≤ n, such that A[1] < A[2] < · · · < A[k − 1] < A[k] and A[k] > A[k + 1] > · · · > A[n]. In other words, A has a unique peak and are monotone on both sides of the peak. Design an efficient algorithm that finds the peak in a unimodal array of...

Project: Given an array numbers. We define a running sum of an array as runningSum[i] =...

Project: Given an array numbers. We define a running sum of an array as runningSum[i] = sum(nums[0]…nums[i]). Return the running sum of numbers. Example: Input: nums = [1,2,3,4] Output: [1,3,6,10] Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4]. You need to do: Create a class called RunningSumArray to perform the main method. Create a class called ArrayOperationto hold the actions for array. In this project, you will need 4methods: 1. Public static Int[] getArray() --- inside ArrayOperationclass,...

You are given an array of length n that is filled with two symbols (say 0...

You are given an array of length n that is filled with two symbols (say 0 and 1); all m copies of one symbol appear first, at the beginning of the array, followed by all n − m copies of the other symbol. You are to find the index of the first copy of the second symbol in time O(logm). include: code, proof of correctness, and runtime analysis

5. Suppose you are given an n-element array containing distinct integers that are listed in increasing...

5. Suppose you are given an n-element array containing distinct integers that are listed in increasing order. Given a number k, describe a recursive algorithm to find two integers in A that sum to k, if such a pair exists. What is the running time of your algorithm? Java Language....

Suppose you are given an n-element array containing distinct integers that are listed in increasing order....

Suppose you are given an n-element array containing distinct integers that are listed in increasing order. Given a number k, describe a recursive algorithm to find two integers in A that sum to k, if such a pair exists. What is the running time of your algorithm?

Given an array A[1..n] of integers - all of whose numbers are in the range [0,...

Given an array A[1..n] of integers - all of whose numbers are in the range [0, n^3 − 1] give an algorithm which sorts them in O(n) time.

Let P = (p1,...,pn) be a permutation of [n]. We say a number i is a...

Let P = (p1,...,pn) be a permutation of [n]. We say a number i is a fixed point of p, if pi = i. (a) Determine the number of permutations of [6] with at most three fixed points. (b) Determine the number of 9-derangements of [9] so that each even number is in an even position. (c) Use the following relationship (not proven here, but relatively easy to see) for the Rencontre numbers: Dn =(n-1)-(Dn-1 +Dn-2) (∗) to perform an...

Given an array of numbers, find the index of the smallest array element (the pivot), for...

Given an array of numbers, find the index of the smallest array element (the pivot), for which the sums of all elements to the left and to the right are equal. The array may not be reordered. Example arr=[1,2,3,4,6] the sum of the first three elements, 1+2+3=6. The value of the last element is 6. Using zero based indexing, arr[3]=4 is the pivot between the two subarrays. The index of the pivot is 3. Function Description Complete the function balancedSum...

Subjects