Cheatsheet for grading final

=========================================================

1

F F T F
T T F theta(3^n)

=========================================================
2

just irreflexive

just onto

O(n^2), O(2^n)
omega(2nlogn), omega(n^2)

=========================================================
3

a) (a,\emptyset), (a,{9}), (a,{12}), (a,{9,12}), 
   (b,\emptyset), (b,{9}), (b,{12}), (b,{9,12}) 

b) 19 choose 2  == 19 choose 17.   See formula for combinations with
repetition.


c) T_1 = 2
T_2 = 3

T_n = T_n-1 + T_n-2, for n >= 3

=========================================================
4

a) There are positive real numbers k and C such that
for all n >= k, f(n) <= Cg(n).

b) There is a martian M such that M is green but M is not tall or
M is not ticklish.

c) The relation requires that the two intervals overlap with the 
first one starting no later than the second one.  So a counter-example
to transitivity might look like

   (2,6)R(5,8) and (5,8)R(7,10) 
    but not (2,6)R(7,10)

A popular mistake was to try to build a general argument that a
counter-example had to exist.   

=========================================================
5  
a) For each pair of non-identical elements of A, you need to
decide whether the pair is related or not.   So you have

2^p choices where
   p = n choose 2 


b) Same choices as in (a), plus you need to choose which of the n
elements are related to themselves.   So

  2^{p+n}

c) 2^{n-1} - 1

Each division of A into 2 classes can be thought of as assigning 0 or
1 to each member of A.   There are 2^n such assignments.   But this
counts each division twice, because we don't care which class is called
"0".   So 2^{n-1}.   But one of these divisions puts all elements in the
same class, so we have to subtract 1.

=========================================================
6

a) Let (a,b) and (x,y) in N^2.   Suppose f(a,b) = f(x,y).
Then (5b,b^2 + a) = (5y, x^2 + y).   So 5a = 5y and
b^2 + a = x^2 + y.

5b = 5y implies that b = y.
So then b^2 + a = x^2 + y implies that b^2 = x^2.   
So then b = x, since all the variables are non-negative.

b)  Let x,y in A, x != y and suppose that xRy.   We'll show by
contradiction that yRx isn't true.   Suppose yRx.  Then
xRy and yRx implies that xRx (transitivity).  But we know that
xRx doesn't hold because R is irreflexive.

=========================================================
7

a) 4.  Best way to show 4 is enough is to put a color label on each
node in the graph picture.  To show 3 can't work, notice there's a
group of 4 nodes for which all pairs are connected (K_4).

b) e decreases by 1, the other two don't change

c) v - e + f = 1 + k

=========================================================
8

a) theta(n)
   i increases and never decreases.  i starts at 1 and the loop
   stops when i gets bigger than n.

b) n times.  inputs in which each value is followed by an equal or
smaller value.

c) theta(n)

=========================================================
9  Let's use ~ as ascii symbol for congruence.
Suppose a ~ b (mod k)  and c ~ d (mod k)
Then k | (a - b) and k | (c - d).
So a - b = kp and c-d = kq, for some p and q. 
So a = kp + b and c = kq + d.

Then a^2 + c = (kp + b)^2 + (kq + d)
            = (kp)^2 + 2bkp + b^2 + kq + d
            = km + b^2 + d
where m = kp^2 + 2bp + q 
So (a^2 + c) - (b^2 - d) = km
So k | (a^2 + c) - (b^2 - p).
So (a^2 + c) ~ (b^2 - d) (mod k).


=========================================================
10
   Base:  F_4 = 3 = 2^2 - 1
          F_5 = 5 < 2^3 - 1

   IH:  Suppose that F_n <= 2^{n-1} -1 for all n between 4 and k

   Inductive step:  F_{n+1} = F_n + F_{n-1}
                            <= 2^{n-1} -1 + 2^{n-2} -1
                            = 2^{n-1} + 2^{n-2} -2
                            <= 2^{n-1} + 2^{n-2} -1
                            <= 2^{n-1} + 2^{n-1} -1
                            = 2^n -1

Popular mistakes:  forgetting the second base case, trouble with
the mechanics of stating the strong inductive hypothesis.

=========================================================