Fundamental Algorithms, Spring 1998

Assignment 1. Review of mathematical foundations.

Given January 21, due February 4.

1.
For which of the following functions is it true that f(2n) = O(f(n)) as tex2html_wrap_inline27 ?
a.
f(n) = n.
b.
tex2html_wrap_inline31 .
c.
tex2html_wrap_inline33 .
d.
tex2html_wrap_inline35 .
e.
tex2html_wrap_inline37 .
2.
A certain algorithm works collections triangles. After n passes of the algorithm, the are T ``active'' triangles and P ``passive'' ones. In a pass of the algorithm, each active triangle is turned into 3 active triangles and 7 new passive ones. All the old passive triangles remain unchanged. Starting with a single active triangle, how many triangles will there be after n passes? Show that this is tex2html_wrap_inline51 .
3.
Use the fact that tex2html_wrap_inline53 to show that

displaymath16

4.
A data compression algorithm takes time proportional to tex2html_wrap_inline55 to compress a block of n bytes of data. The program compresses a large data set by breaking it into blocks of n bytes and compressing these blocks one after another. The program takes 30 minutes to compress a gigabyte (GB) of data in 512 byte blocks. Assuming that all the time is spent in the compression algorithm, how long would it take to compress the same data if the block size were increases to 1 KB?