\$30.00

Category:

Description

Completing the assignment in Latex will earn you extra credit on Midterm 1.

1. Sorting (10 points)

Consider the sorting algorithm below which sorts the array A[1 : : : n] into increasing order by repeatedly bubbling the minimum element of the remaining array to the left.

Algorithm 1 mysterysort(int A[1 : : : n])

i = 1 // C1 | 1

while i <= n do // C2 | n + 1

//(I) The elements in A[1 : : : (i 1)] of the array are in sorted order and

are all smaller than the elements in A[i : : : n]

k = n; // C3 | n

// tk = # of times while loop executes

n

while (k >= i + 1) do // C4 | P(tk + 1)

1

//Inner while loop moves the smallest element in A[i : : : n] to A[i]

n

if A[k 1] > A[k] then // C5 | Ptk

1

n

swap A[k] with A[k 1] // C6 | Worst Case: Ptk Best Case: 0

1

end if

n

k ; // C7 | Ptk

1

end while

i + +; // C8 | n

end while

1. (2 points) Consider running the above sort on the array [5; 3; 1; 4; 2]. Show the sequence of changes which the algorithm makes to the array.

 5 3 1 4 2 ! 1 5 3 2 4 ! 1 2 5 3 4 ! 1 2 3 5 4 ! 1 2 3 4 5
1. (4 points) Use induction to prove the loop invariant (I) is true and then use this to prove the correctness of the algorithm. Speci cally complete the following:

1. Base case

• i = 1 ) No elements in A[1 : : : i 1], so loop invariant trivially holds true

1. Inductive step

(Hint: you can assume that the inner loop moves the smallest ele-

ment in A[i : : : n] to A[i])

• iold = value before iteration

• A[1 : : : iold 1] are sorted and smaller than A[iold : : : n]

• Inner loop moves the smallest element in A[iold : : : n] to A[iold] )

A[1 : : : iold] are now in sorted order and smaller than A[iold +

1 : : : n]

• Since inew = iold + 1, A[1 : : : inew 1] are sorted and smaller than

A[inew : : : n], thus maintaining the loop invariant after iteration

1. Termination step

• Terminates when i > n, i.e. i = n + 1

• Loop invariant says A[1 : : : i 1] are sorted and smaller than

A[i : : : n]

• i = n + 1 ) A[1 : : : n] are sorted and smaller than A[n + 1 : : : n], i.e. the entire array is now sorted and the algorithm terminates correctly producing a sorted array

1. (2 points) Give the best-case and worst-case runtimes of this sort in asymptotic (i.e., O) notation.

Worst Case:

• Array is in reverse order ) C1 + (C3 + C8)n + C2(n + 1) + (C5 + C6 +

n n

C7) Ptk + C4 P(tk + 1)

1 1

n n

• C4 P(tk + 1) = C4n + C4 Ptk

1 1

n

! tk = n k ) P(n k) = n 1 + n 2 + ::: + 2 + 1 n(n2 1)

1

Best Case:

• Array is in sorted order ) C1 + (C3 + C8)n + C2(n + 1)

n n n

C7) Ptk + C4 P(tk + 1) + C6 P0

1 1 1

• O(n2)

• (C5 +

• Only C6 is not executed, so the runtime is the same as worst case ) f(n) 2 O(n2)

1. Asymptotic Notation (8 points)

Show the following using the de nitions of O, , and .

1. (2 points) 2n3 + n2 + 4 2 (n3) f(n) 2 O(n3):

• 2n3 + n2 + 4 2n3 + n3 + 4n3 = 7n3

• 7n3 Cn3 for C = 7 and n n0 = 1 > 0 ) f(n) 2 O(n3) f(n) 2 (n3):

• 2n3 + n2 + 4 n3 + 0 + 0 = n3

• n3 Cn3 for C = 1 and n n0 = 1 > 0 ) f(n) 2 (n3) Since f(n) 2 O(n3) and f(n) 2 (n3) ) f(n) 2 (n3)

1. (2 points) 3n4 9n2 + 4n 2 (n4)

(Hint: careful with the negative number) f(n) 2 O(n4):

• 3n4 9n2 + 4n 3n4 0 + 4n(n3) = 3n4 + 4n4 = 7n4

• 7n4 for C = 7 and n0 = 1 ) f(n) 2 O(n4)

f(n) 2 (n4):

• 3n4 3 3n2 + 4n 3n4 n n n2 + 0 = 3n4 n4 = 2n4

 ! n4 C = 24 n 0 = 3 ) f(n) 2 (n4) 4 2 for and 4 ) Since f(n) 2 O(n ) and f(n) 2 (n ) ) f(n) 2 (n
1. (4 points) Suppose f(n) 2 O(g1(n)) and f(n) 2 O(g2(n)). Which of the following are true? Justify your answers using the de nition of O. Give a counter example if it is false.

1. f(n) 2 O( 5 g1(n) + 100 )

• f(n) 2 O(g1(n)) ) f(n) C g1(n) for C = k1 and n0 = k2

! 5 k1 g1(n) 5 k1 g1(n) + 100 ! By de nition f(n) 2 O(5g1(n) + 100) for C = k1 and n0 = k2

(b) f(n) 2 O( g1(n) + g2(n) )

! f(n) 2 O(g1(n)) ) f(n) C1 g1(n) for C1 = k1 and n0 = k2 ! f(n) 2 O(g2(n)) ) f(n) C2 g2(n) for C2 = m1 and n0 = m2 ! f(n) k1 g1(n) + m1 g2(n) k1 m1(g1(n) + g2(n))

! By de nition f(n) 2 O(g1(n) + g2(n)) for C = k1 m1 and n0 = max(k2; m2)

g2(n)

• False, Counterexample: f(n) = n, g1(n) = n, g2(n) = n2

• f(n) 2 O(n), f(n) 2 O(n2), f(n) 2= O(nn2 ) ) f(n) 2= O(n 1)

1. f(n) 2 O( max(g1(n); g2(n)) )

• Trivially true, since f(n) C1 g1(n) and f(n) C2 g2(n)

• Clearly, f(n) will be less than or equal to the larger of the two functions.

• Thus, f(n) 2 O(max(g1(n); g2(n)))

1. Summations (4 points) Find the order of growth of the following sums.

 n n n iP (1) (4i + 1): =5
• 4 P i + P 1

i=5 i=5

n 4

) 4( P i P i) + (n 4) = 4(n(n2+1) 10) + (n 4)

i=1 i=1

) 2n2 + 3n 44 ) sum is O(n2)

log2(n)

(2) P 2i (for simplicity you can assume n is a power of 2)

i=0

) From formula sum = 1 2log2(n)+1

1 2

) 1 2log2(n) 2 = 1 2n = 2n 1 ) sum is O(n)

1 1