Assignment sheet

1. Give an O(n²) algorithm to find the longest monotonically increasing subsequence of a se- quence of n numbers. (Example: given the sequence 4,8,5,7,2,9,10,1 your algorithm should output 4,5,7,9,10.)

2. Describe an O(n) time algorithm that, given a set S of n distinct numbers and a positive integer k ≤ n, determines the k numbers in S that are closest to the median of S.

3. Let X[1..n] and Y [1..n] be two arrays, each containing n numbers already in sorted order. Give an O(log n) time algorithm to find the median of all 2n elements in arrays X and Y.

4. Consider two sets A and B, each having n integers in the range from 0 to 10n. We wish to compute the Cartesian sum of A and B, defined by

C = {x + y : x ∈ A, y ∈ B}.

Note that the integers in C are in the range 0 to 20n. We want to find the elements in C and the number of times each element of C is realized as a sum of elements in A and B. Show that the problem can be solved in O(n log n) time.

5. We are given 2 positive integers a = (a_n-1a_n-2 . . . a₀) and b = (b_n-1b_n-2 . . . b₀), of n bits each, as 2 arrays A[1..n] and B[1..n], respectively. The MSB of a, that is an-1, is stored in the location A[1] and so on. Similarly with b. Give an O(n log n) algorithm to compute the array C[1..2n] that holds the integer ab (the product of a and b) in binary.