CSC373 – Problem Set 1
To avoid suspicions of plagiarism: at the beginning of your submission, clearly state any resources (people, print,
electronic) outside of your group, the course notes, and the course staff, that you consulted.
Problem Set: due October 1, 2021 22:00
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:
n∑
j=1
wj ∗ cj
. (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.
3 Legend of Adlez
You are playing a video game called Legend of Adlez. There are n towns, right now you’re in town a, and you want to walk
to town b. Unlike in other video games where you can walk for hours and hours without stopping, you cannot do that here.
In particular, you have a current number of stamina points; if your stamina drops to 0 then you cannot travel anymore.
To walk the road between two towns that are d KMs apart uses up d stamina points. If you do not currently have at least d
stamina points then you cannot walk this road.
Luckily, each town has an inn where you can rest. For every hour that you rest, you gain back one stamina point up to your
maximum stamina points m. Each inn has a cost that you pay for each hour of rest. You don’t want to unnecessarily waste
money staying at the inns.
What is the cheapest cost to get from your starting town a to your destination town b?
1. [5] Implement the function cheapest_cost in the starter code. You can assume that n and m are at most 500, and
that the number of roads is at most 1000.
Requirements:
� Your code must be written in Python 3, and the filename must be cheapest.py.
� We will grade only the cheapest_cost function; please do not change its signature in the starter code. You may
include as many helper functions as you wish.
� For each test-case that your code is tested on, your code must run within 10x the time taken by our solution.
Otherwise, your code will be considered to have timed out.
Please include comments in your code to explain what your algorithm is doing.
2. [2] Write-up: in your ps1.pdf/ps1.tex files, include the following: a concise and precise explanation of how your code
works, a concise justification of correctness, and justification of the worst-case runtime complexity. Some points will be
awarded for achieving strong complexity bounds.