Suppose you have a square floor with dimensions 2 by 2k, k > 1. A floor with these dimensions can be covered with a single square tile and (224 - 1)/3 L-shaped tiles. 1. (13 marks) Design, implement, and test a divide-and-conquer algorithm that takes, as input, the value of k and the location of the single square tile. The algorithm then places the remaining L-shaped tiles to fully cover the floor. Output the floor showing the resultant placement of the tiles. Given the location of the single tile (numbered 0), the sample solution below shows the placement of the other 21 L-shaped tiles to fully cover an 8 x 8 grid. 1 1 1 2 2 3 3 4 4 5 5 2 3 6 6 4 7 5 8 8 9 9 6 10 7 7 8 11 | 11 9 10 10 12 12 13 13 11 14 15 15 12 | 16 | 0 | 13 | 14 | 14 | 1715 18 16 16 19 20 17 17 21 18 18 19 19 20 20 21 21 2. (4 marks) Let n = 22kDetermine the recurrence relation that describes the time complexity of your algorithm in part 1) and using the Master Theorem, state its exact order of complexity in terms of n. Suppose you have a square floor with dimensions 2 by 2k, k > 1. A floor with these dimensions can be covered with a single square tile and (224 - 1)/3 L-shaped tiles. 1. (13 marks) Design, implement, and test a divide-and-conquer algorithm that takes, as input, the value of k and the location of the single square tile. The algorithm then places the remaining L-shaped tiles to fully cover the floor. Output the floor showing the resultant placement of the tiles. Given the location of the single tile (numbered 0), the sample solution below shows the placement of the other 21 L-shaped tiles to fully cover an 8 x 8 grid. 1 1 1 2 2 3 3 4 4 5 5 2 3 6 6 4 7 5 8 8 9 9 6 10 7 7 8 11 | 11 9 10 10 12 12 13 13 11 14 15 15 12 | 16 | 0 | 13 | 14 | 14 | 1715 18 16 16 19 20 17 17 21 18 18 19 19 20 20 21 21 2. (4 marks) Let n = 22kDetermine the recurrence relation that describes the time complexity of your algorithm in part 1) and using the Master Theorem, state its exact order of complexity in terms of n