算法分析代写｜EECS 325 Analysis of Algorithms Homework 4

本次美国代写是一个Python算法分析的assignment

Instructions:

• This homework is due by 11:59PM Pacific Time on Thursday, December 2nd. You have
a one-time grace period allowing you to submit a homework assignment up to two days late.

Subsequent assignments submitted up to two days late will incur a 20% penalty. Assignments
submitted more than two days late will not be graded and will receive a score of 0.

• You must submit your written solutions as a single .pdf file on Canvas with your name at the
top. Typesetting your written solutions using LATEX is strongly encouraged. If you solve the
extra credit part of Question 1 you must submit your solution as a single .cpp, .java, or .py
file depending on your choice of language.

• You are welcome and encouraged to discuss the problems in groups of up to three people, but
you must write up and submit your own solutions and code. You must also write the
names of everyone in your group on the top of your submission.

• The primary resources for this class are the lectures, lecture slides, the CLRS and Erickson
algorithms textbooks, the teaching staff, your (up to two) collaborators, and the class Piazza
forum. We strongly encourage you only to use these resources. If you do use another resource,
make sure to cite it and explain why you needed it.

• Scoring: 50 points with up to 5 points of extra credit.

Question 1 (Chomping logs, 12 points + 5 extra credit points). Filbert and Maple are beavers
at the Oregon Zoo. They are experts at chomping logs into pieces, and, realizing that there’s a
market for logs of a particular length, they decide to monetize their skills. In this problem you will
design an algorithm to help Filbert and Maple maximize their profit.

As input, you get an integer L ≥ 1 corresponding to the length of the starting log to be
chomped (in feet), and a table corresponding to the retail value v(i) of i-foot-long logs for each
integer 1 ≤ i ≤ L. The goal is to pick a number of pieces k satisfying 1 ≤ k ≤ L and integer lengths
‘1; : : : ; ‘k satisfying 1 ≤ ‘1 ≤ · · · ≤ ‘k ≤ L so that L = Pk i=1 ‘i (the sum of the lengths of the log
pieces is equal to the length of the original log) and the total retail value Pk i=1 v(i) is maximized
over all choices of k and ‘1; : : : ; ‘k. The final output is the maximum possible total retail value
Pk i=1 v(i).

Consider the example in the following table:

a. (8 points) Design a tabulation-based dynamic programming algorithm for solving the \chomping
logs” problem. Give pseudocode for your algorithm and analyze its runtime. Clearly specify
what the dimensions of your table are, what each entry in the table represents, and how the
value of each in the table is computed.

(Hint: Suppose that you were given the value of ‘1. How could you use that to help solve the problem?)