CS 2620 Assignment #8 Summer 2004

How to handin.
Points : 45
Weight : 3%
Due : Tuesday Jun 15, 2004 @ 11:00 PM
Note : Late assignments will be accepted only with the instructor's pre-approval.

1. [2] What does it mean for a term to dominate a function? To get a feel for the answer, calculate the value of n²+1145, n²+n-5, n²-n+5 and 2n² for n = 1,10,100,1000,10000. You may want to write a small program to do this. Notice that each value of n is 10 times the previous value.

2. [16, 2 marks each] Below are some functions to do various tasks. Analyze each function to determine running time. First, determine each function's inputs and then determine a function the will count the number operations needed in terms of the function's inputs. Finally show the asymptotic running time in big-oh notation.

   1. int sum1 (int n) { return n * (n-1) / 2; }

   2. int sum2 (int n) {
      
         int total = 0;
         for (int i = 1; i <= n; i++)
            total = total + i;
         return total;
      }
      

   3. void print1(int n) {
      
         for (int i = 0; i < n; i++) {
            for ( int j = 0; j < n; j++)
      	 cout << i+j << ' ';
            cout << endl;
         }
      }
      

   4. void print2(int n) {
      
         for (int i = 0; i < n; i++) {
            for ( int j = i; j < n; j++)
      	 cout << i+j << ' ';
            cout << endl;
         }
      }
      

   5. void print3(int n) {
      
         for (int i = 0; i < n; i++) {
            for ( int j = n; j > 0; j--)
      	 cout << i+j << ' ';
            cout << endl;
         }
      }
      

   6. void print4(int n)
      
         for (int i = 0; i < n; i++) {
            for ( int j = 0; j < 10; j++)
      	 cout << i+j << ' ';
            cout << endl;
         }
      }
      

   7. void print5(int n) {
      
         for (int i = 0; i < n; i++) {
            int j = n;
            while (j > 0) {
      	 cout << i+j << ' ';
      	 j = j/2;
            }
            cout << endl;
         }
      }
      

   8. template <typename T>
      void sort1(vector<T>& vec) {
      
         int length = vec.size();
         for (int last = length-1; last > 1; last--)
            for (int currPos = 0; currPos < last; currPos++)
               if (p[currPos+1] < p[currPos]) {
                  T temp = v[currPos];
                  v[currPos]  = v[currPos+1];
                  v[currPos+1] = temp;
               }
      }
      

3. [6] Here is the code for a bubble sort.

   //******************************************************************
   // function to sort a list using a smarter bubble sort.       
   //Post-condition: elements of list are sorted in nonincreasing order
   //******************************************************************
   template <typename T>
   void bubble(vector<T> list) {
   
      int currPos;
   
      for (int last = list.size()-1; last > 1; last--)
         for (int currPos = 0; currPos < last; currPos++)
             if (list[currPos+1] < list[currPos])
                swap(list[currPos],list[currPos+1]);
   }
   
   

   Assume the list is a vector which contains the following values:

    48 23 37 5 34 17 11 41 

   Trace the bubble sort function for the call

    bubble(list);

   Show the contents of the list after each pass.

4. [7] Repeat the trace in the previous question using the shell sort code below.

   //*********************************************************************
   // function to sort a list using the shell sort. Insertion version.
   // Gap sequence used y:  ... 31, 15, 7, 3, 1
   //*********************************************************************
   template <typename T>
   void shell(vector<T> list) {
      int length = list.size();
      int gap;     // select an initial gap between elements to be compared. 
      for (gap=1; gap < length; gap *=2);  // smallest 2**k greater than length
      gap/=2;  gap--;           // largest 2**k less than length then decrement
   
      // now proceed to sort
      while (gap > 0) {
         for (int seqStart = gap; seqStart < length; seqStart++) {
            T key = list[seqStart];
            int currPos = seqStart;
            for (;;) {
               currPos -= gap;
               if (currPos < 0 || list[currPos] < key) break;
               list[currPos+gap] = list[currPos];
            }
            list[currPos+gap] = key;
         }
         gap /= 2;
      }
   }
   

   Just show the contents of the list after each pass

5. [7] Using the same list, show the initial heap and the heap tree after each pass when using the heap sort algorithm.

6. [7] Describe the quick sort. Include in your description the following :
   • the quick sort algorithm, including any helper functions
   • its time complexity (worst, average and best case)
   • its advantages and disadvantages

University of Lethbridge Home Page