Computer-Engineering Homework 2-Solution

Description

Part 1:

Analyze the time complexity (in most appropriate asymptotic notation) of the following procedures by your solutions for the Homework 1:

9. Searching a product.

II. Add/remove product.

III. Querying the products that need to be supplied.

Attach the code of your solution for each part just before its analysis.

Part 2:

1. Explain why it is meaningless to say: “The running time of algorithm A is at least O(n²)”.

2. Let f(n) and g(n) be non-decreasing and non-negative functions. Prove or disprove that: max(f (n), g(n)) = Θ(f(n) + g(n)).

3. Are the following true? Prove your answer.

I. 2ⁿ⁺¹ = Θ(2ⁿ)

II. 2²ⁿ = Θ(2ⁿ)

III. Let f(n)=O(n²) and g(n)= Θ(n²). Prove or disprove that: f(n) * g(n) = Θ(n⁴).

Part 3:

List the following functions according to their order of growth by explaining your assertions.

n^1.01, nlog²n, 2ⁿ, √n, (log n)³, n2ⁿ, 3ⁿ, 2ⁿ⁺¹, 5 ^log2 ⁿ, logn

Part 4:

Give the pseudo-code for each of the following operations for an array list that has n elements and analyze the time complexity:

• Find the minimum-valued item.

• Find the median item. Consider each element one by one and check whether it is the median.

• Find two elements whose sum is equal to a given value

• Assume there are two ordered array list of n elements. Merge these two lists to get a single list in increasing order.

Part 5:

Analyze the time complexity and space complexity of the following code segments:

a)

int p_1 (int array[]):

{

return array[0] * array[2])

}

b)

int p_2 (int array[], int n):

{

Int sum = 0

for (int i = 0; i < n; i=i+5)

sum += array[i] * array[i])

return sum

}

c)

void p_3 (int array[], int n):

{

for (int i = 0; i < n; i++)

for (int j = 0; j < i; j=j*2)

printf(“%d”, array[i] * array[j])

}

d)

void p_4 (int array[], int n):

{

If (p_2(array, n)) > 1000)

p_3(array, n)

else

printf(“%d”, p_1(array) * p_2(array, n))

}

RESTRICTIONS:

• Answer in detail the questions by using asymptotic notations.

• Yes / no answers and plagiarisation from the web will not be accepted.

GENERAL RULES:

• For any question firstly use course news forum in Moodle, and then the contact TA.

• You can submit assignment one day late and will be evaluated over sixty percent (%60).

REPORT RULES:

• All the analysis must be stated in the report/answer sheet in details.

• The report may be handwritten (only for this homework) if you want but, it must be scanned well and submitted to Moodle.

GRADING :

–	Part 1:	20 pts
–	Part 2:	10 pts
–	Part 3:	25 pts
–	Part 4:	30 pts
–	Part 5:	15 pts

• Disobey restrictions: -100

– Cheating:

-200

• Your assignment is evaluated over 100 as your performance.

CONTACT :

• Teaching Assistant : Mehmet Burak Koca

• b.koca@gtu.edu.tr