program代写、代写Python设计编程

日期：2022-10-30 09:58

Problem 1 [20 points]: Problem 16-1 (Coin Changing) in your textbook.

Problem 2 [30 points]: Suppose you were planning a scenic cross country road–trip along the “Mother

Road” (i.e., U.S. Route 66). Your gas tank, when full, holds enough gas to go p miles, and you have a map

that contains the information on the distances between gas stations along the route. Let d1 < d2 < · · · < dn

be the locations of all the gas stations along the route, where di

is the distance from the Chicago end of the

freeway (your starting point in this hypotehtical trip) to the gas station. You may assume that the distance

between neighboring gas stations is at most p miles. Your goal is to make as few gas stops as possible along

the way, as you want to enjoy the scenery instead of gas stations.

• Give the most efficient algorithm you can come up with to determine at which gas stations you should

stop.

• Prove that your algorithm yields an optimal solution

• Give the time complexity of your algorithm as a function of n. Note that for full marks, you must

show how you derived the complexity.

Problem 3 [25 points]: Suppose you are participating in a skiing competition with your friends. Suppose

skiers go fastest when their skis’ length is about their height. To help your team win the competition, you

decide to come up with an efficient algorithm to match skis to skiers. Your team consists of n members,

with heights h1, h2, . . . , hn, respectively, and has n pairs of skis, with corresponding lengths l1, l2, . . . , ln.

• Describe an efficient algorithm in English (and, if helpful, pseudo–code) to minimize the sum of the

absolute differences between the height of skier hi and the length of the corresponding ski lj , i.e.,

minimize 1

n

P|hi − li

|.

• Prove (or at least provide compelling arguments in favor of) the correctness of your algorithm.

• Provide an analysis of the running time of your algorithm (i.e., show the time complexity of your

algorithm, and explain how you derived it).

1

Problem 4 [25 points]: Consider a very simplistic video

game, as shown on the right, where given a field of n ∗ m cells,

your goal is to help the miner move around in order to maximize

the gold she can collect. Suppose the field is represented as

matrix F, each element Fij ≥ 0 of which denotes the amount

of gold (positive integer) to be collected from that particular

cell. A .csv file representation of F is to be provided as input

to your program. Specifically, each separate line will contain

exactly m elements separated by a coma, and there will be n

lines in total. The example input file below, represents a 3 × 3

field:

1,3,3

2,1,4

0,6,4

Initially the miner is at the first column, but can be at any row. Additionally, from any given cell, the miner

can move to the cell directly to the right, diagonally up towards the right, or diagonally down towards the right.

Given the example input above, your solution should produce the following output:

12: (2,1) -> (3,2) -> (3,3)

The first element is the total amount of gold collected, and the sequence of tuples following the “:”

character denotes the sequence of steps the miner should take. Specifically, each transition (i, j) → (k, m)

denotes a move from cell Fij to Fkm. In the specific example, the miner initially moves from cell F21,

collecting a reward of 2 amount of gold, to F32, and subsequently to F33, for a total harvest of 2 + 6 + 4 = 12

units of gold.

Implement your algorithm in Python or Java. Make sure to indicate your setup (e.g., version of Python

and libraries required), and how to run your program. If your program fails to compile, or produces logical

errors, will receive 0 points. For full marks, your code should be well documented/commented.

Your program will be evaluated for correctness [20 points] using small–scale, toy fields, and scalability [5

points] on large fields.

2