University of Port Harcourt

PMB 5323

Port Harcourt

 School of Graduate Studies

Course Code: CSC 507.2                                              Algorithms

 Course Continuous Assessment Assignment 2

Last Submission Date:      Saturday December 15 2007

 Question 1

a.             Briefly describe how best case analysis differs from worst case. Distinguish clearly between the properties of a problem and those of a particular algorithmic solution. If possible, provide an example of best case analysis to illustrate your argument.

b.             Suppose algorithms A and B have the same asymptotic performance, T_A(n) = T_B(n) = O(g(n)). Now suppose that A does ten operations for each data item, but algorithm B only does three.

(i)                Which of the two algorithms will be faster?. Give a reason for your answer.

(ii)                Now suppose, algorithm A is

{

   set up the algorithm, taking 50 time units;

   read in n elements into array A;  /* 3 units per element */

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

      do operation1 on A[i];  /* takes 10 units */

      do operation2 on A[i];  /* takes  5 units */

      do operation3 on A[i];  /* takes 15 units */

   }

}

                                and algorithm B is

{

   set up the algorithm, taking 200 time units;

   read in n elements into array A;  /* 3 units per element */

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

      do operation1 on A[i];  /* takes 10 units */

      do operation2 on A[i];  /* takes  5 units */

   }

}

                Which algorithm sets up faster? Calculate the execution time of A and B and illustrate your result with a graph. What are the time complexities of the two algorithms?