# Python算法代写 | CSC373 – Problem Set 1

本次加拿大作业是**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.