Problem 4. A brickin' awesome problem (2+8+2+3= 15 points) Drew's dad collects bricks.. The bricks are...

Transcribed Image Text:

Problem 4. A brickin' awesome problem (2+8+2+3= 15 points) Drew's dad collects bricks.. The bricks are laid out in a nx n display, meaning there are n bricks in total (note that you can visualize this as n rows and n columns). Each brick has an age, which is simply the number of years it has been since the brick was produced. You can think of the input as being a nxn matrix B, where B[i, j] is the age of the brick in position i, j. You have been tasked with finding a brick such that none of the bricks adjacent to it (above, below, left, or right) are older than that brick. It is certainly possible that more than one brick meets this condition, in which case, finding any single brick with this property would suffice. If a brick is on a corner or a side, it only needs to be older than all of the adjacent bricks. You are able to access the age of any single brick in O(1) time. Design a O(n)-time divide-and-conquer algorithm to solve this problem. (a) Note that there must be a brick with the desired property. That is, a solution exists. Let L be the largest value of any brick and let (x,y) be any brick such that B[x, y] = L. Argue that (x,y) is a brick with the desired property. Can there be a different brick (u, v) with the desired property such that B[u, v] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 20 10 4 4 2 4 4 20 20 20 20 20 10 1 4 1 121 10 10 10 10 10 5 10 10 10 11 10 20 20 20 20 20 10 20 20 20 11 20 1 1 1 20 10 20 1 1 1 1 1 1 1 1 20 10 20 1 1 1 1 1 1 1 1 1 1 1 1 20 10 7 6 1 4 1 20 10 6 5 2 4 4 20 10 1 3 1 2 1 1 1 1 20 10 20 1 1 1 1 20 10 20 1 1 1 1 Problem 4. A brickin' awesome problem (2+8+2+3= 15 points) Drew's dad collects bricks.. The bricks are laid out in a nx n display, meaning there are n bricks in total (note that you can visualize this as n rows and n columns). Each brick has an age, which is simply the number of years it has been since the brick was produced. You can think of the input as being a nxn matrix B, where B[i, j] is the age of the brick in position i, j. You have been tasked with finding a brick such that none of the bricks adjacent to it (above, below, left, or right) are older than that brick. It is certainly possible that more than one brick meets this condition, in which case, finding any single brick with this property would suffice. If a brick is on a corner or a side, it only needs to be older than all of the adjacent bricks. You are able to access the age of any single brick in O(1) time. Design a O(n)-time divide-and-conquer algorithm to solve this problem. (a) Note that there must be a brick with the desired property. That is, a solution exists. Let L be the largest value of any brick and let (x,y) be any brick such that B[x, y] = L. Argue that (x,y) is a brick with the desired property. Can there be a different brick (u, v) with the desired property such that B[u, v] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 20 10 4 4 2 4 4 20 20 20 20 20 10 1 4 1 121 10 10 10 10 10 5 10 10 10 11 10 20 20 20 20 20 10 20 20 20 11 20 1 1 1 20 10 20 1 1 1 1 1 1 1 1 20 10 20 1 1 1 1 1 1 1 1 1 1 1 1 20 10 7 6 1 4 1 20 10 6 5 2 4 4 20 10 1 3 1 2 1 1 1 1 20 10 20 1 1 1 1 20 10 20 1 1 1 1

Answer rating: 100% (QA)

a To argue that x y is a brick with the desired property we can observe that if Bx y is the largest value L then it means there are no bricks with a h... View the full answer