1. A triomino is an L-shaped tile formed by three adjacent squares of a chess board.

The trinomino puzzle problem is to cover any 2n-by-2n  chessboard with one missing square (anywhere on the board) with triominos. Triominos should cover all the squares except the

missing one with no overlaps.

Design a divide-and-conquer algorithm for this problem. Describe your main steps (divide, conquer, combine) informally in plain English and illustrate by drawings where appropriate. [0:20h expected time] [6 marks]

2. Give asymptotic upper bound for T (n) in each of the following recurrences.  Assume that T (n) = n for n ≤ 2.  Select the tightest bound from the available options, and the method you used to obtain it.

(a) T (n) = T (n - 1) + 1                                  (i) T (n) = (T (^n))2

(b) T (n) = T (n/2) + 1

(c) T (n) = T (^n) + 1

(j) T (n) = 4T (n/2) + n

(k) T (n) = 8T (n/4) + n logn

(d) T (n) = 2T (n - 1)

(e) T (n) = 2T (n/2)

(f) T (n) = 2T (^n)

(l) T (n) = 27T (n/9) + n2

(m) T (n) = T (8n/9) +^n

(n) T (n) = 5T (n/25) +^n

(g) T (n) = (T (n - 1))2

(h) T (n) = (T (n/2))2

(o) T (n) = T (2n/3) + log n.

[1:00h expected time] [15 marks]