CSC165 SLOG

2014年12月1日星期一

What’s something new I learned this week?

formal definitions of O and Ω

O(n²): set of functions that grow no faster than n²

Ω(n²): set of functions that grow no slower than n²
ϴ(n²): set of functions that are in both O(n²) and Ω(n²) (functions growing as fast as n²)
insertion sort worst-case running time

➔ we first derived the exact form of WIS(n), then determined it’s upper and lower bounds

➔ don’t alway have to derive the exact form, as we will see soon.

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

I think the most challenge lies on the counting the runtime and worst-case running time, proof part is fine, but the first step is always hard for me, I suppose I need more time to practice.

How does course material relate to other classes or interests?

Maybe the csc148 class, the runtime stuff and the efficiencywe talked about in the class.

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

I had a little problem in this week's tutorial since there was a problem relating to counting runtime and that's my weakness.

What’s something new I learned this week?

If there is a mapping from X to Y like this, then we have |X| = |Y|

f is “1-1”, i.e., each y mapped to by at most one x. f is “onto”, i.e., every y has some x that maps to it.
Given two sets X and Y, if there exists a well defined function f : X ↦ Y that is 1-1 and onto, then |X| = |Y|. We can use this to compare the sizes of sets with infinitely many elements. Key is: find an f : X ↦ Y
“countable”：when we count, we do: 0, 1, 2, 3, 4, …，that’s basically enumerating natural numbers，so we say that set N is countable, and any set A satisfies | A | <= |N| is countable.

The argument we made has a name, it’s called “diagonalization”.

➔ Given any list of countably many of functions, we can always construct an fx that is outside that list.
➔ that means the set of all possible functions is uncountable.
➔ Since we can only program countably many Python functions
➔ there are uncountably many functions that we cannot program in Python, or in any computer language.

Induction: Mathematical induction is a proof technique typically used to establish a given statement for all natural numbers.
Principle of Simple Induction (PSI)

Final Exam Review: see the week12 slides for the details :)

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

I think it should be the countability and computability part, and it's lucky for me that countability parrt will not be tested in the final exam:)

Also, it's a pity having missed the final lecture in the Friday to say googbye to Danny, but I think I 'll see him again some time.

How confident do you feel about material covered this week?

For the coumputability part, to be honest, not really confident, but after the review for the final, I think I can do it well finally.

How does course material relate to other classes or interests?

the 1 to 1 and onto part is what I've learned in MAT223 and MAT224, so it's not new to see these again.

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

Quite well I think, since I have got 2 awesome partners for Assignment3, I guess I could get a reasonable mark finally.

Here are some bloggers that I think are fantastic:)
http://yuejiang165.blogspot.ca/
http://csc165maks.blogspot.ca/

2014年11月27日星期四

CSC165 SLOG Week6

What’s something new I learned this week?

non-boolean functions：A function whose return value is not True/False. For example, x > 5 is boolean, x + 5 and sinx are non-boolean.
“floor of x” : the largest integer that ≤ x

⌊x⌋ is not a variable, it’s a function like f(x), and quantifiers are only applied to variables, so you cannot apply a quantifier to ⌊x⌋

Tips for proving non-boolean functions:

1. fully understand the definition of the function, since that’s all you have.

2. manipulate expressions into forms that are closer to those in the definition,

since the definition is all you have and you will have to use it.

prove something false or disprove something

How to disprove a statement S ? Just prove ¬S is true.

Tips for proving something false or disprove something:

1. first make sure to negate it correctly

2. then prove the negated statement

3. draw examples to obtain intuition

proof about limits

for example:

Intuition:

δ is how close x is to 2

ε is how close x² is to 4

if x gets really really close to 2,

then x² gets really really close to 4.

Tips for proof about limits: wise choices are often found by backward
search (like the choice of δ)

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

I think it should be the proof for the limits, first so many Greek letters, and they all represent different meaning, and for proof , given any ε, I should always make a wise choice of δ so that I can win, which means I should know what δ I should pick before I write the proof, which is kind of disturbed.

How confident do you feel about material covered this week?

I think I understood the most of the material, but I still need to practice because when I wrote proof for limits, it was getting kind of hard, and it took time to figure out which proper δ I should pick.

How does course material relate to other classes or interests?

Aha, the proof fot limits part reminded me of the limit definition I learned in MAT137 and I think the proof progress is much the same. except that now I understand more about why I write proof like that.

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

Quite well I think, my TA is really heapful and gave me some tips for doing proof.

2014年11月20日星期四

CSC165 SLOG Week10

What’s something new I learned this week?

➔ The set of all functions that take a natural number as input and return a non-negative real

number.

➔ big-Oh proofs for polynomials (standard procedure with over/underestimates)

➔ big-Oh proofs for non-polynomials (need to use limits and L' Hopital's rule.)

For this one I think I need more practice since it needs to use limits, which is a little harder for me.

➔ proofs for general big-Oh statements

(pick B and c based on known B’s and c’s)

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

What frustrated me most this week is absolutely the test2 !! I thought I could get a nice mark and actually I did get full mark for the previous two questions, but to my surprise, I got 0 for the third question!! I was nearly heartbroken... I admitted that there are drawbacks in my proof work since I didn't have enough time and I did a perfect version after the test. Therefore I think my thoughts using the contradiction is right, but I have no time to finish it... Anyways, I handed in a request form to Danny and I hope it works.

How does course material relate to other classes or interests?

The Big-Oh definition and its proof we talked about this week is much related to the efficiency we saw in CSC148 lectures.

What was one of your achievements this week?

Learned how to prove some general statements about Big-Oh, and I think I practiced it well.

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

Actually the tutorial went well and I think I could get a full mark in the quiz. But for the assignment, I'm not familiar with LaTax, so it's been hard for me to write assignment using this tool.

CSC165 SLOG Week11

What’s something new I learned this week?

A function f is well-defined iff we can tell what f(x) is for every x in some domain.
A function f is computable iff it is well-defined and we can

tell how to compute f(x) for every x in the domain. ot

herwise, f(x) is non-computable.
Halt(f, n) is well-defined and non-computable.
It is impossible to write one halt(f, n) that works for all functions f.( Proof:

construct a clever function that leads to contradiction )
Given any function, we use reductions to decide whether it is computable or not.

Reductions: If function f(n) can be implemented by extending another function g(n), then we say f reduces to g.

g computable => f computable

f non-computable => g non-computable (by contrapositive)

To prove a function computable, show that this function reduces to a function g that is computable
To prove a function non-computable, show that a non-computable function f reduces to this function.

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

It definetely should be the proof for halt(f, n). At first I was quite confused about why we picked a 'clever' function in the lecture, since we could write a certain halt(f, n) that works. And I also post the question on Piazza. After the instructor replied to me, I undrstood that I missed an important point : Here clever() is deliberately constructed counterexample for proving that there does not exist a halt() that works for ALL functions, so it is meant to be in this "bad" way. If we add a "not" after the "while", then it would work correctly therefore it is no longer the counterexample that we wanted.

How confident do you feel about material covered this week?

Not quite sure, still a little confused with the code appeared in the lecture slides and the halting problem. So I think I should read more in Course Notes and lecture notes.

How does course material relate to other classes or interests?

I think the code in the lecture slides are much like codes in python, but also different.

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

No tutorial this week :) and for assignment 3, I'm still working on it.

CSC165 SLOG Week9

What’s something new I learned this week?

More Big-Oh proofs
Tips for provifng :

➔ the ways we talked about of picking c and B, the main point of them is that we know how to show the bounding relation when picking in these ways.

➔ these are not the only ways, you can be more flexible when you are more familiar with

these types of proofs.
➔ In general, larger c or larger B don’t hurt.

Between polynomials, it is fairly easy to figure out who is big-Oh of whom, simply look at the highest-degree term, f(n) is in O(g(n)) exactly when the high-degree of f(n) is no larger than that of g(n).
Prove big-Oh using limit techniques

General procedure

1. prove using “some calculus” : L’Hopital’s rule
2. translate the limit into its definition with c and n’
3. relate this definition to the definition of big-Oh

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

I think my assignment2 and test2 didn't go well. For assignment2, since I was not familiar with the LaTex, it took me a lot of time to move proofs from paper to the LaTex, and I barely missed the deadline time :(. And for test2, I just didn't have enough time to fulfill the last question, though I write the structure and actually knew how to do it.

How confident do you feel about material covered this week?

for the general Big-Oh proofs, I think I'm familiar with it, but for the big-Oh proof using limit techniques, I think it still takes time for me to practice more since it is not easy as the former one.

How does course material relate to other classes or interests?

Prove big-Oh using limit techniques has used the definition of limit and L’Hopital’s rule I learn in Calculus I.

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

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.

订阅：博文 (Atom)

2014年12月1日星期一

CSC165 SLOG Week8

What’s something new I learned this week?

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

How does course material relate to other classes or interests?

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

CSC165 SLOG Week12

What’s something new I learned this week?

If there is a mapping from X to Y like this, then we have |X| = |Y|

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

How confident do you feel about material covered this week?

How does course material relate to other classes or interests?

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

2014年11月27日星期四

CSC165 SLOG Week6

What’s something new I learned this week?

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

How confident do you feel about material covered this week?

How does course material relate to other classes or interests?

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

2014年11月20日星期四

CSC165 SLOG Week10

What’s something new I learned this week?

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

How does course material relate to other classes or interests?

What was one of your achievements this week?

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

CSC165 SLOG Week11

What’s something new I learned this week?

How confident do you feel about material covered this week?

How does course material relate to other classes or interests?

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

CSC165 SLOG Week9

What’s something new I learned this week?

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

How confident do you feel about material covered this week?

How does course material relate to other classes or interests?

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

2014年10月24日星期五

CSC165 SLOG Week7

What’s something new I learned this week?

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

How confident do you feel about material covered this week?

How does course material relate to other classes or interests?