University of Port Harcourt

PMB 5323

Port Harcourt

 School of Graduate Studies

Course Code: CSC 507.2                                              Algorithms

 Course Continuous Assessment Assignment 1

Last Submission Date:      Saturday December 15 2007

 Question 1

Question 1

a.             Give a mathematical definition of the order notation

f(n) Î O(g(n))

and explain how this concept relates to the algorithmic idea of worst case analysis.               

b.             Are the following statements true or false?

(a)            If f (n) = O(g(n)), and both f (n) and g(n) are ³ 2, then lg ( f (n)) = O( lg (g(n)) ).

(b)                If f (n) = O(g(n)), and both f(n) and g(n) are ³ 2, then 2^f(n)  = O(2^g(n)).

(c)                Q(n²) × O(n³ lg n) = O(n⁶/lg n).

(d)            (n)^{lg n}+ (lg n)ⁿ + 2 ^{n lg n} = Q(nⁿ).

(e)                The solution to the recurrence T(n) = T(n/5) + T(4n/5) + n is T(n) = Q(n lg n).

(f)                Worst case time complexity of QuickSort is Q(n lg n).

(g)           To find the closest pair among n points on the 2 dimensional plane requires at least W(n²) time in the worst case.

In each case give a careful argument based on the mathematical definition of O-notation.               

Question 2

a.             Define the following terms as it applies to the study of algorithms:

(i)                  Algorithms, Brute Force, Complexity, Asymptotic analysis, Polynomial time               

b.             Discuss the three major steps in designing an efficient algorithm