Computer Science Homework Help

I’m working on a computer science discussion question and need support to help me study.

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
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 P
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.