1) Implement both the Brute Force and Improved versions of the MCS algorithms.

2) Check the correctness of the algorithms for the following sequences: a. -1, -2, -3, -4, -5, -6 MCS: See notes b. -1, 1, -1, 1, -1, 1 MCS: See notes c. -1, 2, 3, -3, 2 MCS: See notes d. 1, -5, 2, -1, 3 MCS: 2, -1, 3 e. -2, 2, -2, -2, 3, 2 MCS: 3, 2

3) Modify both algorithms to record the number of iterations used. Test your modified algorithms on the above examples.

4) Generate 10 random sequences of length 5, 10, 15, , 50 each (100 sequences in totals). Record the number of iterations for each sequence. Plot the results (x=length = n, y=iterations) to compare the algorithms time complexity. Also compare the Brute Force algorithms iterations with n(n+1)/2 and the Improved algorithms iterations with n. [Produce 3 plots: Brute vs. Improved, Brute vs. n(n+1)/2 and Improved vs. n].