Computer Science Homework Help

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.