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.