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 **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<int> Episodes(const vector<int>& excitement, const vector<int>& 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.
請加QQ：99515681 郵箱：99515681@qq.com WX：codinghelp
