1. (8 points) Over break, you take up bricklaying. For your first assignment, you have been asked to complete a brick wall where someone else has already built the first row of bricks. This wall is being built with bricks of length 1 , 2, and 3. As every builder knows, the bricks in a row need to "connect" the bricks below - that is, for any two neighboring bricks in the first row, there has to be a brick above that covers the connection between the bricks. For example, suppose the first wall's first row consists of bricks with lengths 2,3,1,3,2 as follows: Then it is possible to start the second row with a brick of length 1 (see below on the left), but it isn't possible to start the second row with a brick of length 2 since that makes the brick boundaries line up: Not happy with finding one way to build the next layer, you decide to count all the ways to build it. Specifically, you want to take n bricks with a sequence of lengths 1,2,,n, and calculate the number of ways the next layer of bricks can be built so that none of the brick boundaries line up. For example, with n=2,1=1, and 2=2, there are two possibilities: Give an efficient dynamic programming solution to count number of ways to build the next level. You may find it helpful to think about the problem in terms of N, the total length of bricks in the first layer. (Note that n and N are asympototically equal.) 2. (8 points) Unfortunately for your wall-building plans, you discover that there are only k length-3 bricks. (You still have an unlimited supply of the other sizes.) With this extra constraint, you give up on counting the total number of solutions, but still want to see if you can build the next layer. Give a dynamic programming algorithm with running time O(Nk) that determines if the next layer can be built using at most k length-3 bricks so that none of the brick boundaries line up. 1. (8 points) Over break, you take up bricklaying. For your first assignment, you have been asked to complete a brick wall where someone else has already built the first row of bricks. This wall is being built with bricks of length 1 , 2, and 3. As every builder knows, the bricks in a row need to "connect" the bricks below - that is, for any two neighboring bricks in the first row, there has to be a brick above that covers the connection between the bricks. For example, suppose the first wall's first row consists of bricks with lengths 2,3,1,3,2 as follows: Then it is possible to start the second row with a brick of length 1 (see below on the left), but it isn't possible to start the second row with a brick of length 2 since that makes the brick boundaries line up: Not happy with finding one way to build the next layer, you decide to count all the ways to build it. Specifically, you want to take n bricks with a sequence of lengths 1,2,,n, and calculate the number of ways the next layer of bricks can be built so that none of the brick boundaries line up. For example, with n=2,1=1, and 2=2, there are two possibilities: Give an efficient dynamic programming solution to count number of ways to build the next level. You may find it helpful to think about the problem in terms of N, the total length of bricks in the first layer. (Note that n and N are asympototically equal.) 2. (8 points) Unfortunately for your wall-building plans, you discover that there are only k length-3 bricks. (You still have an unlimited supply of the other sizes.) With this extra constraint, you give up on counting the total number of solutions, but still want to see if you can build the next layer. Give a dynamic programming algorithm with running time O(Nk) that determines if the next layer can be built using at most k length-3 bricks so that none of the brick boundaries line up
