COT6405 Assignment 1 solution


Original Work ?


5/5 - (1 vote)

Assignment 1 (10 points for each question)

1. Exercise 2.3-1: Using Figure 2.4 as a model, illustrate the operation of merge sort on the
array A = {3, 41, 52, 26, 38, 57, 9, 49}

2. Exercise 2.3-6: Observe that the while loop of lines 5 – 7 of the INSERTION-SORT
procedure in Section 2.1 uses a linear search to scan (backward) through the sorted
subarray A[1…j-1]. Can we use a binary search instead of a linear search to improve the
overall worst-case running time of insertion sort to Θ(𝑛lg𝑛)?

3. For the MERGE function, the sizes of the L and R arrays are one element longer
than 𝑛1 and 𝑛2, respectively. Can you rewrite the merge function with the size
of L and R exactly equal to 𝑛1 and 𝑛2?
4. Prove that 𝑒
𝑛 ∈ Ο(𝑛
) (t > 0)
5. Express the function 𝑛
βˆ’ 50𝑛 βˆ’ 100𝑙𝑔𝑛 in terms of Θ notation.

6. Exercise 3.1-6 Prove that the running time of an algorithm is Θ(g(𝑛)) if and only
if its worst-case running time is O(g(n)) and best-case running time is Ξ©(𝑔(𝑛)).

7. Which is asymptotically larger: lgn or βˆšπ‘›? Please explain your reason.

8. Prove that 𝑛
𝑙𝑔𝑐 ∈ Ξ©(𝑐
𝑙𝑔𝑛), where c is a constant and c > 1.

9. Use the definition of limits at infinity to prove (𝑙𝑔π‘₯)
𝑝 ∈ π‘œ(π‘₯

Definition (limits at infinity): Let 𝑓(π‘₯) be a function defined on x > K for some K.
Then we say that, limπ‘₯β†’βˆž
𝑓(π‘₯) = 𝐿 if for every number πœ€ > 0 there is some number
M > 0 such that | 𝑓(π‘₯)– L| < πœ€ whenever x > M