Lab 3 Fall 2014

1. Please plot n, vs T(n), Q(n), X(n),Y(n) for the following functions, by using a C++ program to produce comma separated values and the exporting this file into a spreadsheet program to produce a plot. Always round off the arguments to integers.
   1. T(n)= T(n-1) +1, T(0)=0
   2. Q(n) = Q(n-1) + n , Q(0) =0
   3. R(n) = 2*R(n-1)+1, R(0)=0
   4. X(n) = 2*X(n/2)+1, X(0) =0
   5. Y(N) = 2*Y(n/2)+n, Y(0) =0

   
   int main(void)
   {
     int n;
   
     for (n = 10; n <=1000; n=n+10)
       cout << n<<","<< T(n) <<","<< Q(n) << "," << X(n) <<"," << Y(n)  << "\n";
      exit(1);
   }
   

2. Write the first 15 values of R and guess what function it is. (R(n) was not included in the main program above why?)
3. Solve any two of the above recurrence equations in any of the methods (using telescoping (by series summation), or guess and checking or by using Master Theorem)
4. Implement merge3sort program to split an integer array (filled with randomly chosen elements from -10000 to 10000 )into 3 parts, sort the three parts and merge them. The size of the array is given as input.
5. Implement linear time algorithm for the maximumsubarray problem and test with the input given in Benley's paper first page.{31,-41,59,26,-53,58,97,-93,-23,84} answer is 2 and 6 as the index starts from 0. (From Home work 3, read Section 4.1 of CLRS (third edition) - Wikipedia Article on Maximum subarray problem - Here is a nice write up by Bentley Dr. Bentley )