CSC 3102 Chapter : 3102 Hw3
Document Summary
Due november 16, 2010 (in class: (20 points) a string is palindromic if it is equal to its reverse. e. g. , abcabacba. Give a linear time algorithm to nd the period of a string: (20 points) draw the frequency array and a hu man tree for the following string: dogs do not spot hot pots or cats . Now also show how many bits does the hu man encoding of this string take: (20 points) in order to celebrate your birthday, you go to an all you can eat bu et restaurant to have a big dinner. There are n distinct dishes, each has a di erent volume (which is an integer) v1, v2, , vn. It is obvious that your stomach capacity, v (which is also an integer), is not large enough to hold all the dishes. Also, some dishes are expensive (as per the menu price) and some are not.
