Instructions: Complete the following Proof of Correctness exercises and submit your answers.

Question 1: Given the following recursive algorithm for determining the Fibonacci numbers for any given value of n: int fibo(int n) { if(n < = 1) return n; else return fibo(n-1) + fibo(n-2); }

Question 2: Include its pre-conditions and post-conditions. Finally, prove by induction that the recursive algorithm is correct Given the following iterative algorithm which computes the nth triangular number: int tri(int n) { int result = 0; for (int i = 1; i = n; i ++) result += i; return result; } Convert this function to use recursion. Include its pre-conditions and post-conditions. Finally, prove by induction that the recursive algorithm is correct

Question 3: If the number of steps required in the worst case for two algorithms are: Algorithm 1: f(n) = 4n2+ 6 Algorithm 2: g(n) = 78n+ 25 Calculate the point at which algorithm 2 becomes more efficient than algorithm 1. Question 4: Given the following algorithm for determining the factorial of a given number n: factorial(n) if (n == 0) return 1 return n * (factorial - 1) Find the initial condition and recurrence equation that expresses the execution time for this algorithm