1) Please look http://www.cs.rpi.edu/~moorthy/Courses/CSCI2300/coin-change.cc For calculating the average coins required http://www.cs.rpi.edu/~moorthy/Courses/CSCI2300/coin-change1.cc with 50 cents the average is 4.4 and with out 50 cents coins the average is 4.7 http://www.cs.rpi.edu/~moorthy/Courses/CSCI2300/coin-change2.cc 10 cents could be changed with two 5 cents coins - where as greedy algorithm uses 6 coins. This is due the change denominations. 5.37 Why does it work. Suppose we had another order which is not the sorted order (which gives minimum latency) - Now interchanging any one of higher service time (say i in that order)with lower service time (say j in that order) will reduce the waiting times of all jobs between thse two (and including these two) and hence a contradiction. 5.18 a Use the code http://www.cs.rpi.edu/~moorthy/Courses/CSCI2300/Huffman2.cc and use count = 27 and the data is in http://www.cs.rpi.edu/~moorthy/Courses/CSCI2300/data-Lab7 The data as in on line (book) pdf version (I have a suspicion that the data given in the book is wrong as the frequency sums to 101% instead of 100%) 3:21pm>>g++ Huffman2.cc 3:21pm>>a.out < data-Lab8 | m Char Symbol Code r 48 0000 h 49 0001 u 24 00100 c 26 00101 s 51 0011 e 102 010 n 55 0110 i 58 0111 o 59 1000 b 13 100100 y 16 100101 p 16 100110 g 17 100111 a 68 1010 l 34 10110 d 35 10111 t 77 1100 f 18 110100 w 19 110101 m 21 110110 v 9 1101110 k 6 11011110 j 2 110111110 x 2 1101111110 q 1 11011111110 z 1 11011111111 - 183 111 Total Cost 4201. Average bits per symbol 4.15941