College of Computer & Information Science Fall 2006 Northeastern University Handout 1 CSU690: Algorithms and Data 8 September 2006

Problem Set 1 (due Tuesday, September 19)

1. (4 points) Chapter 1, Exercise 1, page 22.

2. (12 points) Chapter 1, Exercise 4, page 23.

3. (10 points) Recursion and induction in binary codes

Digital transmission protocols transmit signals using binary codes. In order to minimize the effect of errors, it is often useful to select a code such that “similar” signals use “similar” codewords.

One such code is a list of 2^{n} n-bit strings in which each string (except the first) differs from the previous one in exactly one bit. Let us call such a list a twiddling list since we go from one string to the next by just flipping one bit.

Consider the following recursive algorithm for listing the n-bit strings of a twiddling list. If n = 1, the list is 0,1. If n > 1, first take a twiddling list of (n − 1)-bit strings, and place a 0 in front of each string. Then, take a second copy of the twiddling list of (n − 1)-bit strings, place a 1 in front of each string, reverse the order of the strings and place it after the first list. So, for example, for n = 2, the list is 00,01,11,10, and for n = 3, we get 000,001,011,010,110,111,101,100.

Prove by induction on n that (a) every n-bit string appears exactly once in the list generated by the algorithm, and (b) each string (except the first) differs from the previous one in exactly one bit.

4. (12 points) Chapter 2, Exercise 6, page 68.

5. (10 points) Ordering functions

Arrange the following functions in order from the slowest growing function to the fastest growing function. Briefly justify your answers. (Hint: It may help to plot the functions and obtain an estimate of their relative growth rates. In some cases, it may also help to express the functions as a power of 2 and then compare.)

n^{1/3} n + lg n n(lg n)^{5} 2^{\sqrt{lg n}} lg n

6. (3 × 4 = 12 points) Properties of asymptotic notation

Let f(n), g(n), and h(n) be asymptotically positive and monotonically increasing functions. For each of the following statements, decide whether you think it is true or false and give a proof or a counterexample.

(a) f(n) + g(n) = Θ(max{f(n), g(n)}).

(b) If f(n) = Ω(h(n)) and g(n) = O(h(n)), then f(n) = Ω(g(n)).

(c) If f(n) = O(g(n)), then f(n)^{2} is O(g(n)^{2}).