代写CS 170, Fall 2024 Homework 7代写Java编程

CS 170, Fall 2024

Homework 7

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.

6    [Coding] More Advanced Dynamic Programming

For this week’s homework, you’ll implement implement some more dynamic programming algorithms. There are two ways that you can access the notebook and complete the problems:

1.  On Datahub: click here and navigate to the hw07 folder.

2.  On  Local  Machine:  git  clone  (or  if you already cloned it,  git  pull) from the coding homework repo,

https://github.com/Berkeley-CS170/cs170-fa24-coding

and navigate to the hw07 folder. Refer to the README.md for local setup instructions. Notes:

•  Submission  Instructions:   Please  download  your completed submission  .zip  file  and submit it to the Gradescope assignment titled “Homework 7 Coding Portion” .

•  Getting  Help:   Conceptual questions  are always welcome on Edstem and office hours; note  that support for debugging help  during  OH will  be  limited.  If you need debugging help first try asking on the public Edstem threads.  To ensure others can help you, make sure to:

1.  Describe the steps you’ve taken to debug the issue prior to posting on Ed.

2.  Describe the specific error you’re running into.

3. Include a few small but nontrivial test cases, alongside both the output you ex- pected to receive and your function’s actual output.

If staff tells you to make a private Ed post, make sure to include all  of the above items plus your full function implementation.  If you don’t provide them, we will ask you to provide them.

•  Academic  Honesty  Guideline:  We realize that code for some of the algorithms we ask you to implement maybe readily available online, but we strongly encourage you to not directly copy code from these sources. Instead, try to refer to the resources mentioned in the notebook and come up with code yourself.  That being said, we do acknowledge that there may not be many different ways to code up particular algorithms and that your solution may be similar to other solutions available online.