# 算法分析代写｜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?)