代写 CS 336、代做 java/c++设计程序

日期：2024-11-09 11:55

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<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.

2