One morning, you wake up to realize that your dog ate some of your CS 170...

Transcribed Image Text:

One morning, you wake up to realize that your dog ate some of your CS 170 homework paper, which is an mxn rectangular grid of squares. Some of the squares have holes chewed through them, and you cannot use paper that has a hole in it. You would like to cut the paper into pieces so as to separate all the tattered squares from all the clean, un-bitten squares. You want to do this so that you can save as much as your work as possible. For example, shown below is a 6 x 4 piece of paper where the bitten squares are marked with *. As shown in the picture, one can separate the bitten parts out in exactly four cuts. * * * * * * * * * * CS * CS * * * C S C S 1 70 * 1 7 0 * 0 * 0 * 1 7 1 7 * * * * * * * * * * * * * * * * * * * * ↑↑ * * CS 1 0 7 * * * * * * * (Each cut is either horizontal or vertical, and of one piece of paper at a time.) Design a DP based algorithm to find the smallest number of cuts needed to separate all the bitten parts out. Formally, the problem is as follows: Input: Dimensions of the paper m x n and an array A[i, j] such that A[i, j] = 1 if and only if the ijth square has holes bitten into it. Goal: Find the minimum number of cuts needed so that the A[i, j] values of each piece are either all 0 or all 1. (a) Define your subproblem. Hint: try making any arbitrary cut. What two subproblems do you now have? (b) Write down the recurrence relation for your subproblems. A fully correct recurrence relation will always have the base cases specified. (c) Describe the order in which we should solve the subproblems in your DP algorithm. (d) What is the runtime complexity of your DP algorithm? Provide a justification. (e) What is the space complexity of your algorithm? Provide a justification. One morning, you wake up to realize that your dog ate some of your CS 170 homework paper, which is an mxn rectangular grid of squares. Some of the squares have holes chewed through them, and you cannot use paper that has a hole in it. You would like to cut the paper into pieces so as to separate all the tattered squares from all the clean, un-bitten squares. You want to do this so that you can save as much as your work as possible. For example, shown below is a 6 x 4 piece of paper where the bitten squares are marked with *. As shown in the picture, one can separate the bitten parts out in exactly four cuts. * * * * * * * * * * CS * CS * * * C S C S 1 70 * 1 7 0 * 0 * 0 * 1 7 1 7 * * * * * * * * * * * * * * * * * * * * ↑↑ * * CS 1 0 7 * * * * * * * (Each cut is either horizontal or vertical, and of one piece of paper at a time.) Design a DP based algorithm to find the smallest number of cuts needed to separate all the bitten parts out. Formally, the problem is as follows: Input: Dimensions of the paper m x n and an array A[i, j] such that A[i, j] = 1 if and only if the ijth square has holes bitten into it. Goal: Find the minimum number of cuts needed so that the A[i, j] values of each piece are either all 0 or all 1. (a) Define your subproblem. Hint: try making any arbitrary cut. What two subproblems do you now have? (b) Write down the recurrence relation for your subproblems. A fully correct recurrence relation will always have the base cases specified. (c) Describe the order in which we should solve the subproblems in your DP algorithm. (d) What is the runtime complexity of your DP algorithm? Provide a justification. (e) What is the space complexity of your algorithm? Provide a justification.

Answer rating: 100% (QA)

a Subproblem Definition Lets define our subproblem as follows Given a paper grid with dimensions m x n we want to find the minimum number of cuts required to separate the bitten parts Aij1 from the un... View the full answer