Programming and Algorithms II
Degree in Bioinformatics
Fall 2018

***************************************************
*** Lab 3:                                      ***
*** Fibonacci numbers and flattening lists      ***
***************************************************

Part 1:

The Fibonacci numbers fib(0), fib(1), fib(2), fib(3), 
are defined recursively as follows:

fib(0) = fib(1) = 1

and 

So the first elements of the sequence are 1, 1, 2, 3, 5, 8, 13, 21, ...

1. Write a recursive function fib(n) that implements this definition directly, 
i.e. on fib(n) it makes recursive calls to fib(n-1) and fib(n-2). 
Take care with the base case(s)

2. Observe that the running time grows pretty fast. In my machine,
n=35 already takes several seconds.

3. If you look closely you will see that fib(n) will call 1 time 
fib(n-1), 2 times fib(n-2), 3 times fib(n-3), 5 times fib(n-4), 8 times fib(n-5),
13 times fib(n-6), etc. Draw a tree of calls to convince yourself of this fact.

How many times will fib(n-i) be called? How many times will fib(1) (base case)
be called?

The numbers fib(n) grow approximately as g^n, where 
g=1.680... is called the "golden ratio" number. We will see why in theory.
Therefore, fib(n) takes exponential time in n.

4. Give a more efficient algorithm that works for n>1 
with the following header: 

def fib2(n):
    "for n>1, returns a tuple containing fib(n) and fib(n-1)"

If you do it well, it makes n recursive calls and makes O(n) recursive calls.
(Or O(n) iterations if you do it iteratively).
Also, it is easy to make iterative (while it is not obvious how
to make the first program iterative).

Addendum (optional but recommended at least to understand):
As sad before, fib(n) is approximately g^n.
Therefore the $n$th fibonacci number has about log_10(g^n) = O(n) digits.
Therefore performing additions on such numbers takes time O(n), bccause
addition is linear. 
Therefore actually the call to fib2(n) takes time O(n^2).

Verify this experimentally using the timing machinery
from lab 1.

------------------------------------------
Part 2: 

Write a function flatten(lst) that flattens the list lst. 
For example, given the list

[[a],[],[b,c]]

it should return [a,b,c], and given the list

[[a,[b,[d,e],[a,[],c]]],[],[[e,f],[g,h]]]

it should return the list

[a,b,d,e,a,c,e,f,g,h]

To do this:

- Think what the base cases are, that is, give cases
  in which it is obvious what to return without doing any recursive calls.
  
- If you are not in the base case, the list has a first element,
  (which may or may not be a list!), and a rest of the list.
  Think what is the list that you should return in this case,
  and implement it.

You can assume that the parameter of the function is a list.
This means that you should not make any recursive call
with a parameter that is not a list!
  
You can use the python instruction isinstance(x,list)
to determine whether some object x is a list or not

Here are some ready-to-call examples for you to try:

print(flatten([]))
print(flatten([3]))
print(flatten([3,4]))
print(flatten([3,[]]))
print(flatten([[],3,[1,2,[]]]))
print(flatten([[2],3]))
print(flatten([[2,3],[4,5]]))
print(flatten([[[[2]]],3]))