Description
Question – 1
The Hadamard matrices H0, H1, H2, … are defined as follows:
• H0 is the 1 × 1 identity matrix [1].
• For k > 0, Hk is the 2
k × 2
k matrix
”
Hk−1 Hk−1
Hk−1 – Hk−1
#
(1)
Show that if v is a column vector of length n = 2k
, then the matrix-vector product Hkv can be
calculated using O(n log n) operations. Assume that all the numbers involved are small enough
that basic arithmetic operations like addition and multiplication take unit time.
Question – 2
Let T be a table of n relative integers. Give an algorithm to find the maximum sum of contiguous
elements, namely, two indices i and j ,(1 ≤ i ≤ j ≤ n) that maximizes Pj
k=i
T[k].
Question – 4
Given a binary number i with binary representation bk−1…b1b0, defined revk(i) to be the number that
has binary representation b0b1…bk−1. (Example: rev3(3) = 6 since 3 and 6 have binary representations
“011” and “110” respectively.)
Given n = 2k
, consider the problem of computing the sequence revk(0), revk(1),…, revk(n − 1).
(Example for n = 8, the output is (0,4,2,6,1,5,3,7) as the binary representations of these numbers
are 000, 100, 010, 110, 001, 101, 011, 111.)
Give an O(n)-time algorithm by using divide and conquer. (This is faster than the trivial algorithm
which reverses each number one by one in total time O(nk) = O(n log n).) Remember, arithmetic
operations involving two integers are performed in O(1) time.
Question – 5
We are given an index k and two sorted arrays A and B of sizes na and nb, respectively. Describe
an O(log(na) + log(nb) time algorithm that can find the k-th smallest element among all na + nb
elements in the two arrays. Example: If A = (3, 9, 15) and B = (2, 4, 8, 10, 11), and k = 5, the
output would be 9. You may assume that all elements are distinct. Hint: Aim for a recurrence of the
form T(N) = T(N/2) + O(1), where N = nanb. Think in terms of the product of the two arrays.
More hint: Let ma and mb be the middle elements of A and B, respectively. If k < (na + nb)/2, and
ma < mb, can we prune half of one of the arrays? What about the other cases?
Question - 6
(Computer screen display problem.) You are to design and implement a program, using divide-andconquer and runnning in time O(n log n), to display objects on the screen. To make your life simple,
all objects are rectangles and standing on the same horizontal line (say y = 0). The i-th object is
specified as (Li;Hi;Ri) where Li and Ri are its leftmost and rightmost coordinates, respectively, and
Hi is its height. The input is a sequence of triples of integers. The output should show the outline of
the objects such that hidden parts of the objects are not shown.
For example, if the input is (you can assume 3 numbers in a line, separated by spaces):
(1,11,5),(2,6,7),(3,13,9),(12,7,16),(14,3,25),(19,18,22),(23,13,29),(24,4,28)
the output should be:
(1,11), (3,13), (9,0), (12,7), (16,3), (19,18), (22,3), (23,13), (29,0)
Question - 7
You are given a pile of n coins and you may flip the first m ≤ n coins as a group.
• What is the least number of flips needed to ensure that the coins are all heads up in the worst
case?
• What is the least average number of flips needed to ensure that the coins are all heads up if
each arrangement of heads and tails occurs with uniform probability?
• What are the worst and average costs if the cost of each flip is proportional to the number of
coins flipped?
Question - 8
An m × n array A of real numbers is a Monge array if for all i, j, k, and l such that 1 ≤ i < k ≤ m
and 1 ≤ j < l ≤ n we have A[i, j] + A[k, l] ≤ A[i, l] + A[k, j]. In other words, whenever we pick
two rows and two columns of a Monge array and consider the four elements at the intersections of
the rows and columns, the sum of the upper-left and lower-right elements is less than or equal to the
sum of the lower-left and upper-right elements. For example, the following array is Monge:
10 17 13 28 23
17 22 16 29 23
24 28 22 34 24
11 13 6 17 7
45 44 32 37 23
36 33 19 21 6
75 66 51 53 34
(a). Prove that an array is Monge if and only if for all i = 1, 2, . . . , m - 1, and j = 1, 2, . . . , n - 1
we have A[i, j] + A[i + 1, j + 1] ≤ A[i, j + 1] + A[i + 1, j]. (Hint: For the "if" part, use induction
seperately on rows and columns.)
(b). The following array is not Monge. Change one element in order to make it Monge. (Hint: Use
part (a).)
37 23 22 32
21 6 7 10
53 34 30 31
32 13 9 6
43 21 15 8
(c). Let f(i) be the index of the column containing the leftmost minimum element of row i. Prove
that f(1) ≤ f(2) ≤ · · · ≤ f(m) for any m × n Monge array.
(d). Here is a description of a divide-and-conquer algorithm that computes the leftmost minimum
element in each row of an m × n Monge array A:
Construct a submatrix A’ of A consisting of the even-numbered rows of A. Recursively determine the
leftmost minimum for each row in A’. Then compute the leftmost minimum in the odd-numbered
rows of A. Explain how to compute the leftmost minimum in the odd-numbered rows of A (given that
the leftmost minimum of the even-numbered rows is known) in O(m + n) time.
(e). Write the recurrence describing the running time of the algorithm described in part (d). Show
that its solution is O(m + n log m).....solutions for upto question 15