本次加拿大作业是Python算法代写的一个Problem Set

Problem Set

Answer each question completely, always justifying your claims and reasoning. Your solution will be graded not only on
correctness, but also on clarity.

Answers that are technically correct that are hard to understand will not receive full marks. Mark values for each question
are contained in the [square brackets].

You may work in groups of up to TWO to complete these questions.

1 Minimizing Stops

You have a car that can travel d KM on a full tank of gas. Your car starts out with a full tank of gas, you start at position 0,
and you want to travel to position L. There are gas stations at positions g1, g2, . . . , gn. Each time you stop at a gas station,
you fill your gas tank until it is full. Your goal is to minimize the number of gas-station stops that you make. Your gas tank
is never allowed to become completely empty (otherwise your car stalls and you cannot keep going), and you can assume that
the first gas station is within d KM of the starting point, the last gas station is within d KM of the ending point, and no two
consecutive gas stations are more than d KM apart.

1. [4] Give pseudocode for and prove a correct greedy algorithm for this problem. It’s required that you prove it in the
way we have done in lecture. That is, give the greedy choice, define what it means for a partial solution to be promising,
and then propose and prove an exchange argument that lets you incrementally change an optimal solution into your
greedy solution without making the optimal solution worse.

2 Processor Scheduling

We have a processor on which n tasks are to be run. As soon as one task finishes running, the next one can start. Each task j
has a length lj giving the amount of time that the task takes to run. Each task j also has a weight wj giving the importance
of the task; tasks with higher weights are more important.
Define the completion time cj of a task j as the total time that elapses before task j finishes running. For example, if we run
task 1 that has length 3 and then task 2 that has length 5, then the completion time of task 1 is 3, and the completion time
of task 2 is 3 + 5 = 8.

We would like a greedy algorithm that minimizes the following quantity:

(That is, we are minimizing the sum of the completion times but where each completion time is weighted by the importance
of the task.) The output of the algorithm is a permutation of the jobs that minimizes this quantity.

1. [2] Give a plausible but incorrect greedy algorithm for this problem. Specifically, give the greedy choice that your
algorithm uses, the algorithm pseudocode, and a counterexample showing that the algorithm is incorrect.

2. [6] Now give the pseudocode for and prove a correct greedy algorithm for this problem. It’s required that you prove
it in the way we have done in lecture. That is, give the greedy choice, define what it means for a partial solution to be
promising, and then propose and prove an exchange argument that lets you incrementally change an optimal solution
into your greedy solution without making the optimal solution worse.

Think carefully through this proof and compare this problem to our scheduling problem from lecture. Notice that in
lecture we had a set, and here we have a sequence; in lecture, we scheduled a subset of activities, but here we schedule
all tasks. These differences are important in the proof.

Programming Question

The best way to learn a data structure or an algorithm is to code it up. In some problem sets, we will have a programming
exercise for which you will be asked to write some code and submit it. You may also be asked to include a write-up about
your code in the PDF/TEXfile that you submit. Make sure to maintain your academic integrity carefully, and protect
your own work. The code you submit will be checked for plagiarism. It is much better to take the hit on a lower mark than
risking much worse consequences by committing an academic offence.