CSC165 SLOG Week8

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.

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|

• 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/