CSC165 SLOG: 十月 2014

2014年10月24日星期五

CSC165 SLOG Week7

What’s something new I learned this week?

proof by cases :

split your argument into differences cases and prove the conclusion for each case.

Attention : the union of the cases are covering ALL possibilities !!!

uniqueness (math prerequisite) : if m and n are natural numbers, with n ≠ 0, then there is exactly one pair natural numbers (q, r) such that: m = qn + r, n > r ≥ 0,divide m by n, the quotient and remainder are unique.

Patterns of inference :

Two categories of inference rules

➔ introduction: smaller statement => larger statement
➔ elimination: larger statement => smaller statement

introduction rules:

1. negation introduction: assume A leads to contradiction => ¬A

2. conjunction introduction: c is red, c is fast => c is red and fast

3. disjunction introduction: c is red => c is red or fast

4. implication introduction: assume A, then B ⇔ A => B

assume ¬B, then ¬A ⇔ A => B

5. equivalence introduction: A => B and B <=> A <=> B

6. universal introduction: assume a ∈ D, then P(a) =>

∀ x ∈ D, P(x)

7. existential introduction: P(a) and a ∈ D =>

∃ x ∈ D, P(x)

elimination rules:

1. negation elimination: ¬¬A = A

A and ¬A => contradiction!

2. conjunction elimination: A ∧ B ⇔ A and B

3. disjunction elimination: A ∨ B and ¬A => B

4. implication elimination: A => B and A => B

A => B and ¬B => ¬A

5. equivalence elimination: A ⇔ B => A => B and B => A

6. universal elimination: ∀ x ∈ D, P(x) and a ∈ D => P(a)

7. existential elimination: ∃ x ∈ D, P(x) =>

Let a ∈ D such that P(a)

Tips for how to be good at proofs:

➔ become familiar with these patterns, by lots of practice

➔ recognize these patterns in your proof, use the manipulation rules to ger closer to your target.

what “running time means in computer science:

➔ It does NOT mean how many seconds are spent in running the algorithm.

➔ It means the number of steps that are taken by the algorithm.

➔ the running time is independent of the hardware on which you run the algorithm.

➔ It only depends on the algorithm itself.

absolute running time is not important:

what we really care about is how the number of steps grows as the size of input grows!!

we don’t care about the absolute number of steps,

we care about: “when input size doubles, the running time quadruples!

so, 0.5n² and 700n² are no different!

Constant factors do NOT matter!

only the highest-order term matters:

we don’t need to study algorithms in order

to sort two elements, because different

algorithms make no difference,

we care about algorithm design when the

input size n is very large,

so, n² and n²+n+2 are no different,

because when n is really large, n+2 is

negligible compared to n²

O(n²) is an asymptotic notation:

O( f(n) ) is the asymptotic upper-bound

➔ the set of functions that grows no faster than f(n)

analyse the time complexity

of a program : for example, linear search.

➔ program running time varies with inputs

➔ among inputs of a given size, there is a worst case in which the running time is the longest.

worst-case time complexity: tP(x) : running time of a program P with input x. The worst-case time complexity of P with input x in I with size n is

What’s something that frustrated and challenged me this week?

I think it should be counting the running time for certain function in python, especially the for loop and while loop, and the case that a loop contains another loop. Also, counting the worst-case is disturding.

How confident do you feel about material covered this week?

Not really, if finding running time appeared in final test, it will definetely take me a lot of time to solve it.

How does course material relate to other classes or interests?

I think the merge sort and quick sort mentioned in lecture is exactly the same as what I'm learning in CSC148 Sorting part, and I think the website the instructor provided is really useful for both CSC165 and CSC148: http://www.sorting-algorithms.com/

Problem solving:

problem solving for pennies in Friday's lecture.

2014年10月8日星期三

CSC165 SLOG Week5

What’s something new I learned this week?

Proof using contrapositive : when the reverse direction is easier to prove than the original.

General idea: Instead of proving P => Q, prove ¬Q => ¬P (equivalent to P => Q)
When it’s not easy to prove P => Q, try proving ¬Q => ¬P

Proof using contradiction : a special case of contrapositive

P => Q, with implicit P : sometimes it is not clear what P is, for example : “If every common sense is true, then Q”, contrapositively, “if not Q, then something in common sense is false”, i.e. if not Q, then it will contradict with some common sense. When the assumptions are implicit, try assuming ¬Q, and see whether it leads somewhere, hunting for a contradiction.

Proof for existence

direct proof of the existential : find a single example.

Proof about a sequence

With multiple quantifiers, zoom into smaller and smaller part of the statement, layer by layer.

One proof may consist of several different structures

What’s something that frustrated and challenged me this week?

I did't do quite well as I thought in Assignment1, and I think i could improved a lot later on

How confident do you feel about material covered this week?

I thought I understood the material pretty well.

How does course material relate to other classes or interests?

The proof material is kind of like what I met in MAT137 class, though I didn't study the proof structure then. And I think the structure I'm learning is helpful and essential for further math proofs.

How did your tutorial/test/assignment go this week?

I'd like to address assignment1 question4 and the proving sstructure the TA mentioned in this week's tutorial.
Direct Proof Structure: 1) domain assumption 2) assume the antecedent 3) show consequent 4) close assumptions

2014年10月5日星期日

CSC165 SLOG Week4

What’s something new I learned this week?

1、Transitivity

(P ⇒ Q)∧ (Q⇒ R) ⇒(P ⇒ R)

2、Double Quantifiers

Free to switch the order of quantifiers, does not change the meaning.The order in which we consider elements of an ordered pair doesn't change the logic.

3、A proof foretold

1. Understand why you believe the thing is true. This step is

messy, creative, but then increasingly precise to identify

(and then strengthen) the weak parts of your belief.

2. Write up (express) why you believe the thing is true. Each

step of your written proof should be justied enough to

convince a skeptical peer. If you detect a gap in your

reasoning, you may have to go back to step 1.

4、Chains with ∧or ∨

(P⇒R1)∧(P⇒R2 ) ⇔ (P ⇒ (R1∧R2))

((R1⇒ Q)∧(R2 ⇒Q)) ⇔((R1∨R2) ⇒Q)

How did your tutorial/test/assignment go this week?

For tutorial, I learned that "A and B are both guarantees that C is true. " means (A ∨ B ⇒ C),not means A ∧ B ⇒ C.
And for assignment1 this week, I learned that
1)the converse of the contrapositive of the imlpication, is the same as the convere of the implication.
2) "necessary and sufficient" means "⇔"
3) " A ⇒ C" is true means A can imply C.