COMP3270 Homework 12 Solution

• USE THIS FILE AS THE STARTING DOCUMENT YOU WILL TURN IN. DO NOT DELETE ANYTHING FROM THIS FILE: JUST INSERT YOUR ANSWERS.

• IF USING HAND WRITING (STRONGLY DISCOURAGED), USE THIS FILE BY CREATING SUFFICIENT SPACE AND WRITE IN YOUR ANSWERS.
• FAILING TO FOLLOW TURN IN DIRECTIONS /GUIDELINES WILL COST A 30% PENALTY.

Objectives of this assignment:
• to use and manipulate the concepts presented in this module
• to propose and write algorithms in pseudocode
• to analyze the time complexity of algorithms
• to analyze the space complexity of algorithms
• to learn autonomously new concepts
What you need to do:
Answer the questions and/or solve the exercises described below.

Exercise 1 (50 points)
Consider a modification of the rod-cutting problem in which, in addition to a price pi for each rod, each cut incurs a fixed cost of c. The revenue associated with a solution is now the sum of the prices of the pieces minus the costs of making the cuts. Give a dynamic-programming algorithm to solve this modified problem. Precisely comment and explain the modifications/additions you make to the original algorithm to meet the requirements.
Include here the pseudocode
Make sure you comment and explain the modifications/additions.


Exercise 2 (50 points)
1) Implement in your preferred language MEMOIZED-CUT-ROD. Insure your program can be compiled and executed on an Engineering Unix Tux machine.
Turn in this program separately on Canvas with your homework

2) Test your implementation that it yields the same results as in the textbook. State here whether your implementation yields the same results as in the textbook.
Insert here screenshots to show that your program yields the same results

3) Modify your MEMOIZED-CUT-ROD implementation (from Question 1) to return not only the value but the actual solution, too.
Include/Insert here the pseudocode of your program
Turn in the modified implementation separately on Canvas

4) In addition to the pseudocode in THIS file, turn in the source code of your implementation. Include a small report stating 1) whether your code works, 2) how to compile and execute your program on a Tux machine.
state here whether your programs work as required
include here how to compile and execute your two programs on Tux machines







What you need to turn in:
• Electronic copy of this file (including your answers) (standalone). Submit the file as a Microsoft Word or PDF file.
• Source code of required program(s) with directions about how to compile and execute them.
• Recall that answers must be well written, documented, justified, and presented to get full credit.

• How this assignment will be graded:
• A right answer will get full credit when:
• It is right (worth 25%)
• It is right AND neatly presented making it easy and pleasant to read. (worth 15%)
• There is an obvious and clear link between 1) the information provided in the exercise and in class and 2) the final answer. A clear link is built by properly writing, justifying, and documenting an answer (worth 60%).
• Calculation mistakes will be minimally penalized (2 to 5% of full credit) while errors on units will be more heavily penalized.
•

Appendix: Grading: What is an OBVIOUS and CLEAR LINK?
Here is an example to explain what an obvious and clear link is and how we grade your work. Consider the following problem:
"(100 points) John travels from Auburn to Atlanta in his car at a speed of 60 mph. Leaving at 8am, at what time will John reach Atlanta".
Here are the answers of three students and their scores:
• Student 1 answers: "9:48am". Student 1 will get 25 points.
• Student 2 answers: "John will reach Atlanta at 9:48am". Student 2 will get 25+15 = 40 points
• Student 3 answers: "The time t to travel a distance d at speed v is equal to d/v = d/60mph. The problem does not provide the distance d from Auburn to Atlanta. Based on GoogleMaps, the distance from Auburn to Atlanta is approximately 108 miles (document is attached).


Therefore, the time t = 108 miles/60mph * 60 minutes/hour= 108 minutes. Since John left at 8am, he will then reach Atlanta at 8am + 108 minutes = 8 am + 60 minutes + 48 minutes = 9:48".

Student 3 will get 25 + 15 + 60 = 100 points
Do you see the direct link going from the data provided in the question to the final answer, using general knowledge/formula and documents?.... Can you now solve the following problem and get 100 points?
"(100 points) Alice travels from Auburn to Atlanta in her car at a speed of 60 mph. Leaving at 8am, at what time will Alice reach Atlanta assuming that she had a flat tire that delayed her 30 minutes".