Assignment $1$

For this assignment, you are to work in groups of $2$ or $3.$ This assignment should

provide you with experience in the analysis of algorithms.

What to include in your submission:

$$ One $.$zip folder named appropriately$1$

containing:

o A PDF containing your answers to questions #$2-$ #$9.$

o A Python file and a C file. Make sure each program$$s header $($block$)$

comment includes your name.

Complete the following:

$1.(2$ marks$)$ You are given a Python program, Assignment$1.$py$,$ which will allow

you to perform experimental analysis of two algorithms which you will need to code.

a$.$ Read the starter code to understand what it does.

b$.$ Complete the program by writing the code for the two functions

prefix$\_$averages$1,$ and prefix$\_$averages$2$ given the pseudocode

provided at the end of this document in Appendix A$.$ Run the program on

small input sizes to ensure the functions execute as expected. For example, if

n $=5,$ and your input array is $[30,43,3,5,9],$ the prefix averages computed

would be: $[30,36\mathrm{.}5,25\mathrm{.}33,20\mathrm{.}25,18].$ Please note: you are free to add any

other code to the program to help you during testing.

$2.(2$ mark$)$ Once you are sure your program works, you are now ready to perform

experimental analysis on large input sizes. Decide on an appropriate initial input

size, n$1,$ but keep in mind that the program will also execute on input sizes n$2=2$n$1,$

n$3=2$n$2,$ n$4=2$n$3,$ and n$5=2$n$4.($So if n$1$ is $1000000,$ then n$5$ would be $16000000.)$

a$.$ For each function, record the times you obtained in a table like the one shown

below: $($Note that the starter code is set up such that for each input size, the

algorithm will execute $3$ times.$)$

$1$ Check the Class Plan for Assignment submission requirements

Input Size Run #$1$ Run #$2$ Run #$3$ Average Execution Time $($sec$)$

n$1=$

n$2=$

n$3=$

n$4=$

n$5=$

Please note the following:

$$ If your timings are erratic $($e$.$g$.0$s or there is no clear increase in

time with respect to input size$),$ try starting with a larger input size.

The goal is to slow the program down enough to be able to

determine how time grows as the input size grows.

$$ You are not required to use the same initial input size for both

functions.

b$.$ Plot the average running times obtained in part $($a$)$ as a function of n as scatter

plots on a linear scale for each algorithm.

$3.(2$ marks$)$ For each function $-$ prefix$\_$averages$1$ and prefix$\_$averages$2-$ complete the

table given below to help you determine the growth of running time with respect to

the size of the input. Clearly state the experimental growth rate of the function given

your execution times: does it look more like $()($

$2$

$)?$

Input size Average

Execution

time in ms

$($as determined

by

experiment$)$

Actual Time

Increase Ratio:

Calculate

$$

$1$

Time increase

factor if O$($n$)$:

Calculate $$

$1$

Time increase

factor if O$($n$2$

$)$:

Calculate

$$

$2$

$1$

$2$

n$1=$ t$1=$ N$/$A N$/$A N$/$A

n$2=$ t$2=$

n$3=$ t$3=$

n$4=$ t$4=$

n$5=$ t$5=$

$4.(6$ marks$)$ Repeat Questions #$1-$ #$3$ above using the C file, Assignment$1.$c$,$ as

your starting point.

$5.(1$ mark$)$ Given the experimental analysis you performed for prefix$\_$averages$1$

and prefix$\_$averages$2$ using Python and C$,$ do the experimental growth rates

align with the theoretical growth rates of these $2$ algorithms? If not, please provide

possible reasons for the discrepancies.

$6.(3$ marks$)$ Al Gorythm, who is well versed in Python$$s built$-$in functions, claims the

prefix averages algorithm could be improved if one uses Python$$s built$-$in mean

function$2$

$.$ The result is prefix$\_$averages$3$ which is also given in Appendix A$.$

prefix$\_$averages$3$ produces the correct output using fewer lines than the other

two versions, yet how does this version compare to prefix$\_$averages$1$ and

prefix$\_$averages$2$ in terms of growth rate? Add code to the Python program to

include prefix$\_$averages$3.$ Perform experimental analysis for this new version

as you did for prefix$\_$averages$1$ and prefix$\_$averages$2$ and report

your findings. Explain why or why not Al$$s algorithm is the best of the three versions.

$7.(2$ marks$)$ Assume prefix$\_$averages$1$ on an input size of n $=500000($five

hundred thousand$)$ takes $3$ minutes. Given that time, what do you predict the

execution time to be when the input size grows to $13$n $($i$.$e$.,6500000)?$ Justify your

prediction.

$8.(2$ marks$)$ Assume prefix$\_$averages$2$ on an input size of n $=500000000(500$

million$)$ takes $3\mathrm{.}5$ seconds. Given that time, what do you predict the execution time to

be when the input size grows to $13$n $($i$.$e$.,6500000000)?$ Justify your prediction.