Objectives of this assignment:

to explore time complexity and $$real time$$

to $$dust off$$ programming skills

Use This File

USE THIS FILE AS THE STARTING DOCUMENT YOU WILL TURN IN$.$ DO NOT DELETE ANYTHING FROM THIS FILE: JUST INSERT EACH ANSWER RIGHT AFTER ITS QUESTION$/$PROMPT$.$

IF USING HAND WRITING $($STRONGLY DISCOURAGED$),$ USE THIS FILE BY CREATING SUFFICIENT SPACE AND WRITE IN YOUR ANSWERS.

FAILING TO FOLLOW TURN IN DIRECTIONS $/$GUIDELINES WILL COST A $30\%$ PENALTY.

What you need to do:

Implement a simple algorithm A to compute the sum $\_($i$=0)^$n$$ax$^$i where where a and x are a real numbers with $0<=$x$<=1.$

Collect the execution time T$($n$)$ of algorithm A as a function of n

Plot the functions $($T$($n$))/($g$\_1($n$)),$ T$($n$)/($g$\_2($n$)),$ and $($T$($n$))/($g$\_3($n$))$ on separate graphs. $($See below what the functions g$\_1($n$),$ g$\_2($n$),$

and g$\_3($n$)$ are.$)$

Refer to the analysis of the time complexity your performed for your Module $1$ and discuss it in light of the plots you plotted above.

Objective:

The objective of this programming assignment is to implement in your preferred$*$ language an algorithm A to compute the sum $\_($i$=0)^$n$$ax$^$i where a and x are a real numbers $(0<=$x$<=1).$ We are interested in exploring the relationship between the time complexity and the $$real time$($wall time$).$ For this exploration, you will collect the execution time T$($n$)$ of Algorithm A as a function of n and plot $($T$($n$))/($g$\_1($n$)),$ T$($n$)/($g$\_2($n$)),$ and $($T$($n$))/($g$\_3($n$))$ on different graphs. Finally, discuss your results: use the plots you will build to determine and justify the time complexity of T$($n$).($Hint: analyze ahead the time complexity T$($n$)$ of ComputeSumPowers to predict the expected shapes of $($T$($n$))/($g$\_1($n$)),$ T$($n$)/($g$\_2($n$)),$ and $($T$($n$))/($g$\_3($n$)))$

Algorithm A

ComputeSumPowers$($a$,$x$,$n$)$

inputs: x is a real number with $0<=$x$<=1.$ a is a real number. n is an integer $($n $>=0)$

output: a real number equal to $\_($i$=1)^$n$$ax$^$i

sum $=0$

prod $=$ x

for i $=1$ to n

sum $=$ sum $+$ prod

prod $=$ prod $*$ x

return a$*$sum$$

Questions

IMPORTANT: The following questions are meant as hints to guide you to analyze, predict, determine, and$/$or justify the shape of time complexities T$($n$).$ If you are given the plot T$($n$)$ and asked to determine whether T$($n$)$ grows like n$,$ n$^3,$ nln$($n$),$n$,$n ln$($n$).......,$ or n$^2,$ your task will in general be hard if you just plot T$($n$).$ The shape of the curve T$($n$)$ may be misleading as the scales on the x and y vary. A strategy to help determine the asymptotic growth is the following: if we suspect that T$($n$)$ grows like a function g$($n$),$ then plotting $($T$($n$))/($g$($n$))$ will help you. Indeed, if T$($n$)$ grows like a function g$($n$),$ the curve of $($T$($n$))/($g$($n$))$ will be look like an unmistakable horizontal line for large values of n$.$

The following questions should help you understand why plotting $($T$($n$))/($g$($n$))$ is helpful and how to decide whether T$($n$)$ grows like g$($n$).$

For this assignment, we will suspect that T$($n$)$ grows as the functions g$\_1($n$),$ g$\_2($n$),$

or g$\_3($n$)$:

g$\_1($n$)=$n

g$\_2($n$)=$n$^2$

g$\_2($n$)=$n

Insert your answers in THIS file after each question

a$)$ Suppose that for n very large, T$($n$)$Kg$\_1($n$)$ where K is a constant.

i$)(1$ point$)$ What would then the values of $($T$($n$))/($g$\_1($n$)),$ T$($n$)/($g$\_2($n$)),$ and $($T$($n$))/($g$\_3($n$))$ be$,$ respectively? $($just replace T$($n$)$ with Kg$\_1($n$)$

and simplify the expression you get$).$

$....$ answer here

ii$)(3$ points$)$ Based on the expressions obtained in the previous question, what would then the shapes of the plots $($T$($n$))/($g$\_1($n$)),$ T$($n$)/($g$\_2($n$)),$ and $($T$($n$))/($g$\_3($n$))$ be$,$ respectively?

$....$ answer here

b$)$ Suppose that for n very large, T$($n$)$Kg$\_2($n$)$ where K is a constant.

i$)(1$ point$)$ What would then the values of $($T$($n$))/($g$\_1($n$)),$ T$($n$)/($g$\_2($n$)),$ and $($T$($n$))/($g$\_3($n$))$ be$,$ respectively? $($just plug in T$($n$)$

and simplify the expression you get$).$

$....$ answer here

ii$)(3$ points$)$ Based on the expressions obtained in the previous question, what would then the shapes of the plots $($T$($n$))/($g$\_1($n$)),$ T$($n$)/($g$\_2($n$)),$ and $($T$($n$))/($g$\_3($n$))$ be$,$ respectively?

$....$ answer here

c$)$ Suppose that for n very large, T$($n$)$Kg$\_3($n$)$ where K is a constant.

i$)(1$ point$)$ What would then the values of $($T$($n$))/($g$\_1($n$)),$ T$($n$)/($g$\_2($n$)),$ and $($T$($n$))/($g$\_3($n$))$ be$,$ respectively? $($just plug in T$($n$)$

and simplify the expression you get$).$

$....$ answer here

ii$)(3$ points$)$ Based on the expressions obtained in the previous question, what would then the shapes of the $($T$($n$))/($g$\_1($n$)),$ T$($n$)/($g$\_2($n$)),$ and $($T$($n$))/($g$\_3($n$))$ be$,$ respectively?

$....$ answer here$$

Program to implement $(28$ points$)$

$....$ answer here

Actions to complete:

$1)$ ssh into a Tux machine

$2)$ clear the screen on the Tux machine $($use the command clear$)$

$3)$ Display the current date $($use the command date$)$

$4)$ Compile your program

$5)$ Execute your program and interrupt it just to show how the execution starts

$6)$ Take a screenshot of the Tux terminal and insert here $($below$).$ Your screenshot should look like this template screenshot