Last Post

Well this is it, my final blog post. It’s been a fun journey this semester learning about logic, proofs, complexity and computability. Monday was a daunting lecture for me through which I was confused about why there are infinitely many more real numbers than rational numbers. I’m going to keep reading the notes and hope that something clicks because the proof shown in class once again didn't convince me. Tutorial was super easy since the reductions we had to make didn't require much work. I liked the in-class problem solving episode we did on Wednesday and my partner was definitely onto something. I didn't go to class today since I needed the time to study for my upcoming exams but I’m sure that it was a very fun lecture. Most importantly, I figured out the perfect solution to the diagonal problem on Tuesday night and I showed it to Professor Heap on Wednesday morning and he confirmed that it was correct. Here it is:

def diagonal(m, n):

    x = fractions.gcd(m, n)

    m = m / x

    n = n / x

    return x*(m + n - 1)

As you can see, the solution is quite simple and it involves reducing the problem to a case where either m or n is odd. I felt an amazing satisfaction when I finally figured it out and I’m really glad that the problem solving approach taught in this class led me to the right answer.

In closing, this course has been crucial to my understanding of proofs and logic. It has taken my knowledge to new heights and I can’t wait to start CSC236 next year. Professor Heap’s teaching style and jokes (most of which I think I was the only one that understood), were the best I have seen so far in my first year in university. He was also very approachable and helpful with a variety of different course materials. I hope that I have him as an instructor in my future courses since he is concise and entertaining. So long CSC165!

SLOG Entry #11 Week 11 Diagonal Progress

The lecture on Monday was like no other lecture we've had so far. Finally, something really grabbed my attention. I was completely new to the halting problem before and the idea of a program that could predict the behaviour of functions fascinates me. On that note, the way Professor Heap showed that the halting function cannot exist didn't convince me. The so-called naval_gaze function didn't impress me at all but it did make me think about naval_gaze itself. Basically, the function takes itself as input and returns where or not it halts by using an imaginary halting function. It then provides a contradiction because the function itself doesn't halt when halt is called on it. This makes me very skeptical. It seems to me that the function is set up in a way simply to provide a contradiction. Having said that, I could probably make a function that takes almost any function that is commutable as input and comes up with a contradiction. Does that mean that the function is non-computable? No.

I won't talk about the tutorial in this blog post because I would like to post my partial solution to the diagonal problem in here. After a about an hour of drawing many different grids, I came up with a formula that worked for many numbers less than double digits and for many odd numbers in double digits.

To begin, I recorded the result of many different grids. 1x2, 1x3, 1x4, 2x3, 2x4, 2x5, 2x6, 3x3, 3x4, 3x7, 3x9, 4x6, 4x8, 4x 10, 7x5, and 7x12 to name a few.

I first noted that for any two numbers n and m, if one of the numbers is odd and they don't divide each other  then the number of squares covered is equal to (m+n)-1. I also noticed that if both numbers are even and one divides the other, then the numbers of squares is max(n, m). I then tried to reduce cases where both numbers are even but don't divide each other to a case when one is odd so that I could the first algorithm (m+n)-1. I did this by dividing both m and n by 2 and multiplying (m+n)-1 by how many times I divided them both by two. I soon realized that this didn't work for a grid that is 40x60.  In other words, my formula needs to be tinkered with some more.

My function is this: 

def diagonal(n,m):

    if n < m:

        if m%n == 0:

            return m

        

        elif n%2 == 0 and m%2 == 0:

            count = 1

            while n%2 == 0 and m%2 == 0:

                n = n//2

                m = m//2

                count = count + 1

            

            return (count*((n+m) - 1 ))

    

        elif n%2 == 1 or m%2 == 1:

            return (n+m) - 1  

    else:

        if n%m == 0:

            return n    

        

        elif n%2 == 0 and m%2 == 0:

            count = 1

            while n%2 == 0 and m%2 == 0:

                n = n//2

                m = m//2

                count = count + 1

            

            return (count*((n+m) - 1 ))

        elif n%2 == 1 or m%2 == 1:

            return (n+m) - 1     

It works for most inputs less than double digits but of course that's not good enough for me.

So I am continuing to look for a more correct function that involves reducing complicated cases to simple cases. I feel that I'm very close to the right answer and I really hope to get it in by next week.

SLOG Entry #10 Week 10

Monday's class made me realize how long it has been since we did differentiation in my calculus class. Having to use L'Hopital's rule seemed impossible until I looked in my math textbook to remember how to apply it. It was obvious from the example of 2ⁿ ∉ O(n²) that the proof would involve taking a limit as n → ∞ to show that 2ⁿ grows significantly faster than n². For the second time in this course, I found myself restricted by my knowledge of the mathematical prerequisites and wishing that we would have spent more time in class reviewing how to apply L'Hopital's rule. Big-Omega and Big-Theta were very self-explanatory seeing as how there are just minute differences between the definitions of them and Big-Oh. On top of that, I really liked proving statements about more than one function since I think that such problems have more real life applications than just statements that claim something about a single function. The problems we did in lecture on Friday were super easy but I assume that’s just because there’s an intuitive feel to these kinds of problems.

I was surprised to see such a difficult tutorial handout on Tuesday. I was under the impression that I had a firm understanding of the material but I began to question that view after I sat in my chair waiting to see the problem taken up. I’ll admit that the solution to the tutorial handout was easy to understand but it simply didn't follow from any examples we did in class. I realize that tutorial is supposed to be a learning opportunity, but I think that more closely related examples to the tutorial handout should have been shown in class so I could have an idea of what I was supposed to do.

I’d like to finish off by saying that I am still working hard on the diagonal problem and that I hope to get a solution by the last week of class.