Week 11 sLOG

This is the second last week of class in this semester, and only one class left. We have been learning induction this week, which was covered in MAT137 as well as in high school, so the only difficulty is the formatting of the proof in CSC165 is slightly different than what I have learned previously. In previous courses, we usually find the base case first, so that function f(x) works, then but with some algebra we proof that f(x+1) works as well, and then we have to write a pretty long statement saying why does this work. In this course though, we assume f(x) is already working, we only have to proof f(x+1), which is simpler.

On Friday, the professor gave us a question to work in class. The question was if a rectangle that has n (rows) by m (columns) square boxes, and draw a straight line diagonally, how many square boxes will it intersect with. After trying with couple small cases, such as, m = n = 2, m = n = 3, m = n = 4, m = 2 n = 3, m = 3 n = 2, m = 4 n = 3 etc, I found that there is a pattern and I created a little method on Python that would return that number of boxes that a diagonally line would intersect with.

def diagonal(n, m):

‘’’ (int, int) -> int

   Return the number of boxes that a diagonal line will intersect with, assuming m and n are larger than 1’’’

if m = n:

    return m

elif m > n:

    return 2n

else:

    return 2m

Basically, if the rectangle is a square, then the diagonal line would intersect with the number of rows or columns boxes; else the diagonal line would intersect with twice of the number of rows or columns depending on if there are fewer rows or fewer columns.

Will A Function Halt? (Week 10 sLOG)

In this week’s lecture, we have finished discussing about Big-O and Big-Omega, and started talking about wether a function is computable or not. The way we know if method will run or not is kind of interesting, we create another method to test if the function is computable.

With the method we talked about in class, halt(f, i), it’s the first time I have ever seen a method inside a method.

def initialized(g, v):

''' return True if g initialize v on every possible input'''

…

def halt(f, i):

      def f2(x):

            del (x)

            print(x)

      return not initialized(f2, x)

Basically, in these two methods, it tests if a given input is computable in a function. In the method, f2, after inputing the value x, it will delete the value, and since x is not defined anymore,  when it call ‘print(x)’, it will create an error and not able to print the value. Then initialized(f2, x) will return False since x is not defined, and the negation of False is True, so the method halt(f, i) will return True, meaning the function will stop running. I found that this is an interesting idea to test a function in a method, and negate the result. 

Proof of Big-O and Big-Omega (Week 9 sLOG)

Is the 9th week of the course, both assignment 2 and term test 2 have finished, only assignment 3 and the final exam is left behind in this course. I didn't do as well in the term test 2, I have trouble doing proofs with "floor", "ceiling" or absolute values, which I am not very familiar with, and its something I have to work really hard on, everything else we learned in this course are fairly easy.

In the past two weeks, we have been proofing the "big-O"  and the "big-Omega", 

Big-O

Big-Omega

which has similar meaning to the maximum and the minimum run-times of the growths of two functions. Basically is just finding a value such that when the first function multiple by it, the second function is either smaller or larger compare to it. I found that in most cases, the proof is not that difficult, as we are just modifying the original function so that some other function is larger (or smaller) compare to it; moreover, the requirements of our proofs are now less restricted, we can cut out most of the end booking lines, which makes it a lot less time consuming. I found that the most difficult part of this kind of proofs is when doing computation with inequality, it is hard to keep track with the signs and not sure if it works with negative number or zero.

Proof of Worst Case (Week 8 sLOG)

We have been doing proofs for around 3 weeks, and it was mostly mathematical proof. And this week, we have been introduced proofing the maximum steps of a method, and mostly contains loops in it. When I programming in the past, I never thought of the maximum steps, or time load that would takes to run through a code, maybe because of the processing power and the amount of random access memory our computers have nowadays, most of our program can be run through very quickly and with lots of storage space. Though, if the input is related to the code quadratically, maybe even more, then the larger size of the input is, the more time will be required to run through the code and that will be noticeable. 

However, after proofing the upper bound and the lower bound of the worst case performance, I am still not quite understand the method and the structure of these proofs. I am hoping this will be explain clearly in next week’s tutorial.

Structure of Proof (Week 7 sLOG)

To the 7th week of class, we have started doing more proofs, mostly mathematical proofs. On Monday, we have learnt that even though we might be able to do a proof initially, though, we can still write all the structure of the proof. Pushing the proof inward, and usually by doing some mathematic algebra on the side, we can figure out the proof easily. On Wednesday, we have learnt that there are several inference rules that can apply when doing proofs, just as manipulation rules. Then have been introduced about different ‘steps’.

Introducing Proofs (Weeks 6 sLOG)

The result of the term test from last week has been announced, and I did fairly well in it. After the first term test, we have been learning about proofs in class; what is a proof, how to proof and the structure of proof. 

In this week’s lectures, I learnt that sometimes we don’t necessarily to understand to know how to proof a statement in the beginning. Instead, we can write down the assumptions and the conclusions first, just like doing negation of a statement, we push the statement inward, until we get to a point where it has to be explained. And this method helps me a lot for understanding and showing a proof. This weeks’ classes are mostly proofing some basic algebra and definition of limits, and they are rather easy to understands, so we can focus on the basic structure.

First Term Test (Week 5 sLOG)

This is the 5^th week of class and also the first term test of this course. Everything that has been introduced in this course is fairly simple. I have learn how to use Venn diagram to show sets that is true or not; basic logic symbols to represent a statement; implications, contrapositive, converse and negate different statements; and also the basic structure of a proof.

I redo all the tutorial problems and quiz, also the past term test from last year, feeling confident with the term test. After writing the term test, checking with the model answers, I believe I should have done fairly well in it.

This week’s lecture is mostly about proofs, we learn more about the structure, what statement has to be made before showing and proofs; how to do a proof with the given materials and by using implications, we prove something to be true, or by contradiction, we could proof something to be wrong.