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) Repeat the last exercise with ‘small’ replaced by ‘large’

Imitate the proof of the Master theorem to show that if T(n) ≥ c for all n ≤ n0 and T(n) ≥ aT(n/b) + f(n) where f(n) = Ω(n s ), then (a) if s > logb a, then T(n) = Ω(n s ), (b) if s < logb a, then T(n) = Ω(n logb a ), (c) if s = logb a, then T(n) = Ω(n s log n).

Solutions

Expert Solution

orchestra answered 1 year ago

Next > < Previous

Related Solutions

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:...

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...

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...

Let A be a set of real numbers. We say that A is an open set...

Let A be a set of real numbers. We say that A is an open set if for every x0 ∈ A there is some δ > 0 (which might depend on x0) such that (x0 − δ, x0 + δ) ⊆ A. Show that a set B of real numbers is closed if and only if B is the complement of some open set A

A sequence is just an infinite list of numbers (say real numbers, we often denote these...

A sequence is just an infinite list of numbers (say real numbers, we often denote these by a0,a1,a2,a3,a4,.....,ak,..... so that ak denotes the k-th term in the sequence. It is not hard to see that the set of all sequences, which we will call S, is a vector space. a) Consider the subset, F, of all sequences, S, which satisfy: ∀k ≥ 2,a(sub)k = a(sub)k−1 + a(sub)k−2. Prove that F is a vector subspace of S. b) Prove that if...

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.

Suppose that the array X consists of real numbers X[1], X[2], …, X[N]. Write a pseudocode...

Suppose that the array X consists of real numbers X[1], X[2], …, X[N]. Write a pseudocode program to compute the minimum of these numbers.

Subjects