CSCI 3110 Assignment 4 posted: 11.06.2021
Instructor: Travis Gagie due: midnight 18.06.2021
You can work in groups of up to three people. One group member should submit a copy of the solu-
tions on Brightspace, with all members’ names and banner numbers on it; the other group members
should submit text files with all members’ names and banner numbers (otherwise Brightspace won’t
let us assign them marks!). You may consult with other people but each group should understand
the solutions: after discussions with people outside the groups, discard any notes and do something
unrelated for an hour before writing up your solutions; it’s a problem if no one in a group can ex-
plain one of their answers. For programming questions you should submit your code, which should
compile and run correctly to receive full marks.
1. You have a week to complete an assignment with several questions, each worth the same
number of marks. You don’t want to spend more than h hours on the whole assignment
and you can estimate accurately how many hours each question will take you. Give a greedy
algorithm to decide which questions to answer. PROVE YOUR ALGORITHM CORRECT!
2. Your professor is training to run against his friend Simon, but he’s not sure he can make it
around his whole planned route in one go, so he’s made a list of places where he can stop for
a break, coffee, etc. (For example, if he starts at the shipyards and runs along the coast, he
can stop at the Tim Horton’s by the ferry terminal, then in the Salt Yard, then at one of the
restaurants along the waterfront, then at the Garrison Brewery or Tomavinos by the Seaport
Market, then at the entrance of Point Pleasant, then at the top of Arm Road in the park,
etc etc.) Suppose he gives you this list, with the distance between each consecutive pair of
potential pitstops, and the distance d he can run without stopping. Give a greedy algorithm
that tells him where to stop such that 1) he never runs more that distance d without a break
and 2) he makes the minimum number of stops. PROVE YOUR ALGORITHM CORRECT!
3. A cross parsing of a string S[1..m] with respect to a string T [1..n] is a partition of S into a
minimum number of substrings each of which occurs in T . Suppose you are given an array
L[1..m] such that, for 1 ≤ i ≤ m, the substring S[i..i+L[i]− 1] occurs in T but the substring
S[i..i+L[i]] doesn’t. Give a greedy algorithm for computing a cross parsing of S with respect
to T . PROVE YOUR ALGORITHM CORRECT!
4. According to https://www150.statcan.gc.ca/t1/tbl1/en/tv.action?pid=1710000901, the
populations of Canada’s provinces and territories in the first quarter of 2021 were as follows:
1
https://www150.statcan.gc.ca/t1/tbl1/en/tv.action?pid=1710000901
Newfoundland and Labrador 520,438
Prince Edward Island 159,819
Nova Scotia 979,449
New Brunswick 782,078
Quebec 8,575,944
Ontario 14,755,211
Manitoba 1,380,935
Saskatchewan 1,178,832
Alberta 4,436,258
British Columbia 5,153,039
Yukon 42,192
Northwest Territories 45,136
Nunavut 39,407
Suppose we choose a resident of Canada uniformly at random and let X be the province or
territory where they live.
(a) Compute the entropy (in bits) of the random variable X.
(b) Compute
∑
i pidlg(1/pi)e, where pi is the probability the resident of Canada lives in the
ith province or territory listed above.
(c) Build a Huffman code for the probability distribution p1, . . . , p13; what is its expected
codeword length?
5. Suppose you have season passes for m train lines between n cities, with different expiry dates.
A ticket lets you travel on the line between two cities as many times as you like, in either
direction, from now until the ticket expires. How can you quickly determine the last date on
which you will be able to reach any city from any other city using your passes?
(a) Give a solution with the union-find data structure that takes O(mα(m,n)) time after
you’ve sorted the passes by expiry date.
(b) Give a solution that colours and re-colours the cities, that takes O(m) time after you’ve
sorted the passes by expiry data.
You need not prove your solutions correct.
2