Week #7

Week #7

#17

get wrong right
S: forall x in X, forall y in Y, P(x,y) => Q(x,y)
To disprove S, should you prove
forall x in X, forall y in Y, P(x,y) => neg Q(x,y) X
What about
forall x in X, forall y in Y, neg[P(x,y) => Q(x,y)] X
We should prove:
neg S: exists x in X, exists y in Y, P(x,y) and neg Q(x,y) O

e.g. forall n in N, T(n) => T(n2)
Proof:
Assume n in N
Assume T(n)
Then n = 7i + 1, some i in N         # defn of T(n)
Then n2 = (7i+1)2 = 49i2 + 14i + 1   # algebra
= 7(7i2 + 2i) + 1   # more algebra
Then exists i0 in N, n2 = 7i0 + 1    # i0 = 7i2 + 2i in N
# 7, 2, i in N, N closed under *,+
Then T(n2)                           # defn
Conclude ...

e.g. Disprove forall n in N, T(n2) => T(n)
In order to disprove the statement, prove its negation, which is:
exists n i N, T(n2) and neg T(n)
Pick n = 3 /*this place can leave blank at first*/, Then n in N
Then n2 = 36 /*this place can leave blank at first*/
Then exists i in N, n2 = 7i + 1    # i = 5
But neg(exisits k in N, n=7k+1)    # 6 = 7*0 + 6
Then T(n2) and neg T(n)
Conclude ...

#18

Direct Prove Implication
assume A, derive C
Indirect Prove Implication
assume neg C, derive neg A
Prove things about typical representative
assume x in R, ... Conclude forall x in R, ...
Prove the existence of x in D, with property P(x)
pick x = ___, show x in D and P(x)


Sorting strategies
-insertion sort
    <-4
1  2  3    5  6  7
- selection
4<->1<->2<->3  5  6  7
- Radix
- Quick sort
- Tim
- Merge sort
- ...

# The speed of different algorithm depend on input/hardware

Abstract Steps
f(x) = x2, g(x) = 3(x)+50, h(x) = 15x2 + x