The basic setup for each problem is given below. For more details,
hints, and a solution to each, click on the problem's title.


Title 
Difficulty 
Basic Setup 

Fibonacci Function

1/5 
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(n1) + Fib(n2) 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 nth 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).


Finding 2 Element Sum in Array

3/5 
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^{2}),"polynomial time"


Computing Exponentials for Integers

3/5 
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"


Swapping Variables with No Temp Variable

2/5 
CS Trivia:
How can you swap the value of two variables without using a temp variable?


Detecting Loop in Linked List

4/5 
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.

