You are given a one dimensional array that may contain both

Question

Q1. You are given a one dimensional array that may contain both positive and negative integers. Give an O(n log n) algorithm to find the sum of contiguous (ie. next to one another, in sequence) sub-array of numbers which has the largest sum. For example, if the given array is [-2, -5, 6, -2, -3, 1, 5, -6], then the maximum sub array sum is 7 (the sub array is marked in boldface). Argue that your algorithm is correct.

You get as input n distinct positive integers a₁, . . . , a_n. Give an O(n log n) algorithm to count the number of pairs i < j where a_i > 2a_j.

Q2. You are given two arrays, A and B, each of which contains n integers. The elements in each array are guaranteed to already be in sorted order in the input, i.e.

A[0] ≤ A[1] ≤ . . . ≤ A[n - 1],

and also

B[0] ≤ B[1] ≤ . . . ≤ B[n - 1].

Give as fast an algorithm as you can for finding the median value of all the 2n numbers in both A and B. (We define the median of 2n numbers to be the average of the nth smallest and nth largest values.) Argue that your algorithm is correct and give its running time.

Q3. You are given an array X of n elements. A majority element of X is any element occurring in more than n/2 positions. The only access you have to the array is to compare any two of its elements for equality; hence you cannot sort the array, etc. Design an O(n log n) divide-and-conquer algorithm to find a majority element in X (or determine that no majority element exists).

Q4. You are given a 2^k x 2^k board with one missing cell. Give an O(2^2k)-time algorithm for filling the board with "L-shaped" tiles. (See Figure 1 below.)

5. Consider you get as input a very sparse undirected weighted graph G = (V, E), in particular for which [E] - [V] = 20. Give an O(|V|) time algorithm for finding a minimum spanning tree on G and prove your algorithm correct.

Note - Question 1 has 2 different separate questions (Part A and B) with 2 different solutions.