PART A. Algorithm Analysis & Design

1. (2marks)Determine the complexity of the following algorithm using Big- Oh notation. Make sure to give the tightest bound possible and provide justification.

2. (2 marks) Algorithms A and B spend exactly TA(n) = 0.1n and TB(n) = 50? microseconds, respectively, for a problem of size n. Choose the algorithm,

which is better asymptotically (i.e. the algorithm that has the better performance in the "Big Oh" sense) and determine the problem size n0 for which the "better" algorithm begins to outperform the other. Which algorithm would you use for a problem size of ONE HUNDRED THOUSAND? Show your work.

3. (2marks)An arrayA contains(n-1)unique integers in the range[1..n]- that is, there is one number from this range that is not in A. Design a O(n)- time algorithm to find that number. Make sure to specify the input and output of the algorithm. You are allowed to use only O(1) additional space besides the array A itself. (In other words, you cannot create another array of size n.)

PART B. Experimental Analysis2

1. (4marks)Write a program in C which implements the two algorithms prefixAverages1, and prefixAverages2 from Section 1.4 in the textbook (and also provided at the end of this document).

1. (4marks)Perform careful experimental analysis of their running times by doing the following:
2. For each algorithm, choose atleast 5 appropriate values for n, where n is the input array size, and determine how long it takes to run in milliseconds. For each value n, run at least five times and record each time as well as the average in a table. Please note the following:

• One good strategy is to grow the input size by repeated doubling (e.g 200000,400000,800000, etc).
• If your timings are erratic (e.g. 0s or there is no clear increase in time with respect to input size), try choosing larger values for n.
• You are not required to use the same values of n for both algorithms.

1. Plot the running times obtained in part(a)as a function of n as scatter plots on a linear scale for each algorithm.
2. (2marks)Given the experimental data obtained in#2, determine the rate of growth of time with respect to the size of the input of each algorithm and express using Big-Oh notation. Provide justification. If your experimental results are not what you expected, please provide possible reasons for the discrepancies.
3. (2marks)Run prefix Averages 1 on an input size of n=100000(one hundred thousand) and record the time. Given that time, what do you predict the execution time to be when the input size grows to 15n (i.e., 1500000)? Justify your prediction. Please note, if your execution time for the input size of 100000 is insignificant, you may start with a larger value for n.
4. (2marks)Run prefix Averages 2 on an input size of n=25000000(25 million) and record the time. Given that time, what do you predict the execution time to be when the input size grows to 15n (i.e., 375000000)? Justify your prediction. Please note, if your execution time for the input size of 25000000 is insignificant, you may start with a larger value for n.

Hints:

• To measure execution time in C in milliseconds:
• // The following header file defines clock_t datatype,
• // clock() function, as well as the constant CLOCKS_PER_SEC */ #include
• clock_t start = clock();
• /* Code you want timed here */
• double timeElapsed=((double)clock()-start)/CLOCKS_PER_SEC * 1000;
• To generate random values from 1 to 100 using pseudorandom generators available in C's library:
• srand(time(NULL)); //creates seed for generator int r = rand()%100 + 1;
• Although your input values can be integers, your output values most certainly should be floating-point values.