COS 111, Fall 1999 - Problem Set 4

Due by 5pm, Tuesday Oct. 19, 1998

Show your work on all problems. Without it, we can't give partial credit.

Problem 1
Consider the simple compression scheme based on run-length encoding that we looked at in lecture. Recall that in a 10-bit "chunk" we could represent some single bit repeated up to 255 times by writing a leading 0, followed by the bit to repeat, followed by an 8-bit binary number representing the number of repetitions (a run-length encoding). Alternatively, we could in this 10-bit "chunk" represent a 9-bit sequence by writing a leading 1, followed by the 9 bits of the sequence. In this scheme, for more than 9 repetitions of a bit, it makes sense to use the run-length encoding.

Consider compressing with this scheme a simple bit sequence consisting of n repetitions of the bit 0 followed by 90 bits of 0's and 1's that have no repetitions longer than 8. What does the value of n have to be to get a compressed representation that is 80% the length of the original sequence?

Problem 2
Brookshear, Chapter One Review Problem 60, pg. 75.

Problem 3
Brookshear, Chapter One Review Problem 7, parts a and d, pg 71.

Problem 4
Brookshear, Chapter One Review Problem 58, pg 75.

Problem 5
Brookshear, Chapter Two Review Problem 5, pg. 108. Assume the machine has a subtraction instruction, unlike Brookshear's machine of Appendix C.)

Problem 6
Brookshear, Chapter Two Review Problem 11, pg. 109.


Back to Schedule and Assignments