Python 算法编程 - Assignment

Problem 1. Karatsuba Example

Carry out Karatsuba’s Algorithm to compute 52 · 89. What are the inputs for each recursive call,

what does that recursive call return, and how do we compute the final product?

Problem 2. Help thy neighbor

2022 has been a tough year for the Red Sox. Looking to find some silver linings in the difficult season, manager Alex Cora has asked you to help identify the best stretch of the season for the team. To do this, the analytics department has shared with you the run differentials from n games this season. For each game, this value can be positive (if the Sox won) or negative (if they lost). For example, if they won 10-4, then lost 6-2, then won 3-2, the run differentials would be 6, -4, 1. Alex would like you to find the stretch of consecutive games such that the total run differential is maximized. The total run differential of a stretch of games is simply the sum of the run differentials of those games.

For example, consider the following:

n = 7, differentials: −1, 5, −2, 1, 4, −3, 1

Here, the optimal solution is from game 2 to game 5, and the total run differential is 8.

(a) Write (in pseudocode) a divide and conquer algorithm which solves this problem in O(nlogn) time. Provide a few sentences describing your approach. Note that your algorithm should output the range of games that yields the maximum total run differential.

(b) Write a recurrence for the runtime of your algorithm and solve it. You may use any method for solving the recurrence that we have discussed in class. Justify your recurrence.

Problem 3. Today Seitan

You have vegan chicken sandwich restaurants in various locations along route US1. You have s stores, where the i-th store is mi miles on US1 from Key West. Using algorithms you have determined t target cities where you would like to sell your delicious seitan sandwiches, where the j-th target city is dj miles on US1 from Key West. However, in order to do so, you need to hire drivers who are willing to deliver sandwiches to the target cities. You want to write an ad posting for the delivery driver position saying “Drivers must be willing to drive up to X miles” and need to accurately determine what X is so that you can have your sandwiches delivered to every target city. Note that drivers can travel in either direction down US1.

Suppose that t is much smaller than s, and knowing this information you would like to design an algorithm which has at most a logarithmic dependence on s and a linear dependence on t. You may assume the di and mi arrays are both already sorted.

For example, consider the following instance:

s = 4, t = 3

Store locations: 15, 20, 65, 82

Target city locations: 6, 33, 71

Answer = 13 (because there is a city at 33 and the closest store is at 20, 33-20=13)

(a) Write (in pseudocode) an algorithm which determines the value of X to place in the job ad. Provide a few sentences describing your approach. For full credit your algorithm should run in O(t ∗ log(s)) time.

(b) State the worst-case runtime of your algorithm and explain how you derived this result.

Problem 4. Deep in tot

You have been put in charge of judging the potato sorting contest at this year’s Eastern Idaho State Fair. Each contestant is tasked with sorting n potatoes by weight in ascending order, without the assistance of any equipment. The judging is as follows:

• Given an ordering of n potatoes, a mistake consists of two potatoes i and j such that potato i is before potato j in ther order, but i weighs more than j.

You need to be able to quickly calculate the number of mistakes in a given ordering. The runtime of your algorithm should be O(nlog(n)) for full credit. You have the ability to compare the weights of two potatoes in O(1) time.

(a) Describe a divide-and-conquer algorithm (in pseudocode) which returns the number of mistakes. Provide a complete written description of your approach.

(b) State the worst-case asymptotic running time of your approach. Write a recurrence which captures the worst-case runtime of your algorithm and solve it using any method that we’ve seen in class.

咨询 Alpha 小助手，获取更多课业帮助。