-------------
(I) Counting
-------------

(1) 
   Linear Growth: 
       a(i) = a(0) + i*d  for fixed constants d and a0. 
    I.e.,  a sequence with elements a0, a0+d, a0+2d, ... .
    E.g., 5, 9, 13, 17, ... .
    The DIFFERENCE between successive terms is a constant: d.

    Exponential Growth: 
       a(i) = a0*r^i,  where a0 and r > 0 are fixed nonzero constants.

    I.e.: A sequence of the form a0, a0*r, a0*r^2,...
    If 0 < r < 1, we call it decay rather than growth.
    The RATIO of successive terms is constant.

(2)  
Moore's Law states the following.
Since about 1960, about every 18 months,
  -- the minimum feature length on a chip decreases by 0.7X.
  -- the on-chip density of logic devices (per mm2) doubles.
  -- the cost of memory (per bit) decreases by 0.5X.
  -- the number of operations performed per second doubles.
  -- the cost of building a chip fabrication plant doubles.
  -- every 15 years, computers become 1000 times more powerful!

The trend is expected to continue through at least 2008.

(3) 
Because Moore's law will continue for another 5--10 years, the exponential
growth suggests that more growth in computing power may occur in that
time than in the previous 50 years.


(4) 
It's 1/2 of the area of the rectangle of size (N+1) by N, 
which is exactly N(N+1)/2.
 

(5) 
Let S(N) = 1+2+...+N.  Recall from Ex. 1.4 above 
that S(N) = N(N+1)/2 which is approximately N*N/2 (the quadratic
term N*N/2 dwarfs the linear term N/2), when N is large.
Let .=. denote "approximately equals." 
Hence, S(2N) .=. 2N*2N/2 = 4*N*N/2 .=. 4*S(N).  
I.e., S(N) approximately *quadruples* when N is doubled, 
once N is large enough (e.g., about N >=10 ) 
that the above approximations are accurate.

Technical details (optional).
You may ask, what precisely does approximately equal mean?
Here, we have an asymptotic relationship: as N increases, 
the relative accuracy of the approximation S(N) .=. N^2/2  increases also,
because the limit of N / N^2 is zero as N increases to infinity.
I.e., for any given level of accuracy, there is a threshold N0 such
that for all N > N0, the approximation is valid. )
                       
(6)

(i)  N(N-1)/2 unordered pairs.  If you list them all systematically
for a small example, you will see that there are 
      (n-1)+(n-2)+...+2+1 = n(n-1)/2.
 Alternatively, using the next exercise, there are N choices for the
 first element and N-1 choices for the second, but we must divide by
 2 to avoid treating (a,b) as distinct from (b,a).

(ii) N!   N choices for the first element, N-1 for the second, etc.

(7)

(i)  2^N
(ii) log(N)  (base-2)
 

------------------------
(II) Types and Representation
------------------------

 

(1) See answer at 
http://www.cs.ucla.edu/classes/winter05/cs31/lectures/defs.html

 

(2) Type casting : converting a VALUE of one type to 
                   a VALUE of another type

    Promotion : Convert without loss of information,
                 e.g., convert an int to a double.

    Truncation :  Convert with loss of information,
                   e.g. convert a non-integer double to an int.

    If a language and its libraries together support N types,
    then, by Exercise I above, there are N*(N-1) different possible
    conversions (here, the order of the pairing matters, because
    converting from type a to type b is not the same as converting
    from type b to type a).  Each such conversion has its own rules.
    That's a lot of rules!  I.e., the number of possible conversions
    grows as the square of the number of types.

    Rule of thumb: promotion is usually safe, but truncation
    may cause loss of accuracy.  Use conversion with caution.
    Be aware of the consequences of any conversion you use,
    especially implicit conversion done automatically by the compiler.
    If you understand what the conversion does, then it is often
    convenient and safe to use it.  If you don't, then it is 
    potentially very dangerous.

(3)
    386 = 256 + 128 + 2  (decimal)
        = 110000010      (binary)
        = 182            (hexadecimal (base-16).

(4)
   (i)  0.0001100110011...
   (ii) 0.5 in decimal has the exact binary representation 0.1.
   In general, any short sum of nearby powers of two will have an
   exact representation, e.g. 0.5 + 0.25 + 0.125 (decimal) = 0.111 (binary).
 
(5)
In this system, there are 4 representable numbers between every two
consecutive powers of two (including the smaller power of two
but not the larger one).  Representable numbers on the number 
line are spaced like the vertical bars below.

   ...||||| | | | |   |   |   |   |       |    ...
  0   1   2   3   4   5   6   7   8   9   10       numbers increase--->

Notes.
i) The number of representable numbers between zero 
and one equals the number of representable numbers 
between one and infinity.

ii) Between 1/2 and 1  there are also 4 numbers, not including 1,
and between 1/4 and 1/2 there are also 4 numbers, not including 1/2.

iii) A special representation for 0.0 (zero) is required.

iv)  Negative numbers are similar (mirror image across 0).


(6) char caseChange(char ch){
      char d;
      if( ch >= 'a' && ch <='z'){   // ch is lower case
        d=ch-'a';
        return char('A'+d);
      }
      else if( ch>='A' && ch<='Z')   // ch is upper case
        return char('a'+d);
      else
        return c;
     }


-------------
(III) 
-------------
Please see the online definitions and the first set of lecture notes.
http://www.cs.ucla.edu/classes/winter05/cs31/lectures/defs.html
http://www.cs.ucla.edu/classes/winter05/cs31/lectures/intro/intro.pdf
 

-------------
(IV)
-------------
The most important element of good style is a modular design:
a hierarchy of small, loosely coupled functions whose
communication (through parameter lists and return values)
is precisely regulated, with preconditions strictly enforced.

For further discussion, see
http://www.cs.ucla.edu/classes/winter05/cs31/hw/style.html
 

----------
(V) Calendars
----------
#include <string>
#include <iostream>
#include <iomanip>
using namespace std;

void printNewCal(int days_per_wk, int days_per_mo, int first_day,
                  string monthName ){
      cout<< "\n      " << monthName << endl;

    //----Print out space before the first day:
      for(int i=1; i<first_day; i++)
            cout<<"   ";

    //----Start printing calendar :
      for(int i=0; i<days_per_mo; i++){
            cout<<setw(3)<<i+1;
            if( (i+first_day)%days_per_wk == 0 )
               cout<<endl;
      }
      cout<<endl;
}


----------
(VI)
----------
void Egyptian(int levels, char x) {

      for(int i=1; i<= levels ; i++){
         //---print the spaces :
         for(int j=1; j<=(levels-i); j++)
             cout<<" ";

            //---print the characters :
            for(int j=1; j<=(2*i-1); j++)
                  cout<<x;
            cout<<endl;
      }
}


void Mayan(int levels, char x) {
      for(int i=1; i<= levels ; i++){
            for(int j=1; j<=(levels-i); j++)
                  cout<<" ";
            for(int j=1; j<=(2*i+1); j++)
                  cout<<x;
            cout<<endl;
      }
}

----------
(VII)
----------
(This version of the solution assumes F(1) = 1, F(2) = 1, ..., 
and F(i) is requested.  The alternative form F(0) = 0, F(1) = 1, ...
with F(i) requested is similar but requires a small change to the loop
header, listed under the "Alt" comment below.)

void fibonacci(int i){
   int fib1 = 1, fib2 = 1, nextFib =1;      
   for(int j=3; j<=i; ++j){     // Alt:  for( int j=2; j<=i; ++j) { ...
     nextFib = fib1 + fib2;
     fib1 = fib2;
     fib2 = nextFib;
   }
   cout<<"Element "<< i <<" of the Fibonacci sequence is "
       << nextFib << endl;
}

The above solution uses only 4 integer variables,
no matter how large the value of its input, i.  The number of
additions is approximately i.  Hence, the function requires
a constant amount of storage and an amount of run-time directly
proportional to i.

The following solution, "slowFib()," requires exponential time and is very
inefficient, because the incremental tree recursion leads to
many identical subproblems being solved separately.
slowFib() will not be useful for values of n greater
than about 15.  

int slowFib(int i){
   assert (i > 0);
   if (i==1 || i== 2) return 1;
   else return slowFib(i-1) + slowFib(i-2);
}