CS 6363: Algorithm D esign and Analysis − Spring 2022Homework # 3 − D ue: March 22Professor D.T. HuynhProblem #1. Do Problem #15.5-1 in [CLRS], page 403.Problem #2. Generalize Huffman’s algorithm to ternary codewords (i.e. codewords using the symbols 0, 1, 2), and prove that it yields optimal ternary codes.Problem #3. (Coin changing)Consider the problem of making change for n cents using the least number of coins.1. Describe a greedy algorithm to make change consisting of quaters, dimes, nickels, an dpennies. Prove that your algorithm yields an optimal solution.2. Suppose that the available coins are in the denominations c0, c1, . . . , ckfor some integersc > 1 and k ≥ 1. Show that the greedy algorithm always yields an op timal solution.3. Give a set of coins denominations for which the greedy algorithm does not yield an optimalsolutionProblem #4. Do Problem # 16.4-5 in [CLRS], page 443.Problem #5. Do Problem # 21.2-2 [CLRS ], p . 567] and Problem # 21.3-1 [CLRS], p. 572].Problem #6. Give an efficient algorithm for computing th e tr an sition function δ for the string-matching automaton corresponding to a pattern P . Your algorithm should r un in time O(m|Σ|).(Hint. Prove that δ(q, a) = δ(π[q], a) if q = m or P [q + 1] 6= a.)Problem #7. Do Problem # 32.4-7 in [CLRS], page