代写 CS 336、代做 java/c++设计程序
- 首页 >> Matlab编程 CS 336: Algorithms Problem Set 5 Date: Thursday, October 31, 2024 Due: Thursday, November 7, 2024
Submit your solution on Gradescope.
Please, solve all problems on your own. Do not collaborate with other students.
Problem 1. The page limit for Problem 1 is 2 pages.
Similarly to HW2, you want to travel from city A to city B located on a straight line (A is
located in position 0 and B is located in position M ≥ 0), and you can travel at most distance D ≥ 0 miles per day, and you can only move to the right. Similarly, you have hotels between A and B with locations a1, . . . , an, where you can stay for a night.
You are a person who likes to optimize all aspects of your life. In particular, if you didn’t fully use all D miles per day, it causes you great distress. Namely, if on some day you traveled distance d miles (out of possible D miles), the amount of distress is 2D−d.
You start at city A. Your goal is to reach city B while suffering the least total amount of distress. Example: Assume that D = 4 and city B is located in position 6. You have two hotels in locations
2 and 3. The following routes have the following distress:
• 0→2→6: 24−(2−0) +24−(6−2) =4+1=5
• 0→2→3→6: 24−(2−0) +24−(3−2) +24−(6−3) =4+8+2=14 • 0→2→6: 24−(3−0) +24−(6−3) =2+2=4
The last route is optimal.
Please do the following:
• Formulate the subproblem. Please state it as precisely as possible. • Design a dynamic programming algorithm for solving this problem:
– State the base case.
– State the recurrence relation.
– Explain why the recurrence relation is correct (from your explanation, one should un- derstand how to get your the recurrence relation).
– Please provide the pseudocode. Please use the bottom-up approach.
– Explain:
∗ What is the running time of your algorithm (all arithmetic operations take constant time).
∗ How to recover the maximum reward.
∗ How to recover the optimal route. You don’t need to write a pseudocode.
∗ How your algorithm correctly handles the case when an optimal solution doesn’t
exist.
1
Problem 2. There is a new series in your streaming platform, Panopto. The series contains n episodes in total. Episodes need to be watched in order; that is, you cannot watch episode j before episode i if i < j. Since you’re busy, you decide to skip some subset of episodes (potentially empty). Your goal is to minimize the total amount of energy needed for this series, computed as follows:
• You figure out that if you skip episode i, you would have to spend pi energy at the end of the year to figure out the missed content.
• In addition, each episode has excitement value ei. You don’t want to dramatically change your emotions as well. So, for any consecutive episode i and j you watch, you need to spend |ei − ej | energy to adjust your mood as well.
For example, if there are 5 episodes:
• If you decide to watch episodes 1, 3, and 4, you need to spend p2 +p5 +|e1 −e3|+|e3 −e4| units of energy.
• If you only decide to watch episode 3, you need to spend p1 + p2 + p4 + p5 units of energy.
• If you decide to watch none of the episodes, you need to spend p1 +p2 +p3 +p4 +p5 units of
energy.
Implement the following function, which returns the list of episodes you decided to watch in the sorted order (the episodes are 1-indexed). For example, if you decide to watch first, third, and fourth episodes, your function must return a vector with items 1,3,4, in exactly this order. The input arrays are e and p respectively. It is guaranteed that for all test cases, the optimal answer is unique.
vector Episodes(const vector& excitement, const vector& penalty)
Time limit The instructions are similar to the previous programming assignments. Your program should pass each tests in no more than 1 second. You can assume that 1 ≤ n ≤ 104 and all numbers are between 1 and 109.
2
Submit your solution on Gradescope.
Please, solve all problems on your own. Do not collaborate with other students.
Problem 1. The page limit for Problem 1 is 2 pages.
Similarly to HW2, you want to travel from city A to city B located on a straight line (A is
located in position 0 and B is located in position M ≥ 0), and you can travel at most distance D ≥ 0 miles per day, and you can only move to the right. Similarly, you have hotels between A and B with locations a1, . . . , an, where you can stay for a night.
You are a person who likes to optimize all aspects of your life. In particular, if you didn’t fully use all D miles per day, it causes you great distress. Namely, if on some day you traveled distance d miles (out of possible D miles), the amount of distress is 2D−d.
You start at city A. Your goal is to reach city B while suffering the least total amount of distress. Example: Assume that D = 4 and city B is located in position 6. You have two hotels in locations
2 and 3. The following routes have the following distress:
• 0→2→6: 24−(2−0) +24−(6−2) =4+1=5
• 0→2→3→6: 24−(2−0) +24−(3−2) +24−(6−3) =4+8+2=14 • 0→2→6: 24−(3−0) +24−(6−3) =2+2=4
The last route is optimal.
Please do the following:
• Formulate the subproblem. Please state it as precisely as possible. • Design a dynamic programming algorithm for solving this problem:
– State the base case.
– State the recurrence relation.
– Explain why the recurrence relation is correct (from your explanation, one should un- derstand how to get your the recurrence relation).
– Please provide the pseudocode. Please use the bottom-up approach.
– Explain:
∗ What is the running time of your algorithm (all arithmetic operations take constant time).
∗ How to recover the maximum reward.
∗ How to recover the optimal route. You don’t need to write a pseudocode.
∗ How your algorithm correctly handles the case when an optimal solution doesn’t
exist.
1
Problem 2. There is a new series in your streaming platform, Panopto. The series contains n episodes in total. Episodes need to be watched in order; that is, you cannot watch episode j before episode i if i < j. Since you’re busy, you decide to skip some subset of episodes (potentially empty). Your goal is to minimize the total amount of energy needed for this series, computed as follows:
• You figure out that if you skip episode i, you would have to spend pi energy at the end of the year to figure out the missed content.
• In addition, each episode has excitement value ei. You don’t want to dramatically change your emotions as well. So, for any consecutive episode i and j you watch, you need to spend |ei − ej | energy to adjust your mood as well.
For example, if there are 5 episodes:
• If you decide to watch episodes 1, 3, and 4, you need to spend p2 +p5 +|e1 −e3|+|e3 −e4| units of energy.
• If you only decide to watch episode 3, you need to spend p1 + p2 + p4 + p5 units of energy.
• If you decide to watch none of the episodes, you need to spend p1 +p2 +p3 +p4 +p5 units of
energy.
Implement the following function, which returns the list of episodes you decided to watch in the sorted order (the episodes are 1-indexed). For example, if you decide to watch first, third, and fourth episodes, your function must return a vector with items 1,3,4, in exactly this order. The input arrays are e and p respectively. It is guaranteed that for all test cases, the optimal answer is unique.
vector
Time limit The instructions are similar to the previous programming assignments. Your program should pass each tests in no more than 1 second. You can assume that 1 ≤ n ≤ 104 and all numbers are between 1 and 109.
2