This is a theory of algorithms type of assignment. The
assignment.docxis what I want you to do. Anywhere that you see the red question marks is what you have to do.
YOU MUST SHOW YOUR WORK!I would like to understand it. Upon you sending back the answers, I will check it immediately and let you know if it's right.
Question 1 Given the following profits and weights of items below: Item I0 I1 I2 I3 I4 I5 I6 I7 Profit 25 15 40 40 10 30 25 20 Weight 5 3 4 40 5 10 10 10 Knapsack capacity is 35. For each item below, write the fraction of the item is to be taken. · If the entire item is taken, write 1. If the item is not taken, write 0. · For fraction write x/y to represent the fraction. For example, if half of the item is taken, write 1/2; if a quarter is taken, write 1/4, etc. Write in simplified form, i.e., don't write 6/14, but write 3/7 instead. · Only write numbers for the answers. In case of ties in the ratio, break it in favor of the item with the lower index, i.e., a tie between say I0 and I1 is broken in favor of I0. 1. I0: ? ⇐ FIND THIS ANSWER 2. I1: ? ⇐ FIND THIS ANSWER 3. I2: ? ⇐ FIND THIS ANSWER 4. I3: ? ⇐ FIND THIS ANSWER 5. I4: ? ⇐ FIND THIS ANSWER 6. I5: ? ⇐ FIND THIS ANSWER 7. I6: ? ⇐ FIND THIS ANSWER 8. I7: ? ⇐ FIND THIS ANSWER The total profit earned is ? ⇐ FIND THIS ANSWER Question 2 For a message, we have the following set of characters and respective frequencies. Assume 8-bit ASCII characters and Σ= {A, Y, R, X, T, Z} Letter A Y R X T Z Frequency 260 70 310 180 30 150 The number of bits needed by ASCII encoding is ? ⇐ FIND THIS ANSWER Only write numbers for the answer; Question 3 For a message, we have the following set of characters and respective frequencies. Assume 8-bit ASCII characters and Σ= {A, Y, R, X, T, Z} Letter A Y R X T Z Frequency 260 70 310 180 30 150 For fixed length encoding, 1: the number of bits needed to represent each character is ? ⇐ FIND THIS ANSWER 2: the total number of bits needed to encode the message is ? ⇐ FIND THIS ANSWER 3: the number of bits needed for the mapping table is ? ⇐ FIND THIS ANSWER Only write numbers for the answers. Question 4 For a message, we have the following set of characters and respective frequencies. Assume 8-bit ASCII characters and Σ= {A, Y, R, X, T, Z} Letter A Y R X T Z Frequency 260 70 310 180 30 150 We create the Huffman tree as usual, with the added clause that whenever you merge two nodes as the children of its parent, then the node with the smaller frequency becomes the left child. As usual, traversal down a left branch results in a 0, whereas down a right branch results in a 1. For each of the following characters, write the encoded bit-string representing the character 1. A: ? ⇐ FIND THIS ANSWER 2. Y: ? ⇐ FIND THIS ANSWER 3. R: ? ⇐ FIND THIS ANSWER 4. X: ? ⇐ FIND THIS ANSWER 5. T: ? ⇐ FIND THIS ANSWER 6. Z: ? ⇐ FIND THIS ANSWER Based on the above, the total number of bits needed to encode the message is ? ⇐ FIND THIS ANSWER The number of bits needed for the mapping table is ? ⇐ FIND THIS ANSWER Only write numbers for the answer.