Description

• to explore time complexity and “real time”
• to “dust off” programming skills
What you need to do:
1. Implement a silly (naïve and inefficient) algorithm 𝐴 to compute the sum σ𝑛𝑖=1 𝑎𝑥𝑖 where where 𝑎 and 𝑥 are a real numbers with 0 ≤ 𝑥 ≤ 1.
2. Collect the execution time T(n) of algorithm A as a function of n
3. Plot the functions 𝑇ξ(𝑛𝑛), 𝑇𝑛(𝑛2),, and 𝑛𝑙𝑛𝑇(𝑛(𝑛)) on separate graphs.
4. 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 σ𝑛𝑖=1 𝑎𝑥𝑖 where 𝑎 and 𝑥 are a real numbers (0 ≤ 𝑥 ≤ 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 𝑇(𝑛) of Algorithm A as a function of n and plot ,, and on different
𝑛𝑙𝑛(𝑛) graphs. Finally, discuss your results: use the plots you will build to determine and justify the time complexity of 𝑇(𝑛).

Algorithm A
ComputeSumPowers(x,n)
inputs: 𝑥 is a real number with 0 ≤ 𝑥 ≤ 1. 𝑎 is a real number. 𝑛 is an integer (𝑛 ≥ 0) output: a real number equal to σ𝑛𝑖=1 𝑎𝑥𝑖
sum = 0
for i = 1 to n
prod = 1 for j = 1 to i prod = prod * x sum = sum +prod
return sum

Answer These Questions
These questions are meant as hints to analyze, predict, determine, and/or justify the shape of time complexities
Insert your answers in THIS file after each question
a) Suppose that for 𝑛 very large, 𝑇(𝑛)≈𝐾ξ𝑛 where 𝐾 is a constant. 𝑇(𝑛) 𝑇(𝑛) 𝑇(𝑛)
i) (0.5 point) What would then the values of ξ𝑛 , 𝑛2 ,, and 𝑛𝑙𝑛(𝑛) be, respectively? (just replace T(n) with 𝐾ξ𝑛 and simplify the expression you get).
…. answer here

* You can use any language as long as it is already installed on Engineering Unix Tux machines.
ii) (1.5 points) Based on the expressions obtained in the previous question, what would then the shapes of the
𝑇(𝑛) 𝑇(𝑛) 𝑇(𝑛)
plots ξ𝑛 , 𝑛2 ,, and 𝑛𝑙𝑛(𝑛) be, respectively?
…. answer here
b) Suppose that for 𝑛 very large, 𝑇(𝑛)≈𝐾𝑛2 where 𝐾 is a constant. 𝑇(𝑛) 𝑇(𝑛) 𝑇(𝑛)
i) (0.5 point) What would then the values of ξ𝑛 , 𝑛2 ,, and 𝑛𝑙𝑛(𝑛)be, respectively? (just plug in T(n) and simplify the expression you get).

…. answer here ii) (1.5 points) Based on the expressions obtained in the previous question, what would then the shapes of the
𝑇(𝑛) 𝑇(𝑛) 𝑇(𝑛)
plots ξ𝑛 , 𝑛2 ,, and 𝑛𝑙𝑛(𝑛) be, respectively?
…. answer here
c) Suppose that for 𝑛 very large, 𝑇(𝑛) ≈ 𝐾𝑛𝑙𝑛(𝑛) where 𝐾 is a constant. 𝑇(𝑛) 𝑇(𝑛) 𝑇(𝑛)
i) (0.5 point) What would then the values of ξ𝑛 , 𝑛2 ,, and 𝑛𝑙𝑛(𝑛) be, respectively? (just plug in T(n) and simplify the expression you get).
…. answer here
ii) (1.5 points) Based on the expressions obtained in the previous question, what would then the shapes of
𝑇(𝑛) 𝑇(𝑛) 𝑇(𝑛)
the plots ξ𝑛 , 𝑛2 ,, and 𝑛𝑙𝑛(𝑛)be, respectively?
…. answer here
d) (4 points) Time complexity of Algorithm A:
Report on this table the time complexity you obtained for the silly algorithm in M1:Homework (Refer to your homework)
Operations Total Operations Grows as
Comparisons 𝑓𝑐(𝑛) =
Additions (line 6) 𝑓𝑎(𝑛) =
Multiplications 𝑓𝑚(𝑛) =

Program to implement (28 points)
…. answer here
State here whether your implementation worked and produced data.
Provide here the instructions to compile and execute your program on a Tux machine.

collectData()
for n = 100 to L (with step 100)// L should be as large as your machine
// and your available time allow
Start timing // Note current time start
ComputeSumPowers(0.25,n)
Stop Timing // T(n) = Current Time – start

Store the value n and the values T(n)/ξ𝑛, T(n)/n2, and T(n)/n.ln(n) in a file F where T(n) is the execution time.
// Pay attention do not use n^2. The ^ operator is often not the exponentiation. Rather, it // is the exclusive OR (XOR)

Data Analysis (42 points) 𝑇(𝑛) 𝑇(𝑛) 𝑇(𝑛)
(3*7 points per plot) Use any plotting software (e.g., Excel) to plot the values ξ𝑛 , 𝑛2 ,, and 𝑛𝑙𝑛(𝑛) in File F as a function of n (on different graphs). File F is the file produced by the program you implemented. Discuss your results based on the plots you obtain (3*7 points per plot discussion). Do not list here data as tables. Only plots are expected.
…. answer here

Improve Algorithm A
a) (12 points) Propose a more efficient algorithm to compute the sum σ𝑛𝑖=1 𝑎𝑥𝑖 such that the time complexity grows as n. Use pseudocode to describe it.
…. answer here
B) (8 points) Propose a more efficient algorithm to compute the sum σ𝑛𝑖=1 𝑎𝑥𝑖 such that the time complexity is constant (independent of 𝑛). Use pseudocode to describe it. …. answer here

ASK on Piazza for precisions if you have any doubts, concerns, or issues.
Let us know if you need help to work on Tux machines. (See at the end about how to log on Tux machines)

How to Plot?
I suggest to store the values in File F following the csv format used by Excel. Once the file F is in csv format, you can use Excel to plot.
If you do not know the csv format, google “csv format”. Do not hesitate to ask for help if you need any.

Report
• Write a report using this file to insert your answers (Do not delete anything from this original file)
• Good writing is expected.
• Recall that answers must be well written, documented, justified, and presented to get full credit.

What you need to turn in:
• Electronic copy of your source program (collectData)
• Electronic copy of the data you produce 𝑇ξ(𝑛𝑛), 𝑇𝑛(𝑛2),, and 𝑛𝑙𝑛𝑇(𝑛(𝑛))
• Electronic copy of the report (including your answers) (standalone). Submit the file as a Microsoft Word or PDF file.

Grading
• Each question shows the number of points for it

Login on Engineering Unix Machines,

Log in remotely on the Engineering Tux machines to implement, compile and execute. To log in remotely, you must use an ssh client such as SecureCRT (Windows).

On Mac or any Unix machine (Ubuntu…), use the same command (see above) on a terminal.