CS 170 Reading Quiz -- Week 8, Monday

Please fill out this quiz, and press the "Submit" button at the end. Don't collaborate with anyone on quiz exercise solutions.

Please answer all questions.

Name:

SID: [No spaces and no dashes.]

1. Suppose we have some alphabet, and we are given the frequency of each letter in the alphabet. Suppose we use the Huffman coding technique to build an optimal variable-length prefix-free binary encoding for this alphabet. Professor Argyle makes the following claim:

Let X,Y be any pair of letters in the alphabet. If the frequency of X is less than the frequency of Y, then the encoding of X is guaranteed to be at least as long as the encoding of Y.

Is Prof. Argyle's claim correct? Briefly, why or why not?

2. Given n, define the function F(x,y) like this:

F(x,0) =   F(x+1,0) + F(x+1,1)   if x<n
F(x,1) = 2 F(x+1,0) + F(x+1,1)   if x<n
F(n,0) = 1
F(n,1) = 0

Suppose we want to efficiently compute F(1,1), given n. How should we do it? What will the running time be, as a function of n? Use O(.) notation. For simplicity, assume that it takes O(1) time to add or multiply a pair of integers (no matter how large).

(Revised 3/14:) To qualify as "efficient", it's enough that your answer be strictly faster than exponential time. (Exponential time is too slow.)

3. (This question will not be graded, it is solely to survey the class to find your preferences.)

Which of the following options would you prefer? (Note that Midterm 2 will be held on Monday, April 6.)

Option (1): HW9 is due Friday, April 3 (just before the midterm). There is no homework due Friday, April 10 (you get a week off after the midterm to recover and take it easy).
Option (2): There is no homework due Friday, April 3 (you get a week off before the midterm to study for the exam). HW9 is due Friday, April 10.

Either way, the difficulty level of HW9 would be the same. Do you have a preference between these two options? If yes, which do you prefer?

4. What did you find difficult or confusing about the reading or the lectures, and what would you most like to see explained better? If nothing was difficult or confusing, and you understand the material pretty well, tell us what you found most interesting. Please be as specific as possible.

CS 170 home page