Due: Wednesday, Jan. 22, beginning of class

Hints/clarifications added to problems 5 and 6 (1/18/03)

Total: 100 points

- (5, 5, 5: 15 points) Problem 1.8 in the text, parts (a), (b), and (c).
- (5 points) Problem 1.10 in the text.
- (5, 5: 10 points) Problem 1.12 in the text, parts (a) and (b). Hint: For (b), use induction.
- (8 points) Problem 2.1 in the text.
- (7 points) Simplify the following expressions as much as possible using the Big-Oh notation (express each as big-oh of some function of N e.g. 3 N + log N = O(N)). You don't need to give the constants c and n
_{0}for this problem, but for practice, try finding them for some of your answers.N

^{3}+ 100 N 100 N^{4}+ N log N 2 N^{2}+ N + 2^{100}3 log log N + log^{2}N log log (N^{2}) + 3 log^{2}(N^{2}) 10 N^{2}+ 5 N + N^{3}log N 2.5^{N}+ N^{100} - (10, 15, 5: 30 points) Problem 2.7, parts (a), (b), and (c). For part (b), present your
results as a graphical plot of running time versus N. Use a large enough range of values for N such as N = 10, 100, 1000, 10000, 100000, etc... For part (c), plot your big-oh functions from (a) and compare the plots to those you got in (b).

Hints: To measure run time, you can use the unix "time" command (type "man time" for more info) or embed code for timing within your programs. For example, in Java, you could store the value returned by System.currentTimeMillis() in a variable before you execute your code and in a different variable after, and find the difference between the two to get the run time. In C++, you may use time.h and the clock() command. - (5, 5: 10 points) Estimate the running times of the following functions using the Big-Oh notation (write your answer as big-oh of some function of N):
int fun_a(int N) { if (N<=1) return 100; else return 2*fun_a(N-1); } int fun_b(int N) { if (N<=1) return 100; else return fun_b(N/2) * fun_b(N/2 - 1); }

- (15 points total) Problem 2.20, all parts (a)-(f). For part (a), write your program
as a method, similar to Example 2.4.1 in the text.

(Note: A number N is prime if the only positive integers that divide N (with remainder 0) are 1 and N itself. For example, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, etc., are prime.)