Tasks

1. (2 pts) Chapter 4 Projects and Problems: 5
• also convert your real tag answer to binary
2. (2 pts) Chapter 4 Projects and Problems: 6
3. (4 pts) Assume a 2 symbol input alphabet (a₁, a₂} with probabilities {.6, .4}, respectively. Use arithmetic encoding (without scaling) to derive a binary encoding of the following two strings:
1. a₁ a₁ a₂
2. a₂ a₂ a₂
4. (2 pts) Given an alphabet {a,b,c,d} with respective expected probabilities {.1,.3,.4.,.2}, decode the value .75 as a 8 symbol string.
5. (2 pts) Encoding without scaling. To prepare for this question, review Example 4.3.5. Consider an alphabet {a₁, a₂, a₃} with underlying probabilites of {.7, .1, .2}. Encode the string a₁a₂a₃a₂ using base 10. Then convert your answer to binary.
6. (2 pts) Decoding without scaling. Using the same alphabet and probabilities as the previous question, decode the value .5590 as a 4 character string.
7. (2 pts) Encoding with scaling. To prepare for this question, review Example 4.4.2. Using the same alphabet and probabilities of the previous two questions, encode the string: a₂a₃a₁a₃.
• Submit your answer in binary.
• Only apply scaling rules E₁and E₂, not E₃.
• In example 4.4.2, the first calculation of u⁽³⁾ - "(0.8 - 0.312)" should say "(0.6 - 0.312)"
8. (2 pts) Decoding with scaling. To prepare for this question, review Example 4.4.3. Using the same alphabet and probabilities as the previous three questions, decode the binary value 10011011 as a 5 character string.
• Only apply scaling rules E₁and E₂ , not E₃.
• In decoding with scaling, the wordsize technically must be recomputed at each iteration. For simplicity in this problem, use a word size of 6 bits at each step. (If you do not know what this item means, ASK the professor.)
• In example 4.4.3, the first calculation of u⁽³⁾ - "(0.8 - 0.312)" should say "(0.6 - 0.312)"
9. (2 pts) Encoding with scaling. Using the alphabet {a,b,c,d} and probabilities {.2, .4, .2, .2}, encode the string: adaa.
• Submit your answer in binary.
• Only apply scaling rules E₁and E₂, not E₃.
10. (2 pts) Decoding with scaling. Using the same alphabet and probabilites of the previous question, decode the binary value 110010011 as a 3 character string.
• Only apply scaling rules E₁and E₂ , not E₃.
• For this problem, use a word size of 7 bits at each step.

Notes

1. Graduate students must do all assignments individually. Undergraduate students may collaborate in groups of 2 for assignments. Only one submission with both names should be turned in from a group.
2. Clearly label your answers, and please submit answers in the order assigned.
3. (repeated from course syllabus) Academic Honesty: Unless explicitly stated otherwise, students are not permitted to access or compare any homework, or program-project answers with those of any other student or group past or present, alive or dead, or any Internet web site prior to submitting the assignment. Comparing answers, or getting answers off the Internet before submitting one's work is considered cheating. If you do not have time to complete an assignment, it is better to submit partial solutions than to get answers from someone else. While it is obviously difficult to enforce this policy, students who do not follow this policy should be keenly aware that in this class, they a re cheating, and if caught, will be prosecuted according to University guidelines. This applies both to the student (or group) who gets answers and the student (or group) who gives answers.
4. (repeated from course syllabus) Lateness Policy: Assignments are due at the beginning of class. Unexcused late assignments will be penalized up to 10% per school day (weekends do not count) up to a 2-day maximum penalty of 20%. Without prior discussion with the professor, assignments will not be accepted more than two school days late without a university approved excuse.