Objective: The purpose of this lab assignment is to test different complexity classes of algorithms and measure the execution time effect in practice. Submit your report according to the template given making sure that questions are answered and discussions are provided for each of the Tasks. Assume that System.out.println is only 1 instruction. Task 1 (complexity of Average of numbers from 1 to n algorithms): 20% Two different algorithms can be used to calculate the sum and average of integers from 1 to n : Algorithm1: is a simple for loop that adds the successive integer values from 1 to n and then finds the average. Algorithm2: calculates the sum by using the following formula: sum= (n/2)(n+1) (use this equation without any simplification and then finds the average. Determine the order of magnitude (Big-O) of each algorithm and discuss which one is the most efficient. Write the 2 algorithms in Java and measure the execution time (use System.nanoTime() which returns a long time in nanosecs (107) before and after the code that you want to measure) it takes each one and compare them with the complexity for value of n=1000,000. Also use type long for the variable sum in order not to have overflow. Does the results of the execution time correspond to the complexities (calculate time complexity of your code)? Discuss. Sample output: Sum of numbers from 1 to 1000000 (loop) =500000500000 Average of numbers from 1 to 1000000 (loop) =500000.5 Sum of numbers from 1 to 1000000 (equation) =500000500000 Average of numbers from 1 to 1000000 (equation) =500000.5 Execution time in nanoseconds loop: 23474900 Execution time in nanoseconds equation: 573700 Task 2 (Fibonacci series complexity: iterative vs recursive): 45% Write two Java programs, one recursive and another iterative (will be explained in class but also attached at the end of this lab script), that solve the Fibonacci series problem by printing all the Fibonacci numbers from 0 to n. Your programs MUST print a Fibonacci(counter) in front each number like in the sample output below. Analyze the complexity of the recursive and iterative algorithms by hand and work out the complexity equations T(n) and the Big Oh notation for each. Record the times taken for various Fibonacci numbers (10, 20, 30, 40, and 50) (use long Fibonacci(int n ) to avoid getting incorrect results) and compare with the results with the corresponding complexities. Report any anomalies if any. For any run if you think that the program will not finish during the lab just stop it and note that in your submission. Also run the Fibonacci iterative for n=92 and note the execution time. Sample output: Enter the Fibonacci number: 50 Fibonacci (0)=0 Fibonacci (1)=1 Fibonacci (2)=1 Fibonacci (50)=12586269025 Execution time Fibonacci recursive (secs): 128.8520772// (example here is only for recursive for n=50 ) Task 3 (Tower of Hanoil: 35% Write a recursive Java function of the Tower of Hanoi problem and use it in a program to give the steps required to do any number of dises (input given by the user). Report the number of dises that you can reach within 2 minutes of time by experimenting with the code (should be around 20. Show the details of calculation of the complexity of your algorithm with the resulting T(n) and give the complexity in Big-Oh notation. What is your expectation in time (in years assuming 365 days in a year) for a65 - (your least significant digit of id) dises given that one move costs only 1 nanosecond (=10), show your calculations. The output of the program should be similar to the sample outpot below. Assume that the Systemout.peiatln statement is only I instruction ignoring whatever is inside it. Sample output: Enier the number of dises: 2 1 Move a dise from pog A to peg B 2 Move a dise from peg A to peg C. 3 Move a dise trom Peg B to pes C. Execution time Hanoi 20 dises (secs) 119.65652733 fecurngle bere is for 20 dives is secs - report a for time 120 secs ae yeur computer Note that submissions. of the 3 tasks in one wond file should be done during lab time. Any delay will incar 10 t penalry. lnclade the code, the complexify analysis cxecution. times obtained and discession as requined. Sutonissions without discussions will he heavily pstalized. Fibonacci Recursive without main method that vou need to write to calli: public static long Fibonacci(int n) f if(n-2) retum n; else return Fibonacci(n-1)+Fibonacci(n-2)t 1 Fibonacei Iterative without main methed that vee nend to write to calle public static long Fibonacci(int n) \& long fnm2 =0, fnm 1=1,fn=0; if (n