CS 6363 Fall 2023 HW3 Solution Tan Lam September 30 2023 Problem 1 10 pts Problem Problem 15 5 1 p 403 CLRS Write pseudocode for the procedure Construct Optimal BST root which given the table root outputs the structure of an optimal binary search tree For the example in Figure 15 10 your procedure should print out the structure k2 is the root k1 is the left child of k2 d0 is the left child of k1 d1 is the right child of k1 k5 is the right child of k2 k4 is the left child of k5 k3 is the left child of k4 d2 is the left child of k3 d3 is the right child of k3 d4 is the right child of k4 d5 is the right child of k5 corresponding to the optimal binary search tree shown in Figure 15 9 b Answer Algorithm 1 CONSTRUCT OPTIMAL BST root 1 m 1 print k root 1 m is the root 2 CONSTRUCT OPT SUBTREE 1 root 1 m 1 lef t k root 1 m root 3 CONSTRUCT OPT SUBTREE root 1 m 1 m right k root 1 m root Algorithm 2 CONSTRUCT OPT SUBTREE i j childtype parent root print d j is the childtype child of parent 1 if j i then 2 3 end 4 print k root i j is the childtype child of parent 5 CONSTRUCT OPT SUBTREE i root i j 1 lef t k root i j root 6 CONSTRUCT OPT SUBTREE root i j 1 j right k root i j root 1 Problem 2 10 pts Answer Problem Generalize Huffman s algorithm to ternary codewords i e codewords using the symbols 0 1 2 and prove that it yields optimal ternary codes Algorithm 3 Ternary Huffman Input A set of symbols C using ternary codewords 0 1 2 with probability distribution f C R s t f c 1 cid 88 c C Output Optimal ternary codes for C 1 Q C 2 for i 1 to C 2 do 3 4 5 Create a new node w Let x y and z be 3 roots of 3 trees in Q with least probabilities Assign x y and z to the children of w f w f x f y f z 6 7 end 8 if There are only two trees left at the last iteration then 9 10 end Combine them Correctness 1 Let a b and c be three sibling nodes in max depth of T and let x y and z be the nodes with least probabilities Without loss of generality we assume f a f b f c and f x f y f z Then we have f x f a f y f b and f z f c We swap x and a and produce T We swap y and b and produce T We swap z and c and produce T Then B T B T f c dT c cid 88 c C f c dT c cid 88 c C f a dT a f x dT x f a dT a f x dT x f a dT a f x dT x f a dT x f x dT a f a f x dT a dT x 0 Similarly B T B T 0 and B T B T 0 Thus we have B T B T But since T is optimal we have B T B T Therefore B T B T 2 Let T be the tree representing optimal prefix code for ternary codewords We use same x y and z in 1 and let u be the parent node of them Then we have f u f x f y f z and T T x y z We claim that T is the optimal prefix code for C C x y z u 2 Proof For every c C x y z we have dT c dT and f c dT c f c dT c Since dT x dT y dT z dT u 1 f x dT x f y dT y f z dT z f x f y f z dT u 1 f u dT u f x f y f z Thus B T B T f x f y f z If T is not an optimal prefix code for C then there exists another tree T s t B T B T because u C and is a leaf of T If we add x y and z as children of u in T then we obtain a prefix ocde for C with B T f x f y f z B T This contradicts the claim T is optimal Thus T should be an optimal prefix code for C From 1 and 2 above the algorithm is correct 3 Problem 3 30 pts Problem 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 quarters dimes nickels and pennies Prove that your algorithm yields an optimal solution 10 pts 2 Suppose that the available coins are in the denominations c0 c1 ck for some in tegers c 1 and k 1 Show that the greedy algorithm always yields an optimal solution 10 pts 3 Give a set of coins denominations for which the greedy algorithm does not yield an optimal solution 10 pts Answer Problem 3 1 Algorithm 4 Coin changes Input n Output The least number of coins 1 n1 n div 25 2 r1 n mod 25 3 n2 r1 div 10 4 r2 r1 mod 10 5 n3 r2 div 5 6 r4 r2 mod 10 7 return n1 n2 n3 n4 Correctness We now prove that the greedy algorithm Coin changes is optimal First we prove the following claim Claim 1 Let n1 n2 n3 n4 be an optimal solution where n1 n2 n3 n4 are the number of quarters dimes nickels and pennies respectively Then 0 n2 2 0 n3 1 and 0 n4 4 Proof Suppose by contradiction that there exists an optimal solution n1 n2 n3 n4 where 4 n1 n2 3 Let m n1 n2 n3 n4 Consider another solution n 4 25 n1 1 10 n2 1 n2 3 n3 1 n4 It is easy to see that 25n 3 n 1 10n 1 n 3 5 n3 1 n4 25n1 10n2 5n3 n4 n and that n 4 n1 4 is a better solution than 1 n2 3 n3 1 n4 m 1 m Thus n 3 n n1 n2 n3 n4 which is contradiction Therefore n2 2 Analogously we can prove that n3 1 and n4 4 2 5n 2 n 1 n 2 n 1 n 2 n 3 n 3 n We now return to the main problem Let g1 g2 g3 g4 be the output of Coin changes for an input n then 25g1 10g2 5g3 g4 n and g1 is as large as possible due to the nature of the greedy algorithm Let n1 n2 n3 …
View Full Document
Unlocking...