CS 6363 Algorithm D esign and Analysis Spring 2022 Homework 3 D ue March 22 Professor D T Huynh Problem 1 Do Problem 15 5 1 in CLRS page 403 Problem 2 Generalize Hu man 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 and pennies Prove that your algorithm yields an optimal solution 2 Suppose that the available coins are in the denominations c0 c1 ck for some integers c 1 and k 1 Show that the greedy algorithm always yields an optimal solution 3 Give a set of coins denominations for which the greedy algorithm does not yield an optimal solution Problem 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 e cient algorithm for computing the transition function for the string matching automaton corresponding to a pattern P Your algorithm should run 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 1012