Winter 2005 CS 31 Midterm Answer Key

------------------------
       PART I.
------------------------

1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20
e   c   e   d   b   f   d   c   b   b   e   c   e   c   d   a   f   b   c   d

------------------------
       PART II.
------------------------

---
Q21
---
About 2^n (two to the power n) steps are needed for the function given.
(It's an incremental tree recursion.)  The function is very 
inefficient, as a solution exists using a fixed amount of storage
and operation count proportional to n (see Written HW 1).

---
Q22 
---
puzzle(x, n) = x^n  (x to the power n) for given user specified
values x and n > 0.

---
Q23 
---
puzzle(x, n) requires approximately log n  (log base 2) steps
(it's a divide-and-conquer chain recursion).

---
Q24 
---
(a)  1   (b)  5   (c)  2   (d)  2.4   (e)  1.0  

---
Q25 
---
mystery(x) returns a closest integer to x.
When the closest integer to x is not unique,  
mystery(x) rounds positive x values up and negative x values down.


------------------------
       PART III.
------------------------

---
Q26 
---
////////////////////
// (a)
////////////////////
int pivotPoint( int a[],  int n,  int p ){
   int total = 0;
   for (int i = 0; i < n; ++i)
      if (a[i] <= p) ++total;
   return total;
}

////////////////////
// (b)
////////////////////

void split ( int a[], int n,  int p ){
   int pplace = pivotPoint( a, n, p );
   int i = 0, j = pplace;
   while ( i < pplace && j < n ){
      if ( a[i] < p )
         ++i; 
      else if ( a[j] >= p )
         ++j;
      else  {   // if ( a[i] >= p &&  a[j] < p ){
         swap( a[i], a[j] );
         ++i; ++j;
      }
   }
}

---
Q27 
---
#include <iostream>
#include <string>
using std::cout;
using std::cin;
using std::endl;
using std::string;


void draw(int ht,int w, char fillc, char stripeD, char stripeC, int nS){
   int i, j, stripespacing = 0;
   
   if ((stripeD == 'v' || stripeD == 'd'
        || stripeD == 'h') && nS <= 0) {
   	cout << "Invalid number of stripes" 
   	     << endl;
   	return;
   } 
       
  if (stripeD == 'v' || stripeD == 'd') 
      stripespacing = w/nS;
   else if (stripeD == 'h')  
      stripespacing = ht/nS;


  for (i = 0; i < ht; i++) {
   for (j = 0; j < w; j++) {
     switch (stripeD){
   	   case 'p':
   		   cout << fillc;
   		   break;
   	   case 'h':
   		   if ((i-1)%stripespacing == 0)
   		      cout << stripeC;
   		   else
   		      cout << fillc;	
   		   break;
   	   case 'v':
   		   if ((j-1)%(stripespacing) == 0)
   		      cout << stripeC;
   		   else
   		      cout << fillc;	
   		   break;
   	   case 'd':
   		   if (j%(stripespacing+1) == i)  
   		      cout << stripeC;
   		   else
   		      cout << fillc;
   		   break;
   	   default:
         cout << "Invalid stripe type\n";
     		return;
   	 }

    }
    cout << endl; 
  }
}

////////////////////////////////////////////////////////
// The rest of the solution is optional, 
// provided for your convenience in checking.
////////////////////////////////////////////////////////

int main(){

   draw(3,4,'*','p','0',0);
        cout << endl;
        cout << endl;
   draw(3,4,'*','l','0',0);
        cout << endl;
        cout << endl;
   draw(6, 25, 'X', 'h', '-', 2);
        cout << endl;
        cout << endl;
   draw(6, 25, 'X', 'h', '-', 0);
        cout << endl;
        cout << endl;
   draw(5, 25, '*', 'h', '-', 2);
        cout << endl;
        cout << endl;
   draw(6, 20, '-', 'v', '+', 5);
        cout << endl;
        cout << endl;
   draw(6, 25, '#', 'd', '\\', 3);

   return 0;
}


/* Grading Standard --
   1. Basic Flow -- /5 
      basic function definition, nested for loops, switch or if-else
      statements on stripe type
   2. p -- /5 
      given basic flow, print out correct character - +5
   3. h -- /5
      very high-level pseudocode/correct algorithm - +2
      checking correct row - +1
      correct spacing - +1
      including flag boundaries - +1
   4. v -- /5
      very high-level pseudocode/correct algorithm - +2
      checking correct column - +1
      correct spacing - +1
      including flag boundaries - +1
   5. d -- /5
      very high-level pseudocode/correct algorithm - +2
      checking correct column, especially right shift - +1
      correct spacing - +1
      including flag boundaries - +1
   Points were given if code was very close and understandable,
   even if it wasn't precisely correct.
*/