Chat with us, powered by LiveChat Assignment – Asymptotic Notations and Correctness of Algorithms Assignment: Asymptotic Notations and Correctness of Al | Economics Write
+1(978)310-4246 credencewriters@gmail.com
  

Assignment: Asymptotic Notations and Correctness of Algorithms Resources:

If want help with plotting your data on excel you can use this YouTube link.

1. Identify asymptomatic notation of a function: Use the definitions of O, Ω and Θ to identify if the following statements are true or false. Prove your assertion by solving for the values of c and no. Draw a rough graph representing the c and no values if the statement is True.

a. n(n+1)/2 ∈ O(n3)

b. n(n+1)/2 ∈ Θ(n2)

c. n(n+1)/2 ∈ Θ(n3)

d. n(n+1)/2 ∈ Ω (n)

 

2. Compare order of growth: For each of the following, indicate whether f = O(g), f = Ω (g) or f = Θ (g).

a. f(n) = 10n-6, g(n) = 12345678n + 2020

b. f(n) = n!, g(n) = 0.00001n

c. f(n) = n1.34, g(n) = log n

d. f(n) = n + n4, g(n) = n3 + log n

 

3. Identify asymptomatic notation of an operation:

If you want to search for a value ‘x’ in the following data structures and return True if the value is present otherwise return False. What would be the time complexity for this operation? Assume that the values are sorted. (Use an appropriate notation among O, Ω and Θ to mention the time complexity). Provide an explanation for your answer.

a. Array

b. Linked List

 

4. Read and Analyse Pseudocode: Consider the following algorithm

Classified(A…n-1):

minval = A[0]

maxval = A[0]

for i = 1 to n-1:

if A[i] < minval:

minval = A[i]

if A[i] > maxval

maxval = A[i]

return maxval – minval

a. What does this algorithm compute?

b. What is its basic operation (i.e. the line of code or operation that is executed maximum number of times)?

c. How many times is the basic operation executed?

d. What is the time complexity of this algorithm?

 

5. Using mathematical induction prove below non-recursive algorithm: Any number greater than 8 can written in terms of three or five.

a. Write a pseudocode of algorithm that that takes a number greater than 8 and returns a tuple (x,y); where x represents number of threes and y represent number of fives make that number If number = 8 your pseudocode should return (1,1) https://youtu.be/u7V1LPVlHck

b. Prove correctness of your pseudocode using induction

c. What is the time complexity of your pseudocode?

d. Code your pseudocode into python and name your file ThreeAndFive.py

 

6. Visualizing time complexity for best case, worst case and average case:

a. Implement insertion sort to sort an array of numbers in descending order. Name your function insertionsort and your file EvaluateInsertionSort.py.

b. Modify your code to add another function timeSortingRandomNumbers() that creates arrays of different sizes ranging from 0 to 10,000 with random unsorted numbers and collects the time that insertionsort function takes to sort the arrays.

Collect at least 10 running times.

c. Modify your code to add another function timeSortingAscendingNumbers() that creates arrays of different sizes ranging from 0 to 10,000 with numbers sorted in ascending order and collects the time that insertionsort function takes to sort the arrays. Collect at least 10 running times.

d. Modify your code to add another function timeSortingDescendingNumbers() that creates arrays of different sizes ranging from 0 to 10,000 with numbers sorted in descending order and collects the time that insertionsort function takes to sort the arrays. Collect at least 10 running times.

e. Plot the running time obtained 6.b, 6.c, 6.d using excel. On y axis: running time and on X axis: array sizes

f. What is your observation about the insertion sort algorithm on random array, array with numbers in ascending order and array with numbers in descending order?

 

Debriefing (required!): ————————–

Report:

1. Approximately how many hours did you spend on this assignment?

2. Would you rate it as easy, moderate, or difficult?

3. How deeply do you feel you understand the material it covers (0%–100%)?

4. Any other comments?

  
error: Content is protected !!