CSE 326 - Winter 2003

Assignment 1

Assigned: Monday, Jan. 13
Due: Wednesday, Jan. 22, beginning of class
Hints/clarifications added to problems 5 and 6 (1/18/03)

This assignment is designed to give you practice with the concepts introduced in class. This is a written assignment; there is no electronic turn-in. However, you are required to write some very small programs, measure their running times, and generate graphs (for example, with Excel or Gnuplot). The textbook problem numbers below are the same for the Java and C++ versions of the textbook.

Total: 100 points

  1. (5, 5, 5: 15 points) Problem 1.8 in the text, parts (a), (b), and (c).
  2. (5 points) Problem 1.10 in the text.
  3. (5, 5: 10 points) Problem 1.12 in the text, parts (a) and (b). Hint: For (b), use induction.
  4. (8 points) Problem 2.1 in the text.
  5. (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 n0 for this problem, but for practice, try finding them for some of your answers. 
      N3 + 100 N

  100 N4 + N log N

  2 N2 + N + 2100

  3 log log N + log2 N

  log log (N2) + 3 log2 (N2)

  10 N2 + 5 N + N3 log N

  2.5N + N100
  6. (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.

  7. (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);
}
  8. (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.)