First, you are responsible for all material covered in chapters
1,2,3,4,5,6,7,8,9, and 10 in Horstmann's text.  There are excellent review
questions at the end of each chapter.  You are also responsible for
chapters 1,2 and appendix B (big-O notation) in the Main and Savitch text.

Here are some sample questions that are similar in flavor to those that
will appear on the mid-term.  Most of these were taken from previous CS113
course WWW pages by Drue Coles and Peter Gacs.

TOPIC: ARITHMETIC OPERATIONS AND CASTING

What is the output?

     int x=3, y=5, z=11;
     
     cout << y / x - y / z << endl;
     cout << static_cast < float >(y / x) << endl;
     cout << static_cast < float >(y) / x << endl;
     cout << y % z + z % y;

     int k = 2.25 + 2.5*3;
     cout << k << endl;

TOPIC: LOOPS.

The first code fragment writes a certain number of stars.  What must the
value of x be in the second fragment so that the same number of stars is
written?

     for (int i=0; i<3; i++)
       for (int j=14; j>11; j--)
         cout << '*';


     int i=5;
     while (i > x) {
       cout << '*';
       --i;
     }



TOPIC: PREFIX VS. POSTFIX FORM OF THE INCREMENT/DECREMENT OPERATORS.

        What is the output?

        int w=3, x=5, y, z;
        y = ++w;
        z = x++;
        cout << w << x << y << z;
        cout << --w << x-- << ++y << z++;
        cout << w << x << y << z;



TOPIC: FUNCTION PROTOTYPES

Assume the following function prototypes:

   void fct1(int i);
   int fct2(int i);
   void fct3( );
   int fct4( );
   double fct5(int i, int j, int k);

Which of the following is/are legal function invocations?

   i. int y = fct4;
  ii. fct1(int 7);
 iii. int x = fct2( );
  iv. cout << fct5( fct4( ), 2, 3);
   v. cout << fct5(3, 4, fct1(5));


Topic: Pass-by-Value vs. Pass-by-Reference

Assume the following function definition:

   void f(int x, int& y)
   {
     int w = 22;
     x += y;
     y = w + x;
   }

What is the output?

   int x=13, y=14, w=37;
   f(y, x);
   cout << x << y << w << endl;
        
What is the output?

   int x=13, y=14, w=37;
   f(w, w);
   cout << x << y << w << endl;

TOPIC: STATIC VARIABLES

What is the output?

     int f(int);
     
     int main( )
     {
       cout << f(3) << endl;
       int k = f(4);
       cout << k + f(1) << endl;
       return 0;
     }

     int f(int n)
     {
       int x=5;
       static int y = 5;
       x *= n;
       y *= n;
       return x+y;
     }


TOPIC: RECURSION

What is returned by f(100)?

  int f(int n)
  {
    if (n==0)
      return 0;
    if (n % 2 == 0)
      return f(n/2);
    else return 1 + f(n/2);

  }

Describe what happens as a result of the call Print(5).

  void print(int n)
  {
    int x;
    if (n > 0) {
      cin >> x;
      if (x > 0) {
        print(n-1);
        cout << x << endl;
      }
      else print(n);
    }
  }


Ackermann's function is defined as follows:

  Ack(0,n) = n+1
  Ack(m,0) = Ack(m-1,1)

And if m and n are both positive, then--

  Ack(m,n) = Ack(m-1, Ack(m, n-1))

What is Ack(1,3)?

TOPIC: CHARACTERS AND STRINGS

What is the output?

int main()
{
  string s = "cats";
  s += " and dogs";

  for(unsigned int i=0;i<s.length();++i)
     s = s.substr(1,s.length()-1) + s[0];

  cout << s << "\n";
 
  return 0;
}

TOPIC: VECTORS AND ARRAYS

What is printed by the following program?

#include <iostream>

const int N = 4;

int main()
{
  int a[N][N];
  int i,j;

  for(i=0;i<N;++i)
     for(j=i;j<N;++j)
       a[i][j] = a[j][i] = i*j;

  for(i=0;i<N;++i)
  {
     for(j=0;j<N and a[i][j] < N;++j)
       cout << a[i][j];
     cout << "\n";
  }
  return 0;
}
	     
What is printed by the following program?

#include <iostream>

int main(int argc, *argv[])
{
    for(int i = 0; i<argc; i+=2)
      cout << argv[i]
    return 0;
}


TOPIC: CLASSES

Given the program:

#include <iostream>
#include <vector>

Class A {
public:
    A(int size) {data = vector<int>(size);}
    void set0(int n){data[0] = n;}
    void print0(){cout << data[0] << endl;}
private: 
    vector<int> data;
};

int main() {
    A a1(1);
    a1.set0(1);
    A a2 = a1;
    a2.set0(2);
    a1.print0();
    a2.print0();  
    return 0;
}

What does it print?



TOPIC: RUN-TIME ANALYSIS

Among the following pairs of functions, which one has larger rate of growth
and why?


1. (a) 256n or (b) 2n^2 + log(n) ?
2. (a) 30nlog(n)  or n^1.5 ?
3. (a) (n + 7)(n - 2) or n^2log(n) ?       


What is the time complexity of the following function?

const int MAX_N = 20;

int fillArray(int n)
{

   if(n <= MAX_N)
   {
      double a[MAX_N][MAX_N];
      for(int i = n-1; i > 0; --i)
         for(int j = i; j > 0; --j)
            a[i][j] = a[j][i] = i*j;
   }
}	   

What is the time complexity of the following function?

int find_root(vector <int> A) {
{
   int n = A.size();
   for(int i = 0; i < n; i++)
      if(A[i] == 0) return i;
   return -1;
}

Assume that the vector is ordered, describe an implementation of find_root
that has smaller time complexity.  Also describe what the new time
complexity would be.

</ul>