READ THE INSTRUCTIONS CAREFULLY AND ANSWER THE BELOW ATTACHED QUESTION CLEARLY:

If your solution uses dynamic programming, we need you to provide the following: (a) If there is any preprocessing stage before mentioning subproblem definition, state that. If the preprocessing algorithm uses something known from some tutorial or some earlier course, e.g. DSA, then just mention that as a subroutine. No need to describe that. (b) A precise description of the subproblems you want to solve in the dynamic program. Notice this is just the subproblem, not how to solve it, or how it was obtained. (c) A recurrence which relates a subproblem to smaller (whatever you define smaller to mean) subproblems. Notice this is just the recurrence, not the algorithm or why the recurrence is correct. (d) Identify the subproblem that solves the original problem (e) A description of your dynamic programming algorithm which solves the recurrence efficiently. The description must be in English containing mathematical symbols or it can be a pseudocode in plain text. A C++/Java program etc with variable declaration etc will not be accepted. You do not need to prove correctness of the pseudocode (f) An argument for the running time of your dynamic algorithm.

If your solution uses divide and conquer paradigm, then we need you to provide the following. (a) If there is any preprocessing stage before mentioning subproblem definition, state that. If the preprocessing algorithm uses something known from some tutorial or some earlier course, e.g. DSA, then just mention that as a subroutine. No need to describe that. (b) A precise description of the subproblems, i.e. how you divide the actual problem into smaller subproblems. (c) A precise description on how you combine the solutions of the subproblems to solve the actual problem. (d) A description of your complete recursive algorithm. You can refer to the subroutines of (a) and (b). The description must be in English containing mathematical symbols or it can be a pseudocode in plain text. A C++/Java program etc with variable declaration etc will not be accepted. (e) Analysis of running time of the algorithm including a recurrence relation and the solution the recurrence relation.

QUESTION :

Question 1 Consider the problem of putting L-shaped tiles (L-shaped consisting of three squares) in an nn square-board. You can assume that n is a power of 2. Suppose that one square of this board is defective and tiles cannot be put in that square. Also, two L-shaped tiles cannot intersect each other. Describe an algorithm that computes a proper tiling of the board. Justify the running time of your algorithm. (15 Marks)