The Fibonacci sequence is a somewhat fundamental mathematical/natural sequence whose core property is that every Fibonacci number is equal to the sum of the previous two numbers.

More formally,

Fib(n) = Fib(n-1) + Fib(n-2) and

Fib(0) = Fib(1) = 1.

This results in a sequence like 1, 1, 2, 3, 5, 8, 13, 21...

Write a function which takes one parameter, an integer "n" that returns the n-th number in the Fibonacci sequence.

Depending on how you think, you either wrote the above function using a "recursive function" or an "iterative" approach (using a loop).

Write the Fibonacci function again using a recursive/iterative approach (whichever you didn't use last time). Analyze which approach is better/faster. Particularly, what is the "time complexity" of the two approaches (big O notation).

Write a function which takes two parameters, an integer array named "arr" and a single integer named "target."

This function should return a boolean (true/false) which indicates whether any two elements in the array, when added together, equals the target value.

If you passed CS 101, that should have been a cake walk. So let's make it interesting now and see if you also passed CS 103...

Write the same function, but this time, use an algorithm that takes O(n), "linear time" instead of O(n²),"polynomial time"

Write a function which takes two parameters, an integer "x" and an integer "y"

This function should return the value of x^y, without the use of any library functions, only basic operators.

Again, this is easy to do, so we amp up the difficulty when we...

Write the same function, but this time, use an algorithm that takes O(log(y)), "logarithmic time" instead of O(y),"linear time"

CS Trivia:

How can you swap the value of two variables without using a temp variable?

Given a pointer/reference to a Linked List, describe and/or write an algorithm than can determine if there is a loop in the Linked List.

Determine if there is a loop in the Linked List, but the algorithm must use O(1) "constant" space.