Implement all three methods we discussed for computing a given element F_n the Fibonacci sequence: F_0 = F_1 = 1. F_k = F_k-1 + F_k-2 for k > 1.

1. Recursive (write a recursive function to compute F_n given input n)

2. Inductive (compute F_0, …, F_n in order)

3. Formula (compute F_n directly using the formula we derived, also on pg. 323)

Compare each of these methods on a range of n values. What do you conclude? Which method is fastest, uses the least memory, easiest to implement?

Implement your own Set class in Java for storing sets of integers (note: Java has a built-in set class, but you should not use it). Your class should support the following basic set operations: union, intersection, difference. Demonstrate your class works on some example operations and discuss how efficient your implementation is.