Instructions: Atop your problem set, write your name and whether you are an unde
ID: 3670164 • Letter: I
Question
Instructions: Atop your problem set, write your name and whether you are an undergraduate or graduate student. Also write the names of all the students with whom you have collaborated on this problem set. 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 You are given two arrays, A and B, each of which contains n integers. The elements in each array are guaranteed to be in sorted order, 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 D. (We define the median of In numbers to be the average of the nth smallest and nth largest values.) Argue that your algorithm is correct and give its running time. You get as input n distinct positive integers a_1,... ,a_n. Give an O(n log n) algorithm to count the number of pairs i less than j where a_i less than 2a_j. You are given a 2^K times 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.) On the left is an example grid with a missing cell, with k - 3. In the middle is the "L-shaped" tile, to be used for tiling. On the right is an example solution.Explanation / Answer
Question 3
you get as input n distinct positive integers a1,...an O(n log n) algorithm for to the count numb er of pairs i<j where ai>2aj
Answer
1. Sort the array using Heapsort or Mergesort, worst case O(nlogn).
2. i = 1; j = n
3. while i != j do O(n)
if A[i] * A[j] = t then print (A[i], A[j]) and i++ and j--
if A[i] * A[j] > t then j--
if A[i] * A[j] < t then i++
We sort the array and look at the largest and smallest numbers, if their product is equal to t, we output the two indices. Otherwise, if the product is bigger than t, that means we need smaller numbers, so we decrease j to get to a smaller number in the array. Otherwise, the product is less than t, we need a bigger number and we increase I to get to a bigger number.It runs in O(nlogn + n) = O(nlogn)