Description

Introduction: Objective of this homework is for you to get familiar with and reinforce algorithm analysis techniques discussed in the class including O, Ω, and Θ notation as well as algorithm design using divide and conquer.

Requirements:

1. [15 Pts] Algorithm Analysis: Study the following sorting algorithm.

SORT (A)     // Assume there are n elements in A

• for i = 0 to n – 1
• k = i + 1
• for j = i + 2 to n
• if A[k] > A[j]
• k = j
• if k ≠ i + 1
• temp = A[i + 1]
• A[i + 1] = A[k]
• A[k] = temp

• (10 pts) Use the longer approach described in the lecture CSE360_1_L1_Part3 week 1 that we used in analyzing Insertion-Sort to compute the running time T(n) of the above SORT algorithm. You may need to define variable such as t_i or t_j, similar to the variable t_j we used in the lecture.
• (5 pts) Determine the worst case running time and the best case running time as a function of functions of n.

2.[35 Pts] Asymptotic Notation and Mathematical Induction: Use the definition of O, Ω, and Θ notation to prove that

1. (5 points) Let f(n) = 0.02n² + 20n. Show that f(n) = Θ(n²).
2. (5 points) Let f(n) = Θ(n²) and g(n) = O(n²). Show that f(n) + g(n) = Θ(n²).
3. (15 points) f(n) = 6n2 + 7n + 5 => O(n2), f(n)= 6n2  + 7n + 5 => Ω(n2) and f(n)= 6n2  + 7n + 5   => Θ(n2)
4. (10 points) Using mathematical induction to prove

^kⁿ1k2 n(n1)(₆2n1)

Algorithm Design Questions

3. 3. [10 Pts] Use recursion to solve following problem. Then determine the running time Powering of a number: For a give number X and an integer n >= 0, compute

Xⁿ

Normally, we would multiply X, n times. However that will give is O(n)  time. How do we do this calculation better using recursion (i.e, using recursion) ? Write down your algorithm and prove that its time complexity is better then O(n)

4.[15 Pts] Suppose you are given a set of cities (p number of cities) and there longitude and latitude coordinates. You need to determine the two closest cities. Write an algorithm that uses Divide and Conquer approach to determine the two closest cities. Assume that the subroutine GET_DISTANCE(s, d)  takes the longitude and latitude values of s and d and returns the distance between s and d. Using the same method you have applied in question 2 above determine the running time of your algorithm

Submission

1. a) For questions, 1-4, submit a PDF file containing your answers. Answers can be handwritten (make sure answers are readable) and scanned as PDF. Submit online to the canvas