Tutor profile: Joseph W.

Write a function in Python that solves returns the n-th Fibonacci number. This function should run in O(n) time. Recall that the Fibonacci sequence is given by $$1,1,2,3,5,8,\cdots$$ where each number is the sum of the previous 2 numbers. For the purposes of this problem, consider the 0-th and 1st Fibonacci number 1, the 2nd Fibonacci number is 2 etc..

The most intuitive way to solve this problem is to use recursion with a recursive case that looks something like this: $$fib(n) = fib(n-1)+fib(n-2)$$. Note, however, that this involves 2 recursive calls: fib(n-1) and fib(n-2). Also note the manner in which we solve fib(n-1): $$fib(n-1) = fib(n-2)+fib(n-3)$$. If we implement this function using recursion, we will end up computing fib(n-2)$$ twice. This is a waste of time and the problem clearly states we need to solve this problem in linear time. Instead of solving the problem recursively, we will use dynamic programing and "memo-ization" to store the small, sub-problems we have already computed. The Python code is as follows: def fib(n): f = [1,1] while n>=len(f): f.append(f[-1]+f[-2]) return f[n]

What is recursion? Give an example where you might want to use recursion.

Recursion is a programming technique where a function calls itself. More formally, recursive functions solve a main problem by solving smaller instances of that same problem and combining the results in one way. Recursion is closely related to the idea of induction from mathematics and should be considered whenever the notion of "solving smaller sub-problems" is brought up. One common program that is implemented recursively is the factorial function from mathematics: $(n! = n \cdot (n-1) \cdot (n-2) \cdots 1$) Here, instead of solving for $$n!$$ directly, we can instead solve for $$(n-1)!$$ and rely on the formula: $(n!=n\cdot(n-1)!$)

John is blowing bubbles. One bubble's radius increases at the rate of 0.5cm/second. After 2 seconds, what is the rate-of-change for the bubble's volume?

This question involves related rates, which is a very common question on calculus exams, particularly the AP. The question itself tells us that $$\frac{dr}{dt}=0.5$$. We should also remember, from geometry, that the volume of a sphere is given by $$V=\frac{4}{3}\pi r^3$$. The question is asking for the "rate-of-change" or derivative of volume: so $$\frac{dV}{dt}$$. Let us take the formula for volume and differentiate both sides: $(V=\frac{4}{3}\pi r^3$)$(\frac{dV}{dt}=\frac{4}{3}\pi\cdot 2r\cdot \frac{dr}{dt}$) We how have a formula for for $$\frac{dV}{dt}$$. We know that after 2 seconds, the radius of the bubble is $$2\cdot 0.5=1$$. This makes $$\frac{dV}{dt} = \frac{4}{3}\pi \cdot 2(1) \cdot 0.5 = \frac{4}{3}\pi$$ cubic centimeters per second.