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.

SLOG Entry #9 Week 9 Test Week!

I have realized that instead of complaining about proofs, it would be more productive to embrace them instead. This hasn't been so hard to do this week since reducing complex polynomials to simpler expressions and coming up with constants to prove Big-Oh statements is challenging. I knew what Big-Oh meant from CSC148 last semester, but the definition we used in that course was very vague. The more precise definition that Professor Heap taught us in class on Monday was exactly what I was looking for and it made proving Big-Oh statements possible. Having done proofs for the past few weeks and constantly working with inequalities, the proofs just flowed from the tip of my pen. In all honesty though, current course material didn't really concern me this week since we had a test on Friday and I was focused on doing well on the test more than anything.

Considering that I did quite poorly by my standards on the previous test, I felt a lot of pressure to do way better on this one. Keeping that in mind, I was disappointed on Wednesday when we did no review whatsoever for the test and instead did a problem solving challenge. I enjoyed the in class problem solving challengs but I would rather have done it next week. On Friday, I was confident about the test but that didn't stop me from soaking my T-shirt in sweat. I don't know why, but my body was nervous about the test even though I wasn't. When I opened the test, I was relieved to see easy problems within it. By the end, I was more concerned with whether or not my writing was readable and if that's not a sign that I did well, I don't know what is. I feel very confident about the test and I can't wait to get my results. I think the fact that I didn't have another test immediately after and that there wasn't a snowstorm, really helped me concentrate and not make silly mistakes like I did on the previous one.

Lastly, I have picked the diagonal line problem as the problem that I would like to solve for the SLOG assignment since I think that I got very close to the right answer when we did it in class and the fact that someone else has already done it improves my confidence. In a nutshell, this week has been fun and educational but I do miss doing more course related things like in a regular week without a test.

SLOG Entry #8 Week 8

I would first like to say that the last post and next few posts I'll be making have been sitting in my notebook for some time but I've been too busy with other subjects to get around to posting them. I guess that's what happens when you don't have a laptop and your commute is 1 hour and 15 minutes one way. Here is my SLOG that I wrote for week 8:

My wishes from last week have been fulfilled while we've continued doing algorithm analysis and step counting. Also, the inclusion of graphs when we were discussing complexity classes really helped visualize the concept better. I've done this kind of visualization before where I've plotted 4000x⁴ and x⁵ and saw that at x = 4000, x⁵ overtakes 4000x⁴. However, proofs have gotten a little tedious by now and looking at the course notes suggests that they won’t be going away any time soon.

As for tutorial, I found it to be quite difficult and confusing since we used a method for counting steps much different than the one in class. For example, instead of each line contributing one step, all of the comparisons and indexing in a line of code were counted as steps. While I do think this method is more accurate, it seems to defeat the purpose of getting a sloppy approximation like we did in lecture. The sigma notation which I haven’t seen in a while threw me off quite a bit and I noticed myself trying to understand the sigma notation more than the actual problems. This time, I was very happy that the quiz was easier than the tutorial handout since I was not able to come up with the right answer for each handout problem on my own.

This week was much tougher than I expected it to be and the confusion between lecture and tutorial didn't help. Lastly, while I realize that proofs are important, I have become very bored with them and I’d rather get to a more problem solving oriented part of the course.

SLOG Entry #7 Week 7

I would like to start this blog post by saying that I was very excited to getting back into the coding aspect of computer science. During the break, I made several python programs just to test my skills after not having programmed since 3 months ago. It turns out that my skills were quite rusty at first but I got back on track very fast after about an hour. This leads me to express my liking for this week’s course material. I have come to realize that what I said in my previous blog post does not hold for delta-epsilon proofs. By that I mean it can be very difficult to pick a value for delta such that the limit holds for any value of epsilon. In some cases I like being proved wrong and I was glad to learn that there is much more to proofs than I had thought right before the break. Also, I would like to state my fondness of the algorithm analysis that we did Friday’s lecture. It was fun coming up with expressions for how many steps an algorithm takes and in all honesty, I never even knew we would do that in this course so I’m ecstatic about it.

In CSC-148, algorithm analysis was much more theoretical and it seemed as if we simply had to remember the time complexities of different sorting algorithms instead of derive expressions for them ourselves. Because of this, I was curious to see the behind the scenes of determining the complexity for an algorithm and I satisfyingly learned how on Friday. Tutorial this week unfortunately did not live up to my expectations yet again, and I found myself quite bored in it. Having said that, the quiz was more challenging than the previous quiz and proper indentation was required which I was pleased with.

CSC-165 has taken me by surprise this week with in depth step counting and algorithm analysis and I am glad we have  been engaging in this because a few of my future courses are specifically about algorithm analysis. I would like to end today’s post by saying that I wouldn't mind more code analysis in class in the future and that the practical part of algorithm analysis is just as important as the theoretical part.

SLOG Entry #6 Week 6

Proofs are quite easy for me. The examples we've done in class this week have been simple and logical. Having said that, I don’ think that I would consider them to be so easy without doing a proper outline first. For many of the proofs that I've seen so far, formulating a concise outline with clear comments has been more important than the detail of the proof itself. Figuring out how to manipulate inequalities and what values to pick for variables when existential quantifiers are involved follows smoothly from a great proof outline.

Tutorial this week disappointed me because, like the first one, it lacked depth and difficulty. The only part that I struggled with was the indentation for proofs, more specifically, where to outdent. However, this crucial part of the proof outline wasn't even relevant for the quiz and this disappointed me even more because I wanted to know how I was doing with indentation. Nevertheless, I consider it to be good practice and therefore a productive way to spend my time.

In summary, this week has served a confidence boost for me since I think that I understand the material better than many other students. Also, there wasn't anything this week that surprised me or made me question my knowledge. Overall, I think that this effect on my self-esteem makes me feel more comfortable about the upcoming assignment that Professor Heap has yet to post. In reading week, I plan to read about some more difficult proofs online to fill the lack of neural stimulation that I had in these past three lectures.