Assignment # 1 CSC 373H1

Assignment # 1

CSC 373H1

[Please make sure your solution is no more than 2 regular A4/Letter sized pages per problem, i.e., your
full submission should be no more than 8 pages.]
1. [20 marks]
Consider the problem of choosing cell phone tower locations on a long straight road. We are given a
list of locations along the road at which there are customers’ houses, say {xk
}
K
k=1. No towers have yet
been built (so no customers currently have service). However, a survey of the road has provided a
set of J possible tower locations, {tj
}
J
j=1, where these potential tower locations are also measured in
terms of the distance along the road. (These indexed lists of house and tower locations might be in
any order. You can assume that all these distances are integers.)
Each customer will get service (at home) if and only if they are within a range R > 0 of at least one
cell phone tower that gets built, that is, the house at xk will have service iff there exists a tower that
has been built at some tj with |xk − tj
| ≤ R.
You can assume that if all the towers were built then every home would get service. However, such a
solution could be overly expensive for the phone company. How can we minimize the number of
towers that need to be built but still provide service at every house? Note that a suitable solution
may still leave some parts of the road without cell service, even though each customers’ house will
have service.
(a) [7 points]
Write a greedy algorithm for choosing the minimum number M of cell phone towers required,
along with a suitable set of locations, say T = {tj(m)
}
M
m=1, such that every house has service.
Present your algorithm as a pseudocode.
(b) [10 points]
Prove the correctness of your algorithm.
(c) [3 points]
Compute the complexity of your algorithm.
2. [20 marks]
Consider a variant on the problem of Interval Partitioning.
Suppose we have two resources, and we want to schedule as many requests as we can. The input is
(s1, f1), (s2, f2), ···, (sn, fn), where n ≥ 1 and all si < fi are nonnegative integers. The integers si and fi
represent the start time and finish time, respectively, of request ri
.
A schedule is now defined as a pair of sets (A1,A2), the intuition being that Ai
is the set of requests
scheduled on resource i. A schedule must satisfy the obvious constraints: A1 ⊆ {1,2,...,n}, A2 ⊆
{1,2,...,n}, A1 ∩ A2 = ∅, and for all i , j such that i, j ∈ A1 or i, j ∈ A2, requests i and j do not overlap.
(a) [10 marks]
Design an algorithm (write a pseudocode) to solve the above problem in time o(n
2
), i.e., strictly
less than O(n
2
). Compute the complexity of your algorithm.
(b) [10 marks]
Prove that the above algorithm is guaranteed to compute an optimal schedule.
3. [20 marks]
Consider the problem of making change, given a finite number of coins with various values. Formally:
1 Page 1 of 3
Dept. of Computer Science
University of Toronto
Assignment # 1
(Due May 29, 11:59 pm)
CSC 373H1
Summer 2021
Input: A list of positive integer coin values c1, c2, ···, cm (with repeated values allowed) and a
positive integer amount A.
Output: A selection of coins {i1, i2,..., ik
} ⊆ {1,2,...,m} such that ci1
+ci2
+···+cik
= A and k is as small
as possible. If it is impossible to make change for amount A exactly, then the output should be
the empty set ∅.
(a) [5 points]
Describe a natural greedy strategy you could use to try and solve this problem, and show that
your strategy does not work.
(The point of this question is not to try and come up with a really clever greedy strategy — rather,
we simply want you to show why the “obvious” strategy fails to work.)
(b) [10 points]
Give a detailed dynamic programming algorithm to solve this problem. Follow the steps
outlined in class, and include a brief (but convincing) argument that your algorithm is correct.
(c) [5 points]
What is the worst-case running time of your algorithm? Justify briefly.
4. [20 marks]
During the renovations at Union Station, the work crews excavating under Front Street found veins
of pure gold ore running through the rock! They cannot dig up the entire area just to extract all the
gold: in addition to the disruption, it would be too expensive. Instead, they have a special drill that
they can use to carve a single path into the rock and extract all the gold found on that path. Each
crew member gets to use the drill once and keep the gold extracted during their use. You have the
good luck of having an uncle who is part of this crew. What’s more, your uncle knows that you are
studying computer science and has asked for your help, in exchange for a share of his gold!
The drill works as follows: starting from any point on the surface, the drill processes a block of rock
10cm×10cm×10cm, then moves on to another block 10cm below the surface and connected with the
starting block either directly or by a face, edge, or corner, and so on, moving down by 10cm at each
“step”. The drill has two limitations: it has a maximum depth it can reach and an initial hardness
that gets used up as it works, depending on the hardness of the rock being processed; once the drill
is all used up, it is done even if it has not reached its maximum depth.
The good news is that you have lots of information to help you choose a path for drilling: a detailed
geological survey showing the hardness and estimated amount of gold for each 10cm × 10cm × 10cm
block of rock in the area. To simplify the notation, in this homework, you will solve a two-dimensional
version of the problem defined as follows.
Input: A positive integer d (the initial drill hardness) and two [m × n] matrices H, G containing
non-negative integers. For all i ∈ {1,...,m}, j ∈ {1,...,n}, H[i, j] is the hardness and G[i, j] is the
gold content of the block of rock at location i, j (with i = 1 corresponding to the surface and i = m
corresponding to the maximum depth of the drill).
There is one constraint on the values of each matrix: H[i, j] = 0 =⇒ G[i, j] = 0 (blocks with
hardness 0 represent blocks that have been drilled already and contain no more gold).
Figure 1 below shows the general form of the input. Figure 2 shows a sample input.
Output: A drilling path j1, j2,..., j`
for some ` ≤ m such that:
• 1 ≤ jk ≤ n for k = 1,2,..., ` (each coordinate on the path is valid);
2 Page 2 of 3
Dept. of Computer Science
University of Toronto
Assignment # 1
(Due May 29, 11:59 pm)
CSC 373H1
Summer 2021
• jk−1 − 1 ≤ jk ≤ jk−1 + 1 for k = 2,..., ` (each block is underneath the one just above, either
directly or diagonally);
• H[1, j1]+H[2, j2]+···+H[`, j`
] ≤ d (the total hardness of all the blocks on the path is no more
than the initial drill hardness);
• G[1, j1] + G[2, j2] + ··· + G[`, j`
] is maximum (the path collects the maximum amount of gold
possible).
Follow the dynamic programming paradigm given in class (the “five step” process) to give a detailed
solution to this problem. Make sure to keep a clear distinction between each of the steps, and to
explain what you are doing and why at each step — you will not get full marks if your answer
contains only equations or algorithms with no explanation or justification.
H[1,1],G[1,1] H[1,2],G[1,2] ··· H[1,n],G[1,n]
H[2,1],G[2,1] H[2,2],G[2,2] ··· H[2,n],G[2,n]
.
.
.
.
.
.
.
.
.
.
.
.
H[m,1],G[m,1] H[m,2],G[m,2] ··· H[m,n],G[m,n]
Figure 1: General form of the input matrix.
2,2 2,7 0,0 2,3 1,8
2,2 0,0 1,2 2,0 1,1
1,4 1,1 2,6 2,1 3,8
Figure 2: Sample input with optimum path shown in bold (for d = 4).
3 Page 3 of 3