Software Design Assignment 4

CS313E - Software Design
Assignment 4 - 100 Points
Please submit to the Gradescope!
Note: You can create a single PDF file with multiple pages and submit it to the Gradescope.
You can use using any software like MS-Word or LaTeX to include mathematic formulas if needed.
If you can not create a PDF you can write on a piece of paper, scan it or make a picture of it using
your smartphone and submit multiple images into Gradescope.
You can use this guide to see how you can submit your assignment.
https://gradescope-static-assets.s3.amazonaws.com/help/submitting_hw_guide.pdf
You can use this video tutorial to know how to submit your grade to Gradescope
https://www.youtube.com/watch?v=u-pK4GzpId0.
Tasks
1. Use python to create 3 different plots of the following functions (15 points):
f1(n) = (2
10)(n) + 2
10
f2(n) = n
(3.5) − 1000
f3(n) = 100n
(2.1) + 50
• Create 3 plots and limit the horizontal x-axis to n = 5, 15, 50. On each of the 3 plots you
need to show the above 3 functions. On the first plot the x-axis is limited to 5, on second
one x-axis is limited to 15 and on the 3rd one x-axis is limited to 50.
• Visualize the 3 functions in 3 colors (f1 in red, f2 in blue, f3 in green).
• Describe your visualization and what you see in these 3 plots.
• Add your visualization and your python code to your PDF report file.
You can use the template implementation provided in class.
2. Asymptotic Notation. (15 points)
• Is 2(n+1.3) = O(2
n) ?
• Is 3(2×n) = O(3
n)?
Describe your answer.
Page 1 of 2
3. For each pair of functions f (n) and g(n), check if f (n) = O(g(n)) ?
Functions f (n) and g(n) are:
1. f (n) = (4 × n)
150 + (2 × n + 1024)
400 vs. g(n) = 20 × n
400 + (n + 1024)
200
2. f (n) = n
1.4 × 4
n vs. g(n) = n
200 × 3.99n
3. f (n) = 2
log(n) vs. g(n) = n
1024
Describe your justifications. (30 points)
4. Analyze the Algorithm 1 and give a Big O bound on the running time as a function of n.
Carefully describe your justifications. (20 points)
Algorithm 1 What is the Big O of this pseudocode?
1: i = 1
2: while i ≤ n do
3: A[i] = i
4: i = i + 1
5: end while
6: for j ← 1 to n do
7: i = j
8: while i ≤ n do
9: A[i] = i
10: i = i + j
11: end while
12: end for
5. Analyze the Algorithm 2. What is the Big O on the running time as a function of n.
Carefully describe your justifications. (20 points)
Algorithm 2 What is the Big O of this pseudocode?
1: x = 0
2: for i ← 0 to n do
3: for j ← 0 to (i × n) do
4: x = x + 10
5: end for
6: end for
Page 2 of 2