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.

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?

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.