Day 1 - CPSC 2120



Office Hours - McAdams 204, 9:00 - 9:30 daily
Other hours by Appointment

Dan Welch Office Hours
Before/After lecture or lab

Daily Quizzes

Order n, n^2, log n


for (i=1;i<5;i++)
	for (j=1;j<10;j++)
		
		A[i][j] = A[i][j] * 10;


Order one of complexity or constant.  runs exactly 4 * 9 times (36).

When doing a search on an array [n x n], the order would be an order n^2 



COMMON MATHEMATICAL FORMULAS
----------------------------



Exponents:

   X^a * X^b = X^(a+b)

   X^a / X^b = X^(a-b)

   (X^a)^b = X^(a*b)

   X^n + X^n = 2 * X^n

   2^n + 2^n = 2^(n+1)

Logarithms: 

   Definition: x^a = b  iff  log_x b = a

   Theorem:    log_a b = (log_c b)/(log_c a)   a,b,c > 0, a != 1

   Theorem:    log a*b = (log a) + (log b)

   Theorem:    log a/b = (log a) - (log b)

   Theorem:    log a^b = b*(log a)

   Theorem:    log x < x  for all x > 0

Series:

   2^0 + 2^1 + 2^2 + ... + 2^n = 2^(n+1) - 1

   a^0 + a^1 + a^2 + ... + a^n = [a^(n+1) - 1]/(a-1)

   if (0 < a < 1) and (n -> infinity)
      a^0 + a^1 + a^2 + ... + a^n -> 1/(1-a)

  ***IMPORTANT*** 1 + 2 + 3 + ... + n = n*(n+1)/2

   1 + 4 + 9 + ... + n^2 = n*(n+1)*(2n+1)/6

Powers of 2:

	i    |    2^i (prefix)  
      -------|-------------------
	0    |    1
	1    |    2
	2    |    4
	3    |    8
	4    |   16
	5    |   32
	6    |   64
	7    |  128
	8    |  256
	9    |  512
       10    | 1024 = K (kilo-)
       20    |        M (mega-)
       30    |        G (giga-)
       40    |        T (tera-)
       50    |        P (peta-)
       60    |        E (exa-)
       70    |        Z (zetta-)
       80    |        Y (yotta-)


   Examples:  2^24 = 2^4 * 2^20 =  16M
              2^59 = 2^9 * 2^50 = 512P
              2^16 = 2^6 * 2^10 =  64K

	2^30 = G = K * M = M * K
	2^40 = T 
	2^50 = P
	2^60 = E
	2^70 = Z
	2^80 = Y
	2^90 = ??

	2^8 * 2^40 = 2^48 = 256T
	2^6 * 2^50 = 2^56 = 64P

Powers of 10:

	i    |   10^i (prefix)
      -------|-------------------
       -1    |    deci-
       -2    |    centi-
       -3    |    mille-
       -6    |    micro-
       -9    |    nano-
      -12    |    pico-
             |

   Examples: 25 * 10^(-9) seconds = 25 nanoseconds
             34 * 10^(-3) meters  = 34 millemeters
             15 * 10^(-6) liters  = 16 microliters

PROOF BY INDUCTION:


****

A:

N = 1

1 = 1(1+1)/2

1 = 1 * 2/2 = 2/2   // BASE CASE

B: INDUCTIVE HYPOTHESIS

ASSUME TRUE FOR N = K
1+2+3+...+K = K(K+1)/2

= K(K+1)/2 + (K+1)

= (K/2 + 1)(K+1)

= ((K+2)/2)(K+1)

PROVE FOR N = K + 1

By Induction, we have proven this to be true for all integers > 1.