In Problem 3 :

P0=2----->2+5 =7 then

P1=6-----> 6+5=11 then

P2=10----->10+5=15 then (mim number of stops)

P5=15----->15+5=20 then

P6=20----->20+5=25

Problem 3 (15 points) You are head of SafariRus, a company that organizes camel trips in the desert around Kuwait. You are getting many requests and your goal is to build the optimal desert "safari. You are given a list of n recreation points P1, P2, ..., prin the desert and their distance from SafariRUs headquarters (treat this as the starting point po). Your goal is to travel from po to Pn in the minimum number of stops. The only problem is that your camels cannot travel more than C kilometres without making a stop at one of the recreation points. For example, assume the distances from the headquarters po are given by the array below and C = 5: 2 10 | 12 | 14 | 15 20 If you stop at distance 2, then 6, then 10, skip 12 and 14, then stop at 15, and finally at 20, a total of 5 stops are required in order to reach the destination. Notice that distances among stops are all less than or equal to C(=5). Your goal in this problem is to come up with a greedy strategy for this problem and explain why it is optimal. 6 O e Problem 4 (20 points) a) (3 pts) Which of the following cannot be correct Huffman encodings? Justify your answer by drawing the corresponding Huffman trees and point to possible mistakes. {ab, ba} {a, ba, bb} {a, ba, ab, bb) {aa, ab, ba, bba b) Consider the following table showing the frequency of various letter in a ile. Letter a b d Frequency 20% 40% 20% 10% 10% Encoding 01 1 000 0010 0011 (3 pts) Prof. Dimitriou came up with an encoding for each character which is shown above. Is this a valid encoding that could have been produced by the Huffman algorithm? Explain. (4 pts) Come up with a different Huffman tree whose height is three. Show your work. To ease grading, when combining trees always pick the smallest letter(s) or the subtree(s) containing the smallest letter(s). (2 pts) Compute the average length of each encoding for the 5 characters. Are they the same? (4 pts) Encode the sequence bacbab with Prof. Dimitriou's encoding. Suppose now the first bit is received in error. How many characters will be wrong during the decoding process? Do the same for your encoding. What happens in this case? (4 pts) Repeat the above assuming the 3rd bit is flipped during transmission. Is one of the encodings better than the other with respect to wrong decoded characters