# Homework 1

Due: September 12th, 2012 at the beginning of class
Homework turned in after class will not be accepted.
Homework turned in during class but after I have collected it will lose 20%.
85 total points

Do your own work for this assignment; do not work with others. Consult the book and your professor for help if you need it. Please write neatly, or preferably type your answers. Use good grammar, spelling, and complete sentences.

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) C++ 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 lecture 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:

```sum = 0;                      // c1
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 C function `clock()` before the code fragment runs, saving its result, then running the code fragment many times, then calling `clock()` again and finding the difference between the two calls. The value that `clock()` returns is in units of `CLOCKS_PER_SEC`. Both `clock()` and `CLOCKS_PER_SEC` are defined in `<ctime>`.

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.