Trominoes

This is a regular task. You must submit a PDF$,$ which can be produced using the LATEX template

on Moodle, exported from a word processor, hand$-$written or any other method.

This is a checkpoint task. Instructors will set the task status to $$Discuss$$ if they are satisfied with

your work. The task will only be upgraded to $$Complete$$ once you have discussed at least one of the

checkpoint tasks of this module at this grade level with an instructor in person.

Let n be a power of two. You are given an n$\backslash$times n board with one of its cells missing $($i$.$e$.,$ the board

has a hole$).$ The missing cell can be at any position in the board. You are also given a supply of

$$trominoes$,$ each of which can cover three cells as below.

Using ideas from tutorials or otherwise, design an efficient divide$-$and$-$conquer algorithm to tile

the board, justifying its time complexity $($using the Master Theorem$)$ and correctness.

Rubric.

$$ Your response should describe the steps followed to execute the algorithm in simple English.

Do not write a program, and do not transcribe a program back to written English.

You must justify the correctness of your algorithm.

You must justify that your algorithm runs in time complexity that you claim.

$$ Course materials such as lectures and tutorials don$$t require attribution, but making explicit

reference to similar ideas is still helpful to show your understanding.

Expected response length: less than one page