CMSC 435 Algorithm Analysis & Design

Homework # 4

Due October 2

1. Prove by induction that for an N x N board with a deficiency, where N = 2^m, the number of non-deficient squares is divisible by 3. This is a necessary condition for a tiling with trominoes. Hint! See discussion in Example 3 of the lecture on Divide and Conquer.

2. Prove that a tiling with trominoes exists for any N x N board with a deficiency, where N = 2^m. Hint! Prove by induction. The base case is m = 1. Use the algorithm developed in the book and lecture notes in your proof. (The first problem statement is a necessary condition for this to be true, but it is not used in this proof.)

3. Give a tiling of a 5 x 5 board with trominoes in which the upper left square of the board is missing.

4. Show a 5 x 5 board with one deficiency that is impossible to tile with trominoes. Prove that this board cannot be tiled with trominoes.

5. Write an O(n) algorithm that, given an array A consisting of a sorted subarray of size m followed by a sorted subarray of size n, merges them into A using an extra array of size min{m,n}.

6. Write an O(n) algorithm that computes the union A È B of two n-element sets A and B of integers. The sets are represented as arrays sorted in non-decreasing order.

7. Given two N x N matrices A and B, where N = 2^m, divide each into quadrants A₁₁, A₁₂, A₂₁, A₂₂, and similarly for B. What is the product matrix in terms of these quadrants? Show that Strassen's algorithm produces this same product.

8. Show how Strassen's algorithm computes the matrix product of

| 3 1 0 2| |2 -5 1 2|

| 4 -1 1 1| |0 -3 -1 3|

| 1 1 -2 0| |1 2 3 5|

|-1-1 1 4| |3 1 -2 3|