Homework 1

Assignment

• 1. (10 points) You have probably heard of the Fibonacci sequence, where each number in the sequence is the sum of the previous two numbers.

  Your professor has recently developed the extended Fibonacci sequence, where each number in the sequence is the sum of the previous three numbers. The base cases are efibonacci(1)=1, efibonacci(2)=1, efibonacci(3)=1.

  Give a correct recursive (no loops or arrays) Java function that computes the new extended Fibonacci sequence for any integer n. THINK ABOUT NON-POSITIVE INPUTS; non-positive inputs should continue the sequence. An example of the input (starting from one) and output of this function is:

  ...
  efibonacci(1) = 1
  efibonacci(2) = 1
  efibonacci(3) = 1
  efibonacci(4) = 3
  efibonacci(5) = 5
  efibonacci(6) = 9
  efibonacci(7) = 17
  ...
  

  Your code must be concise. My solution is 8 lines long. Explain why your code works, and give some examples of the answers it gives for various inputs, including large values.


• 2. (10 points) Discuss in what ways your solution for the extended Fibonacci sequence is or is not a good solution (think about efficiency, correctness, readability). Consider the rules of recursion given in class and in the book.


• 3. (10 points) Exercise 2.1 in your textbook.


• 4. (10 points) Exercise 2.6 in your textbook.


• 5. (30 points) Exercise 2.7 in your textbook. For parts 1-4, label each finite-time statement with its own constant as we have in class (i.e. c1, c2, etc.). For example, code fragment (1) should be labeled as:

                              // COST   TIMES
sum = 0;                      // c1     1
for (int i = 0;               // c2
               i < n;         // c3
                      i++) {  // c4
    sum++;                    // c5
}

For parts 1-4, show how you assigned constants for each code fragment, give a precise T(n) for each function before giving your big-Oh answer. For parts 5 and 6, just give a big-Oh answer. Give your code that tests and times each function.

When timing these code fragments, use values of n that vary enough to show clear trends in the running times. Also, you should run each function many times in a row so that the running time is not zero (which isn't meaningful). You can time your code by calling the Java function System.nanoTime() before the code fragment runs, saving its result, then running the code fragment many times, then calling System.nanoTime() again and finding the difference between the two calls. The value that System.nanoTime() returns is in units of nanoseconds.


• 5. (20 points) Pages 31-32 in your textbook describe how to determine the rank of two functions in little-oh notation using limits. Use this method to rank the following functions in terms of their relative growth rates:
  1. a) f(n) = log(n), g(n) = log²(n)
  2. b) f(n) = 3ⁿ, g(n) = 2ⁿ
  3. c) f(n) = log(n), g(n) = n
  4. d) f(n) = 5n, g(n) = n
  Show your work. Use l'Hôpital's rule where appropriate. Your final answers should indicate whether f(n) = o(g(n)), g(n) = o(f(n)), or f(n) = Θ(g(n)).


• 6. (5 points) What is the tightest big-Oh running time one can expect of an algorithm that takes as input an array of length n, and prints out every unique permutation of that array? Remember that a permutation is a shuffling of the order of the elements of the array. Keep in mind the time it takes to print out each array. Explain your answer.


• 7. (10 points) Do parts (a) and (b) of exercise 2.10 from your textbook. Explain your answers. For this problem, imagine that N is unbounded.

Unrelated...

Check this out. It is a good cause; together we can support our wounded warriors.