Section 101 due before class 10/1/98
Section 201 due before class 10/5/98

1. From the Ford/Topp textbook -- Chapter 7.
   Written exercise 7.2 on page 309 (given below)(10 points)
   
   Write a template class DataStore that has the following methods.
   
   int Insert (T elt);
   Inserts 'elt' into a private array named 'dataElements' containing (a maximum of 5) elements of type T.
   The index of the next available location in dataElements is given by the data member 'loc',
   which is also the number of data values in dataElements.
   Return 0 if there is no more room left in dataElements.
   
   int Find (T elt);
   Search for the element 'elt' in dataElements and returns its index if found and -1 if not found.
   
   int NumElts (void);
   Return the number of elements stored in dataElements.
   
   T& GetData (int n);
   Return the element at location 'n' in dataElements.
   Generate and error message and exit if n < 0 or n > 4.
   
2. From the Ford/Topp textbook -- Chapter 7.
   Programming exercise 7.2 --- DO NOT WRITE THE TEST PROGRAM.
   Write only the template function Copy as describe below.(5 points)
   
   

   Write the template function Copy with the declaration
           template <class T>
           void Copy (T A[], T B[], int n);
   

   
   This function copies n elements from array B to array A.
   (Assume that A can hold at least n elements)
   
3. Given the following template class definition
   template <class T> myArray { …. class stuff here …. };
   
   (5 points)
   write declaration statements that would appear in your main program to
   a. instantiate an instance of myArray named A of 100 ints
   b. instantiate an instance of myArray named B of 200 chars
   
4. In the function template definition below, for a user defined class X,
   state exactly which operators and/or member functions of X will be referred to (and therefore need to be defined and written as part of X).
   (5 points)
   

   template <class T>
   const T f (const T& a, const T& b)
   {
       T   d = a;
   
       d  = b + b;
       if ( a > d)
           return d;
       else if (a == d)
           return b;
       else
           return a;
    }
   

5. For each of the following program fragments, give a Big-Oh analysis of the running times (in terms of N).
   (10 points)
   

   a. for (int i = 0, sum = 0; i < N; i++)
           sum++;
   
   b. for (int i = 0, sum = 0; i < N * N * N; i++)
           sum++;
   
   c.
       for (int i = 0, sum = 0; i < N; i++)
           sum++;
   
      for (i = o, sum = 0; i < N; i++)
           for (int j = 0; j < N; j++)
               sum++;
   

6. Given an array that contains N numbers, determine if there are two numbers whose sum equals a given number K. For example, if the arrary is 8, 4, 1, 6 and K is 10, the answer is yes because 4 + 6 = 10. (Note that the same number may be used twice).(10 points)
   (Hint: Many sort algorithms can sort N elements in O(N * lgN) time
   a. give an O(N²) algorithm to solve this problem.
   b. give an O(N * lgN) algorithm to solve this problem.