Due Monday 10/21/2024, at 10:00 pm (grace period until 11:59pm)

1 Study Group

List the names and SIDs of the members in your study group. If you have no collaborators, write “none” .

DP Solution Writing Guidelines:

When writing your solutions to DP problems only, please follow the 4-part solution template below (unless specified otherwise):

1.  Define a function f(·) in words. Make sure to include how many parameters there are and what they mean, and tell us what inputs you feed into f to get the answer to your problem.

2. Write the recurrence relation for f, as well as the “base cases”.

3.  Prove that the recurrence correctly solves the problem.  In almost all cases, you will want to use induction to prove the correctness of a DP algorithm.

4. Analyze the runtime and space complexity of your final DP algorithm.   Note  that the top-down and bottom-up approaches to DP have the same runtime complexity; however, bottom-up can potentially yield a better space complexity.

2 Egg Drop

You are given m identical eggs and an n story building. You need to figure out the highest floor b ∈ {0, 1, 2,... n} that you can drop an egg from without breaking it.  Each egg will never break when dropped from floor b or lower, and always breaks if dropped from floor b + 1 or higher.  (b = 0 means the egg always breaks).  Once an egg breaks, you cannot use it any more. However, if an egg does not break, you can reuse it.

Let f(n,m) be the minimum number of egg drops that are needed to find b (regardless of the value of b).

(a) Find f(1, m), f(0, m), f(n, 1), and f(n,0). Briefly explain your answers. Hint:  use  ∞  to  denote  that  it is  impossible  to find b.

(b)  Consider dropping an egg at floor h when there are n floors and m eggs left.  Then, it either breaks, or doesn’t break. In either scenario, determine the minimum remaining number of egg drops that are needed to find b in terms of f(·, ·), n, m, and/or h.

(c) Find a recurrence relation for f(n,m).

Hint:  whenever you  drop  an  egg,  call  whichever  of the  egg  breaking/not breaking leads to  more  drops  the   “worst-case  event” .   Since  we  need  to  find  b  regardless  of its  value, you should assume the worst-case  event  always happens.

(d) If we want to use dynamic programming to compute f(n,m) given n and m, in what order do we solve the subproblems?

(e)  Based on your responses to previous parts, analyze the runtime complexity of your DP algorithm.

(f) Analyze the space complexity of your DP algorithm.

(g)  Is it possible to modify your algorithm above to use less space?  If so, describe your modification and re-analyze the space complexity. If not, briefly justify.

3 Counting Targets

We call a sequence of n integers x1 , . . . , xn  valid if each xi  is in {1,..., m}.

(a)  Give a dynamic programming-based algorithm that takes in n,m and “target” T as input and outputs the number of distinct valid sequences such that x1 + ··· + xn  = T. Your algorithm should run in time O(m2n2 ). Note that you can assume T ≤ mn since no valid sequences sum to more than mn.

Please provide a 4-part solution.

(b) (Extra  Credit) Give  an  algorithm for the problem in part  (a) that runs in time O(mn2 ).

Please  provide  the  subproblem  definition,  recurrence relation (including base cases), and the runtime/space complexity analyses.  You do  not need to provide a proof of correctness.

4 String Shuffling

Let x, y, and z be strings.  We want to know if z can be obtained only from x and y by interleaving the characters from x and y such that the characters in x appear in order and the characters in y appear in order.

For example, if x = prasad and y = SANJAM, then it is true for z = praSANsadJAM, but false for z = prasadSANJAMpog (extra characters), z = prasSANJAad (missing the final M), and z  = prasadASNJAM (out of order).  How can we answer this query efficiently?  Your answer must be able to efficiently deal with strings with lots of overlap, such as x = aaaaaaaaaab and y = aaaaaaaac.

(a)  Design an efficient algorithm to solve the above problem, briefly justify its correctness, and analyze its runtime. You do not need to provide a space complexity analysis (you’ll do this in the next part!).

(b)  Consider a bottom-up approach to our DP algorithm in part (a).  Naively if we want to keep track of every solved sub-problem, this requires O(|x||y|) space (double check to see if you understand why this is the case).  How can we reduce the amount of space our algorithm uses?

5 My Dog Ate My Homework

One morning, you wake up to realize that your dog ate some of your CS 170 homework paper, which is an x × y 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 × 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.

(Each cut is either horizontal or vertical, and of one piece of paper at a time.) Formally, the problem is as follows:

Input: Dimensions of the paper x × y and an array P[i,j] such that P[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 P[i,j] values of each piece are either all 0 or all 1.

Design a DP-based algorithm to find the smallest number of cuts needed to separate all the bitten parts out in O(x3y3 ) time. For extra credit, try to optimize your algorithm to achieve a runtime of O((x + y)x2y2 ).

(a)  Define your subproblem.

Hint:   try  making  any  arbitrary  cut.    What  two  subproblems  do  you  now  have?    What parameters do you need to properly handle recursing on these two resulting subproblems?

(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.