Suppose you have a log of length L, marked to be cut in n different locations...

Transcribed Image Text:

Suppose you have a log of length L, marked to be cut in n different locations labeled 1, 2, ..., n. The woodcutter will cut a given log of wood, at any place you choose, for a price equal to the length of the given log. For simplicity, let indices 0 and n + 1 denote the left and right endpoints of the original log of length L. Let d, denote the distance of mark i from the left end of the log and assume that 0=d, <d₁ <d₂ <...<d₁ <dn+1 =L. Determining the sequence of cuts to the log that will cut the log at all the n marked places and minimize your total payment. Choose the following strategies: A. Greedy algorithm picking the point closest to the center of log (3 points). This strategy is not optimum. B. Dynamic programming (7 points). The algorithm time-complexity is O(n²). Use C, C++, Java, or Python to implement Part A and B (ask the instructor if you have another programming language in mind). Suppose you have a log of length L, marked to be cut in n different locations labeled 1, 2, ..., n. The woodcutter will cut a given log of wood, at any place you choose, for a price equal to the length of the given log. For simplicity, let indices 0 and n + 1 denote the left and right endpoints of the original log of length L. Let d, denote the distance of mark i from the left end of the log and assume that 0=d, <d₁ <d₂ <...<d₁ <dn+1 =L. Determining the sequence of cuts to the log that will cut the log at all the n marked places and minimize your total payment. Choose the following strategies: A. Greedy algorithm picking the point closest to the center of log (3 points). This strategy is not optimum. B. Dynamic programming (7 points). The algorithm time-complexity is O(n²). Use C, C++, Java, or Python to implement Part A and B (ask the instructor if you have another programming language in mind).

Answer rating: 100% (QA)

The task described in the question is a classic optimization problem known as the rod cutting proble... View the full answer